Laman utama video kami kini memaparkan set 24 cadangan baharu pada setiap penyegaran, hasil daripada peralihan kepada pensampelan takungan berwajaran (weighted reservoir sampling - A-Res). Perubahan ini menghapuskan masalah “grid yang sama selamanya” yang menjejaskan suapan berasaskan skor kami sebelum ini.
Mengapa pendekatan lama merosakkan pengalaman pengguna
Setiap dua jam, kami menarik video trending terkini daripada lapan wilayah dan memasukkan hasilnya ke dalam jadual SQLite. Penyelesaian naif adalah dengan menyusun keseluruhan set—mengikut skor relevansi—dan mengambil 24 teratas. Kaedah tersebut menjamin item dengan skor tertinggi akan muncul, tetapi ia juga menjamin item tersebut akan kekal di sana. Satu klip tular boleh mendominasi kedudukan 1 selama berhari-hari, dan pengguna akan melihat grid yang serupa setiap kali mereka memuat semula halaman.
Selain daripada pengalaman yang membosankan, menyusun keseluruhan jadual bagi setiap permintaan memaksa SQLite memuatkan struktur sementara yang besar ke dalam memori, yang mana ia adalah membazir.
Apa yang diberikan oleh pensampelan takungan berwajaran kepada kita
Pensampelan takungan berwajaran menyelesaikan dua masalah sekaligus:
- Kesegaran dengan bias – peluang setiap video untuk dipilih adalah berkadar terus dengan wajarannya (contohnya, skor relevansi). Video dengan wajaran dua kali ganda mempunyai kebarangkalian dua kali lebih tinggi untuk muncul, tetapi tiada item yang dijamin mendapat tempat.
- Kecekapan memori – algoritma ini hanya menyimpan “takungan” bersaiz tetap sebanyak k item (k = 24 untuk suapan kami). Ia memproses aliran dalam satu laluan tunggal, jadi penggunaan memori kekal pada O(k) tanpa mengira berapa banyak calon yang tiba.
Idea utamanya adalah mudah. Semasa kami mengimbas baris yang masuk, kami menetapkan kunci rawak kepada setiap item yang menggabungkan wajarannya, kemudian mengekalkan k item dengan kunci tertinggi.
Algoritma dalam praktis
Bagi setiap video, kita:
- Ambil nombor rawak seragam u ∈ (0, 1).
- Kira kunci k = u^(1/weight).
(Semakin tinggi wajaran, semakin besar kunci yang dijangkakan.) - Masukkan item ke dalam min-heap yang menyimpan k kunci teratas semasa.
Jika heap melebihi saiz k, kami membuang kunci terkecil.
Apabila aliran tamat, heap tersebut mengandungi 24 video yang akan kami paparkan.
Menangani had titik apungan (floating-point)
Apabila wajaran video sangat besar, u^(1/weight) mengecil kepada nilai yang tidak dapat dibezakan daripada 1.0 dalam aritmetik ketepatan berganda (double-precision), menyebabkan banyak item berat berkongsi kunci yang sama dan kehilangan sifat rawak. Penyelesaiannya adalah dengan bekerja dalam ruang log (log space):
- Kira log_key = log(u) / weight dan bukannya ungkapan kuasa.
Oleh kerana logaritma menukarkan eksponen kepada pendaraban, susunan kunci terpelihara sambil mengelakkan masalah ketepatan. Pengiraan ini hampir tidak memerlukan kos tambahan.
Senarai semak pelaksanaan
- Struktur data: min-heap (gilir keutamaan) bersaiz k menyimpan kunci terbesar dengan cekap (O(log k) bagi setiap penyisipan).
- Jenis numerik: gunakan nombor titik apungan 64-bit untuk u dan kunci berasaskan log; ia memberikan ketepatan yang mencukupi untuk julat wajaran tipikal.
- Semakan kewarasan statistik: jalankan ujian Monte-Carlo pantas pada set sampel kecil. Jika item dengan wajaran 10 muncul kira-kira sepuluh kali lebih kerap daripada wajaran 1, pelaksanaan tersebut adalah betul.
- Penstriman satu laluan: algoritma ini tidak perlu mengetahui jumlah keseluruhan calon lebih awal, yang mana ia sesuai secara semula jadi dengan kursor SQLite kami yang menghasilkan baris satu demi satu.
Kesimpulan
Pensampelan takungan berwajaran membolehkan perkhidmatan cadangan video mengekalkan kesegaran laman utamanya, menghormati skor relevansi, dan kekal ringan memori—semuanya dengan satu laluan tunggal ke atas puluhan ribu calon. Dengan memindahkan pengiraan kunci ke dalam ruang log dan menggunakan min-heap, kaedah ini kekal tepat dan berprestasi tinggi.