Bagaimanakah anda melaksanakan skip list dan menerangkan tingkah laku O(log N) yang dijangkakan?

1. Soalan

Anda memerlukan kamus tertib yang menyokong carian kunci, penyisipan, pemadaman, dan imbasan julat. Set data berkembang secara dinamik, dan penemu duga mahukan operasi purata menghampiri O(log N) tanpa memerlukan pokok AVL atau red-black tree. Reka bentuk skip list dan analisis kerawakan, sempadan, serta susun atur memori.

2. Kekangan dan penjelasan

• Tentukan sama ada kunci adalah unik; jika tidak, tentukan dasar tulis ganti, pengiraan, atau susunan stabil.
• Pilih aras maksimum dan kebarangkalian kenaikan p; bina indeks ke atas daripada senarai terpaut paling bawah.
• Carian, penyisipan, dan pemadaman mengekalkan pendahulu untuk setiap aras; lelaran julat mengikuti senarai paling bawah.
• Bincangkan struktur bebenang tunggal terlebih dahulu. Keserentakan memerlukan penguncian tambahan, pemversian, atau bukti untuk algoritma bebas kunci (lock-free).

3. Idea teras

Setiap nod memiliki tatasusunan penuding ke hadapan bersaiz rawak. Carian bermula di kepala aras tertinggi: maju selagi kunci seterusnya berada di bawah sasaran, jika tidak, turun satu aras. Penyisipan merekodkan pendahulu, memilih ketinggian rawak, dan menyambungkan nod ke dalam setiap aras. Pemadaman menggunakan tatasusunan pendahulu yang sama untuk memutuskan pautannya. Aras atas yang jarang memberikan penuding yang dijangkakan O(N) dan carian, penyisipan, serta pemadaman yang dijangkakan O(log N).

4. Pelaksanaan rujukan

randomLevel(rng, p, maxLevel):
  level = 1
  while level < maxLevel and rng.uniform01() < p:
    level += 1
  return level

findPredecessors(key):
  update = array(maxLevel)
  node = head
  for level from maxLevel - 1 down to 0:
    while node.forward[level] != nil and node.forward[level].key < key:
      node = node.forward[level]
    update[level] = node
  return update

insert(key, value):
  update = findPredecessors(key)
  if update[0].forward[0].key == key:
    update[0].forward[0].value = value
    return
  node = Node(key, value, randomLevel(rng, p, maxLevel))
  for level in 0 .. node.height - 1:
    node.forward[level] = update[level].forward[level]
    update[level].forward[level] = node

Periksa nil sebelum membaca kunci dan pastikan ketinggian baharu tidak pernah melebihi maxLevel. Pemadaman menyambung semula setiap aras yang menuding ke sasaran dengan penggantinya. Jika aras tertinggi menjadi kosong, kurangkan kiraan aras aktif tanpa memindahkan nod.

5. Kerumitan dan kes terburuk

Dengan kebarangkalian kenaikan tetap dan sumber rawak bebas, aras dan panjang laluan adalah logaritma dalam jangkaan dan ruang yang dijangkakan ialah O(N). Jika kerawakan gagal atau pihak lawan boleh meramalkan aras, struktur boleh merosot menjadi senarai terpaut dan operasi menjadi O(N). Gunakan sumber rawak berkualiti tinggi, hadkan ketinggian maksimum, bina semula secara berkala, atau pilih pokok seimbang deterministik untuk beban kerja adversarial.

6. Pengesahan dan kompromi keserentakan

• Uji kunci tertib, pendua, kosong, dan ekstrem untuk carian, kemas kini, pemadaman, dan lelaran julat.
• Ukur taburan ketinggian, purata panjang laluan, dan bilangan penuding merentasi beberapa nilai N.
• Mainkan semula urutan operasi rawak terhadap peta tertib rujukan dan bandingkan kandungan serta susunan.
• Untuk keserentakan, terangkan keterperincian kunci (lock granularity), pemadaman logik, tebus guna memori, dan risiko ABA; membungkus penulisan penuding dalam satu kunci bukanlah reka bentuk bebas kunci.

7. Kesilapan lazim

• Melaksanakan carian tanpa tatasusunan pendahulu, memaksa penyisipan atau pemadaman mengimbas semula senarai.
• Mengabaikan dasar kunci pendua dan menghasilkan susunan julat yang tidak stabil.
• Memperlakukan jangkaan O(log N) sebagai jaminan kes terburuk tanpa membincangkan kerawakan dan input adversarial.
• Menggunakan tatasusunan ketinggian tetap yang membazirkan memori atau membenarkan ketinggian tanpa batasan yang melimpahkan tatasusunan.

8. Mata pemarkahan temu duga

Mencari dari aras tinggi ke bawah

Calon menerangkan syarat kemaraan setiap aras, bila perlu turun, dan mengapa senarai paling bawah mengandungi setiap elemen.

Mengekalkan pendahulu dengan betul

Calon menyimpan tatasusunan kemas kini (update array) untuk setiap aras dan mengendalikan tulis ganti, penuding nil, serta mengecilkan aras aktif tertinggi.

Menerangkan kerumitan kebarangkalian

Calon menyatakan masa yang dijangkakan O(log N), ruang yang dijangkakan O(N), dan syarat yang menyebabkan kemerosotan O(N).

Mengenal pasti sempadan keserentakan

Calon membincangkan kunci, versi, pemadaman logik, tebus guna memori, dan ABA dan bukannya menganggap kod bebenang tunggal sebagai serentak.