Bagaimanakah anda akan melaksanakan baris gilir keutamaan terikat yang stabil?

1. Masalah

Laksanakan StableBoundedPriorityQueue. Setiap entri mempunyai priority, sequence, dan value; bandingkan priority dahulu dan sequence kedua. Dengan kapasiti C, push menyimpan paling banyak C entri. Entri baharu menggantikan entri terburuk semasa hanya apabila ia lebih baik; jika tidak ia ditolak. pop mengembalikan entri terbaik.

2. Kekangan dan penjelasan

• C ialah integer positif; dengan C=0, setiap pemasukan ditolak tanpa menyentuh sempadan tatasusunan.
• Nombor yang lebih rendah bermakna keutamaan lebih tinggi; keutamaan yang sama mesti keluar mengikut susunan pemasukan.
• Menolak item terburuk apabila penuh memerlukan pencarian item tersebut. Min-heap tunggal tidak boleh mendedahkannya secara langsung dalam O(log C), jadi gunakan indeks kedua, max-heap, atau terima imbasan linear.
• Mulakan dengan pelaksanaan bebenang tunggal. Pengeluar dan pengguna serempak memerlukan kunci luaran atau baris gilir serempak khusus.

3. Pendekatan teras

Gunakan min-heap untuk item seterusnya, disusun mengikut (priority, sequence). Gunakan max-heap untuk item terburuk, disusun supaya keutamaan lebih besar dan jujukan lebih lewat adalah lebih buruk. Kedua-dua timbunan merujuk kepada rekod entri yang sama. Pembuangan menandakan entri sebagai alive=false; setiap timbunan membuang nod mati apabila ia mencapai akarnya. Pemadaman malas (lazy deletion) ini mengelakkan pemadaman timbunan pada kedudukan sebarangan.

Untuk kapasiti kecil, imbasan linear untuk item terburuk adalah lebih mudah: pop kekal O(log C), manakala push pada baris gilir penuh berkos O(C). Nyatakan pertukaran kompromi ini sebelum membentangkan pengoptimuman dua timbunan.

4. Pelaksanaan rujukan

record Entry(priority, sequence, value, alive=true)

push(priority, value):
  if capacity == 0: return false
  candidate = Entry(priority, nextSequence(), value)
  if size < capacity:
    add candidate to minHeap and maxHeap
    size += 1
    return true
  discard dead nodes from maxHeap
  worst = maxHeap.peek()
  if (priority, candidate.sequence) >= (worst.priority, worst.sequence):
    return false
  worst.alive = false
  pop maxHeap
  add candidate to both heaps
  return true

pop():
  discard dead nodes from minHeap
  if minHeap is empty: return EMPTY
  entry = pop minHeap
  entry.alive = false
  size -= 1
  return entry.value

Kunci max-heap bermaksud "lebih besar adalah lebih buruk": keutamaan lebih besar adalah lebih buruk, dan untuk keutamaan yang sama jujukan lebih besar adalah lebih lewat dan oleh itu lebih buruk. Jika sesuatu bahasa tiada max-heap, nafikan kunci atau sediakan pembanding (comparator). nextSequence mestilah monotonik; gunakan integer lebar atau tetapkannya semula hanya apabila baris gilir kosong.

5. Kerumitan dan pertukaran kompromi

Pemasukan yang diterima menambah satu nod pada setiap timbunan, jadi ia berkos O(log C); pop berkos O(log C). Penggantian juga berkos O(log C). Pemadaman malas boleh meninggalkan nod mati buat sementara waktu, tetapi setiap nod mati dikeluarkan sekali sahaja, memberikan operasi O(log C) terlunas dan ruang O(C) dengan peningkatan faktor malar. Varian imbasan linear menggunakan kurang ruang dan kod lebih pendek tetapi berkos O(C) untuk pemasukan pada baris gilir penuh.

6. Pengesahan dan kebolehcerapan

• Liputi C=0, C=1, baris gilir kosong, penolakan berulang, dan penggantian berulang.
• Masukkan beberapa entri berkeutamaan sama dan sahkan susunan FIFO mengikut jujukan.
• Uji calon yang lebih buruk, sama, dan lebih baik terhadap baris gilir penuh; jangkakan tolak, tolak, dan ganti.
• Bandingkan surihan operasi rawak dengan model rujukan yang mengisih semua entri hidup mengikut (priority, sequence) dan memotongnya kepada C.
• Rekodkan panjang baris gilir, bilangan penolakan, dan bilangan pembersihan nod malas. Kadar penolakan yang meningkat boleh mencetuskan pendikit hulu (upstream throttling) atau penyingkiran beban (load shedding).

7. Kesilapan lazim

• Mengisih mengikut keutamaan sahaja, yang menghilangkan kestabilan FIFO untuk seri.
• Menganggap keutamaan berangka lebih besar adalah lebih penting tanpa mengesahkan arahnya.
• Mengeluarkan akar timbunan sebelum kemasukan disahkan, yang membuang tugas terbaik apabila baris gilir penuh.
• Gagal membuang nod mati, menyebabkan peek mengembalikan entri yang telah digantikan atau dibatalkan.
• Menggunakan cap masa jam dinding untuk nombor jujukan; pemunduran jam atau pemasukan pada detik yang sama boleh memecahkan FIFO.

8. Soalan susulan

Bagaimanakah anda akan menguatkuasakan kuota bagi setiap penyewa?

Simpan kiraan dan had untuk setiap penyewa. Periksa kedua-dua kapasiti global dan kuota penyewa sebelum pemasukan, dan kira dua sebab penolakan secara berasingan supaya penyewa aktif dapat dilihat.

Bagaimanakah anda akan membatalkan atau mengutamakan semula entri?

Berikan setiap entri satu ID dan gunakan pemadaman malas. Pembatalan menandakannya sebagai mati; pengutamaan semula mencipta entri baharu dan membatalkan entri lama. Bersihkan nod mati semasa mengintai atau mengeluarkan daripada memadam kedudukan timbunan sebarangan.

Bilakah anda patut menggunakan baris gilir keutamaan serempak daripada pustaka?

Gunakan pelaksanaan serempak yang teruji apabila berbilang bebenang atau proses menghasilkan dan menggunakan, penungguan menyekat diperlukan, atau had memori adalah ketat. Reka bentuk dua timbunan tersuai hanya sesuai dengan sempadan bebenang tunggal yang jelas dan kitaran hayat yang boleh diuji.