Reka Bentuk Struktur Data untuk Item Kerap Top-K Dinamik

Soalan dan bila menggunakannya

Satu strim ID integer yang tiada penghujung tiba satu item pada satu masa. add(x) merekodkan satu lagi kemunculan ID x. topK(k) mengembalikan sehingga k ID berbeza dengan kekerapan semasa tertinggi berserta kiraannya; ID yang terikat (seri) boleh muncul dalam sebarang susunan, dan k boleh berubah antara pertanyaan (query). Reka bentuk penyelesaian tepat untuk beban kerja read-heavy dan write-heavy serta analisis kos masa dan ruangnya. Jika bilangan ID berbeza boleh berkembang tanpa had manakala memori adalah tetap, sediakan reka bentuk anggaran (approximate) dan takrifkan maksud ralatnya.

Soalan ini sesuai untuk temu duga kejuruteraan perisian dan algoritma. Kontrak tepat hanya membenarkan penambahan (increment) kekerapan: tiada pemadaman, tetingkap gelongsor (sliding window), atau gabungan teragih. Andaikan N ialah bilangan kemas kini setakat ini dan D ialah bilangan ID berbeza, dengan k << D dalam kes lazim. Versi awam bagi soalan ini secara eksplisit meminta reka bentuk bergantung beban kerja dan lanjutan penstriman dengan memori terhad, jadi "peta cincangan (hash map) ditambah min-heap" hanyalah permulaan jawapan.

Perkara yang dinilai oleh penemu duga

Pertama, adakah calon menetapkan kontrak operasi dan nisbah beban kerja? Kumpulan data yang bertanya sekali selepas strim berakhir tidak sepatutnya menanggung kos penyelenggaraan yang sama seperti papan pendahulu dalam talian yang ditanya selepas setiap kemas kini.

Kedua, adakah kerumitan yang dinyatakan sepadan dengan keadaan (state) yang dikekalkan? Mengira dalam hash map dan membina min-heap bersaiz k pada masa pertanyaan memberikan jangkaan O(1) untuk add dan O(D log k) untuk topK. Dakwaan penyelenggaraan timbunan (heap) O(log k) bagi setiap kemas kini juga memerlukan penjejakan kedudukan heap dan penjelasan tentang bila item di luar heap memasukinya.

Ketiga, bolehkah calon membuktikan struktur dinamik adalah betul? Jawapan yang kukuh menyatakan tiga invarian: setiap ID tergolong dalam tepat satu baldi kekerapan; kekerapan baldi meningkat secara ketat dan tiada baldi yang kosong; dan kekerapan baldi bagi sesuatu ID adalah sama dengan kiraan terkumpul sebenarnya. Hujah kerumitan sepatutnya diterbitkan daripada invarian tersebut.

Keempat, bolehkah calon membezakan top-k tepat, heavy hitters, dan anggaran kekerapan? Space-Saving mengekalkan kunci calon dengan batas kiraan di bawah belanjawan pembilang yang tetap. Count-Min Sketch terutamanya menganggarkan kekerapan kunci yang dibekalkan dan tidak mengekalkan set ID yang boleh disenaraikan dengan sendirinya. Menganggap sketch sahaja sebagai senarai top-k menyebabkan penemuan calon tidak dijelaskan.

Soalan untuk dijelaskan sebelum menjawab

• Adakah k tetap atau khusus untuk pertanyaan? K yang tetap membenarkan heap bersaiz K yang diindeks. k yang arbitrari cenderung kepada struktur yang disusun merentas semua kekerapan.
• Apakah nisbah kemas kini kepada pertanyaan? Sistem write-heavy boleh menangguhkan kerja sehingga masa pertanyaan. Pertanyaan yang kerap mewajarkan pengekalan susunan pada setiap add.
• Adakah keputusan seri mesti mempunyai susunan berketentuan (deterministic)? Kontrak ini membenarkan sebarang susunan, jadi hash set di dalam setiap baldi sudah mencukupi. Keperluan ID menaik memerlukan set yang teratur dan menghapuskan kemas kini jangkaan O(1).
• Adakah pemadaman atau tetingkap masa diperlukan? Dengan hanya penambahan (increment), item beralih daripada kekerapan f ke kekerapan bersebelahan f + 1. Pemadaman menambah pergerakan songsang; tetingkap juga memerlukan keadaan tamat tempoh.
• Adakah D muat dalam memori? Jawapan tepat untuk taburan tanpa had mengekalkan kiraan setiap ID yang berbeza. Memori tetap memerlukan anggaran atau laluan kedua yang boleh dimainkan semula (replayable).
• Apakah ralat yang boleh diterima? "Hampir betul" tidak boleh diuji. Tentukan ralat kiraan aditif, set calon yang tidak pasti, atau syarat pemisahan kekerapan yang memperakui top-k.
• Bolehkah pembilang melimpah (overflow)? Perkhidmatan yang berjalan lama memerlukan pembilang 64-bit atau lebih luas. Contoh ini menggunakan JavaScript number dan hanya tepat dalam julat integer selamat.

Rangka kerja jawapan 30 saat

"Saya akan menjelaskan terlebih dahulu sama ada k berbeza-beza, nisbah baca-tulis, susunan seri, dan had memori. Untuk trafik write-heavy dan jarang membuat pertanyaan, saya akan menggunakan hash map untuk jangkaan penambahan O(1), kemudian mengimbas kiraan D ke dalam min-heap bersaiz k dalam O(D log k) bagi setiap pertanyaan. Jika pertanyaan dengan k arbitrari adalah kerap, saya akan mengekalkan senarai pautan berganda (doubly linked list) bagi baldi kekerapan yang menaik berserta peta ID → bucket. Satu kemas kini hanya memindahkan satu ID dari baldi f ke baldi bersebelahan f + 1, memberikan jangkaan kemas kini O(1); menyusuri ke belakang untuk k hasil menelan kos O(min(k, D)), dengan ruang O(D). Jika D tidak muat dalam memori, saya akan menggunakan pembilang Space-Saving tetap dengan batas ralat dan memperakui top-k hanya apabila batas-batas tersebut terpisah. Count-Min Sketch masih memerlukan set calon untuk menyenaraikan ID."

Penyelesaian langkah demi langkah

Langkah 1: Bandingkan reka bentuk tepat mengikut beban kerja

"Hash map ditambah min-heap" bukanlah pemenang sejagat. Ia sengaja meletakkan kerja penyusunan pada laluan pertanyaan, yang sesuai apabila operasi menulis mendominasi. Jika produk memaparkan papan pendahulu selepas setiap add, mengimbas kunci D secara berulang kali menjadi kekangan (bottleneck) dan struktur baldi kekerapan yang lebih rumit adalah berbaloi dengan kosnya.

Langkah 2: Wujudkan invarian baldi kekerapan

Kekalkan senarai berpautan berganda bagi baldi mengikut urutan kekerapan menaik. Setiap baldi memiliki satu set ID dengan kekerapan tersebut, manakala hash map mengesan baldi bagi sesuatu ID secara terus. ID baharu menyertai baldi kekerapan 1. ID sedia ada berpindah dari baldi f ke baldi f + 1. Oleh kerana satu kemas kini menambah tepat satu, baldi baharu hanya boleh disisipkan antara punca dan penggantinya; tiada carian senarai diperlukan. Alih keluar baldi punca sebaik sahaja ia menjadi kosong.

Tiga invarian membuktikan hasilnya:

1. Setiap ID dalam locations muncul dalam tepat satu set baldi.
2. frequency bagi setiap baldi yang tidak kosong adalah sama dengan kiraan sebenar setiap ID yang terkandung di dalamnya.
3. Kekerapan meningkat secara ketat dari head ke tail.

Oleh itu, menyusuri ke belakang dari tail tidak boleh meninggalkan ID berkekerapan lebih tinggi di belakang, manakala keputusan seri boleh dikembalikan dalam sebarang susunan. Setiap baldi yang dilawati menghasilkan sekurang-kurangnya satu hasil, jadi bilangan baldi yang dilawati tidak lebih besar daripada saiz output dan masa pertanyaan ialah O(min(k, D)).

Langkah 3: Laksanakan pertanyaan k-arbitrari yang tepat

interface Bucket {
  frequency: number;
  values: Set<number>;
  prev: Bucket | null;
  next: Bucket | null;
}

interface TopKEntry {
  value: number;
  count: number;
}

class FrequencyIndex {
  private readonly locations = new Map<number, Bucket>();
  private head: Bucket | null = null;
  private tail: Bucket | null = null;

  add(value: number): void {
    const source = this.locations.get(value);

    if (!source) {
      let target = this.head;
      if (!target || target.frequency !== 1) {
        target = this.insertBefore(this.head, 1);
      }
      target.values.add(value);
      this.locations.set(value, target);
      return;
    }

    let target = source.next;
    if (!target || target.frequency !== source.frequency + 1) {
      target = this.insertAfter(source, source.frequency + 1);
    }

    source.values.delete(value);
    target.values.add(value);
    this.locations.set(value, target);

    if (source.values.size === 0) {
      this.removeBucket(source);
    }
  }

  topK(k: number): TopKEntry[] {
    if (!Number.isInteger(k) || k < 0) {
      throw new RangeError("k must be a non-negative integer");
    }

    const result: TopKEntry[] = [];
    let bucket = this.tail;

    while (bucket && result.length < k) {
      for (const value of bucket.values) {
        result.push({ value, count: bucket.frequency });
        if (result.length === k) break;
      }
      bucket = bucket.prev;
    }

    return result;
  }

  private insertBefore(next: Bucket | null, frequency: number): Bucket {
    const bucket: Bucket = {
      frequency,
      values: new Set<number>(),
      prev: next?.prev ?? null,
      next,
    };

    if (bucket.prev) bucket.prev.next = bucket;
    else this.head = bucket;

    if (next) next.prev = bucket;
    else this.tail = bucket;

    return bucket;
  }

  private insertAfter(prev: Bucket, frequency: number): Bucket {
    const bucket: Bucket = {
      frequency,
      values: new Set<number>(),
      prev,
      next: prev.next,
    };

    if (prev.next) prev.next.prev = bucket;
    else this.tail = bucket;

    prev.next = bucket;
    return bucket;
  }

  private removeBucket(bucket: Bucket): void {
    if (bucket.prev) bucket.prev.next = bucket.next;
    else this.head = bucket.next;

    if (bucket.next) bucket.next.prev = bucket.prev;
    else this.tail = bucket.prev;
  }
}

Kerumitan ini menggunakan andaian masa malar jangkaan biasa untuk Map dan Set, bukan jaminan spesifikasi JavaScript bagi kes terburuk yang ketat O(1). topK(0) mengembalikan tatasusunan kosong, k > D mengembalikan semua ID, dan k yang negatif atau bukan integer akan melontarkan ralat (throw).

Langkah 4: Nyatakan jaminan anggaran di bawah memori terhad

Hash map yang tepat berkembang mengikut D. Space-Saving sebaliknya hanya menyimpan pembilang m yang mengandungi satu ID, anggaran kiraan, dan ralat maksimum; m > k diperlukan untuk membandingkan dengan calon sempadan k + 1. ID dijejaki yang diperhatikan akan menambah pembilangnya. Apabila ID yang tidak dijejaki tiba selepas semua pembilang dipenuhi, ia menggantikan ID dengan anggaran kiraan minimum c_min; anggaran baharu menjadi c_min + 1, dengan ralat yang direkodkan c_min.

Bagi setiap ID yang dipantau, kekerapan sebenar terletak dalam [estimate - error, estimate], dan kertas penyelidikan tersebut mengehadkan anggaran lebih (overestimation) maksimum kepada N / m. Set top-k boleh diperakui apabila batas bawah terkecil antara calon k pertama adalah tidak lebih kecil daripada anggaran batas atas bagi calon k + 1. Jika selang tersebut bertindih, kembalikan calon anggaran dan bukannya mempersembahkan susunan anggaran sebagai tepat. Apabila keseluruhan strim mempunyai D <= m, tiada penggantian berlaku dan kiraan kekal tepat.

Count-Min Sketch menggunakan tatasusunan pembilang width × depth yang tetap. Dengan width = ceil(e / ε) dan depth = ceil(ln(1 / δ)) pada strim penambahan sahaja, anggaran untuk ID yang dibekalkan tidak pernah jatuh di bawah kiraan sebenarnya dan, dengan kebarangkalian sekurang-kurangnya 1 - δ, adalah tidak lebih daripada true count + εN. Sketch tidak mengekalkan ID, jadi ia masih memerlukan heap calon, set calon, atau domain yang boleh disenaraikan. Sketch sahaja tidak dapat menjawab "ID manakah yang berada dalam top-k?"

Langkah 5: Sahkan terhadap oracle, bukan hanya satu contoh

Mulakan dengan [1, 2, 1, 3, 2, 1] dan sahkan bahawa topK(2) mengembalikan dua ID dengan kekerapan 3 dan 2. Kemudian rangkumi struktur kosong, k = 0, k > D, semua seri, satu item hangat ditambah banyak item tunggal, dan satu ID yang bergerak melalui banyak baldi.

Akhir sekali, jana strim kemas kini rawak dan gunakan kiraan cincangan naif berserta pengisihan penuh sebagai oracle. Pada selang masa tertentu, sahkan bahawa panjang hasil ialah min(k, D), ID adalah unik, setiap kiraan yang dilaporkan adalah tepat, dan tiada ID yang dikecualikan mempunyai kiraan di atas kiraan terpilih yang paling kecil. Pelaksanaan di atas melepasi semakan pembezaan (differential check) ini merentas 10,000 kemas kini rawak berketentuan dan beberapa nilai k.

Contoh jawapan yang kukuh

"Saya akan mengehadkan kontrak tepat kepada kemas kini penambahan sahaja, k khusus pertanyaan, dan susunan seri secara arbitrari. Bagi banyak operasi menulis dan pertanyaan yang jarang berlaku, saya hanya akan mengekalkan hash map ID → count untuk jangkaan penambahan O(1). Pertanyaan mengimbas ID D melalui min-heap bersaiz k, dengan kos masa O(D log k) dan ruang tambahan O(k).

Untuk pertanyaan papan pendahulu yang kerap, saya akan menggunakan baldi kekerapan berpautan berganda. Baldi disusun daripada kekerapan rendah ke tinggi dan mengandungi ID yang seri pada kekerapan tersebut; hash map mengesan baldi setiap ID. Satu add hanya memindahkan ID daripada f ke f + 1, jadi ia memeriksa baldi bersebelahan dan mengalih keluar baldi punca yang kosong. Kemas kini adalah dalam jangkaan O(1), menyusuri ke belakang dari ekor mengembalikan hasil dalam O(min(k, D)), dan jumlah ruang ialah O(D). Ketepatan terhasil daripada keahlian baldi yang unik, kiraan baldi yang tepat, dan susunan baldi yang meningkat secara ketat.

Jika D tidak muat dalam memori, kontrak tepat mesti diubah. Saya akan mengekalkan pembilang Space-Saving m dengan selang ralat calon; anggaran lebih maksimum dihadkan oleh N / m, dan saya akan memperakui set tersebut hanya apabila batas bawah bagi k yang pertama terpisah daripada batas atas yang berikutnya. Count-Min Sketch boleh menganggarkan ID yang dibekalkan tetapi masih memerlukan penemuan calon. Sebelum pelancaran, saya akan menjalankan ujian pembezaan rawak terhadap pengisihan penuh dan menguji secara eksplisit bagi kes seri, k tidak sah, dan sempadan limpahan pembilang."

Kesilapan lazim

• Memilih min-heap sebelum bertanya tentang beban kerja → Pertanyaan yang kerap mengimbas semua ID D, manakala pertanyaan yang jarang berlaku mungkin tidak mewajarkan penyelenggaraan berterusan → Letakkan kos pada laluan kemas kini atau pertanyaan mengikut nisbah sebenar.
• Mengekalkan satu K tetap apabila k berubah-ubah → Pertanyaan yang lebih besar daripada K yang dikekalkan tidak mempunyai set calon yang lengkap → Bataskan k secara eksplisit atau gunakan baldi kekerapan atau struktur teratur yang menyokong k arbitrari.
• Mengubah kunci heap di tempatnya (in-place) → Heap biasa tidak mengetahui kedudukan sesuatu item, jadi susunannya rosak atau rekod lapuk terkumpul → Kekalkan ID → heap index, atau alih keluar dan masukkan semula kunci lama dengan kerumitan yang dinyatakan.
• Membiarkan baldi kekerapan kosong kekal berpaut → Pertanyaan boleh menyusuri jurang daripada kekerapan 1 ke kiraan maksimum → Nyahpautkan baldi serta-merta selepas ID terakhirnya berpindah.
• Mendakwa pencincangan O(1) yang ketat → Map dan Set menyokong analisis kerumitan jangkaan biasa, bukan jaminan bahasa yang ketat → Nyatakan andaian cincangan; gunakan pokok seimbang dan terima O(log D) apabila batas kes terburuk penting.
• Mengembalikan top-k terus daripada Count-Min Sketch → Sketch menjawab pertanyaan kunci yang dibekalkan dan tidak boleh menyenaraikan ID yang tidak diketahui → Kekalkan penemuan calon secara berasingan atau gunakan Space-Saving, yang mengekalkan kunci calon.
• Melaporkan anggaran tanpa ralat → Penemu duga tidak dapat mengetahui sama ada kedudukan k dan k + 1 boleh dibezakan → Kembalikan anggaran, batas bawah dan atas, serta sama ada set tersebut diperakui.
• Hanya menguji sampel → Pautan terputus, baldi kosong, dan sempadan seri sering muncul hanya selepas urutan kemas kini yang panjang → Uji secara pembezaan terhadap oracle susun penuh dan sahkan invarian.

Soalan susulan dan jawapan

Susulan 1: Jika topK sentiasa menggunakan K = 100, adakah anda masih memerlukan baldi kekerapan?

Tidak semestinya. Peta kiraan, min-heap bersaiz 100, dan ID → heap index boleh melaraskan ahli heap atau membandingkan dengan nilai minimum selepas setiap kemas kini dalam O(log 100). Ia mungkin lebih mudah dari segi kod dan susun atur memori, tetapi ia tidak dapat menjawab topK(1000). Baldi kekerapan berbaloi dengan kerumitannya apabila k adalah arbitrari dan kemas kini masa malar jangkaan adalah penting.

Susulan 2: Apakah yang berubah jika ID yang seri mesti dalam susunan menaik?

Gantikan Set setiap baldi dengan set yang teratur, atau susun hanya baldi sempadan yang digunakan sebahagiannya oleh pertanyaan. Pilihan pertama menambah O(log s) pada setiap pergerakan untuk baldi bersaiz s; pilihan kedua membayar kos susunan sempadan hanya pada masa pertanyaan. Pilih mengikut kekerapan susunan berketentuan diperlukan.

Susulan 3: Bagaimanakah anda akan menambah remove(x)?

Pindahkan ID daripada kekerapan f ke f - 1 dengan menyemak baldi pendahulu secara simetri, mengalih keluar ID daripada locations apabila ia mencapai sifar. Tentukan sama ada mengalih keluar ID yang tiada akan melontarkan ralat atau diabaikan. Dengan penambahan dan pemadaman serentak, proses mencari, memindahkan, dan menyahpaut baldi kosong mesti berkongsi satu seksyen kritikal atomik, atau ID yang sama boleh muncul dalam dua baldi.

Susulan 4: Bagaimana jika pertanyaan hanya meminta 10 minit terakhir?

Kekerapan tidak lagi monotonik. Indeks baldi juga memerlukan peristiwa bercap masa atau kiraan berbaldi masa supaya tamat tempoh boleh mengeluarkan kemas kini songsang. Baris gilir bagi setiap peristiwa adalah tepat tetapi menggunakan ruang yang berkadar dengan peristiwa dalam tetingkap. Baldi masa mengurangkan keadaan sambil memperkenalkan ralat sempadan yang eksplisit. Ringkasan Space-Saving sepanjang sejarah tidak boleh menolak peristiwa tamat tempoh arbitrari secara terus.

Susulan 5: Bagaimana jika selang Space-Saving untuk kedudukan k dan k + 1 bertindih?

Tingkatkan belanjawan pembilang m, laporkan bahawa set calon belum diperakui, atau mainkan semula data untuk mengira set calon secara tepat. Laluan kedua hanya membetulkan calon yang dikekalkan. Jika ringkasan terlalu kecil untuk menjamin bahawa top-k sebenar memasuki set tersebut, besarkan set calon sebelum memainkan semula.

Susulan 6: Bagaimanakah anda memperoleh top-k global merentas shard?

Senarai top-k tempatan tidak dapat menghasilkan top-k global yang tepat untuk taburan arbitrari. ID tepat di bawah garis pemotongan pada setiap shard mungkin menduduki kedudukan global selepas pengagregatan. Reka bentuk yang tepat mesti mengagregatkan semua kiraan yang berkaitan atau mengekalkan batas calon yang membuktikan liputan. Reka bentuk anggaran boleh menggabungkan ringkasan yang boleh digabungkan, tetapi kontraknya mesti merangkumi ralat tambahan dan kelewatan pelaporan.