Pengembangan algoritma penghitungan baru yang efisien
Pendahuluan
- Bayangkan Anda sedang melakukan pemantauan satwa liar di hutan purba.
- Anda mengambil foto hewan dengan kamera digital, dan ingin mengetahui jumlah hewan yang tidak duplikat.
- Metode yang ada mengharuskan semua hewan diingat dan dibandingkan, tetapi ini tidak efisien.
Situasi masalah
- Di platform berskala besar seperti Facebook, menghitung jumlah pengguna unik yang login setiap hari adalah hal yang sulit.
- Baru-baru ini, para ilmuwan komputer mengusulkan metode baru untuk memperkirakan jumlah item unik dalam daftar panjang.
- Algoritma ini hanya perlu mengingat sedikit item.
Algoritma CVM
- Algoritma CVM merupakan langkah penting dalam menyelesaikan masalah elemen unik yang telah diteliti selama lebih dari 40 tahun.
- Algoritma ini dapat memperkirakan jumlah elemen unik dalam aliran data secara efisien.
- "Algoritma baru ini sangat sederhana dan mudah diimplementasikan" - Andrew McGregor
Contoh: audiobook Hamlet
- Hamlet memiliki 30.557 kata. Untuk mengetahui berapa banyak yang unik, semua kata harus diingat.
- Algoritma CVM menggunakan randomisasi untuk mengurangi penggunaan memori.
Cara kerja algoritma CVM
- Putaran pertama: catat 100 kata, dan hapus kata duplikat dengan lemparan koin.
- Putaran kedua: untuk mempertahankan kata duplikat dengan lebih ketat, diperlukan dua kali lemparan koin.
- Putaran ketiga: diperlukan tiga kali lemparan koin.
- Ini diulang hingga putaran ke-k untuk memperkirakan jumlah kata unik.
Verifikasi akurasi
- Akurasi berubah tergantung ukuran memori.
- Jumlah kata unik di Hamlet adalah 3.967; dengan memori 100, estimasi rata-ratanya 3.955, dan dengan memori 1.000, estimasi rata-ratanya 3.964.
Kesimpulan
- "Bahkan untuk masalah yang mendasar dan telah diteliti dengan baik, ada solusi yang sederhana tetapi tidak intuitif" - William Kuszmaul
Opini GN⁺
- Berguna dalam situasi data streaming: Algoritma CVM dapat memperkirakan item unik secara efisien dalam aliran data berskala besar, sehingga berguna untuk analisis waktu nyata.
- Efisiensi memori: Karena dapat meminimalkan penggunaan memori sambil tetap menjaga akurasi tinggi, algoritma ini sangat menguntungkan terutama di lingkungan dengan keterbatasan memori.
- Pentingnya randomisasi: Fakta bahwa randomisasi dapat menyelesaikan masalah kompleks dengan cara sederhana menunjukkan potensi penerapannya di bidang lain juga.
- Pertimbangan saat adopsi teknologi: Saat mengadopsi algoritma ini, perlu mempertimbangkan keseimbangan antara ukuran memori dan akurasi. Jika memori tidak cukup, akurasi dapat menurun.
- Teknologi terkait: Layak dibandingkan dengan algoritma estimasi elemen unik lain seperti HyperLogLog. Penting untuk memahami kelebihan dan kekurangan masing-masing algoritma agar dapat memilih solusi optimal yang sesuai dengan situasi.
1 komentar
Komentar Hacker News
Ringkasan kumpulan komentar Hacker News
Algoritma yang mirip dengan HyperLogLog
Dijelaskan algoritma yang mirip dengan HyperLogLog, menggunakan rangkaian lemparan koin untuk menjelaskan algoritma sederhana. Algoritma ini bekerja sangat efisien terutama pada data streaming dan menggunakan sedikit memori.
Menunjukkan kesalahan dalam penjelasan algoritma
Disebutkan bahwa penjelasan algoritma itu keliru, lalu diberikan metode yang benar melalui contoh kode. Pendekatan menyimpan kata terlebih dahulu lalu menghapusnya menghasilkan hasil yang lebih akurat.
Rekomendasi makalah
Disebutkan bahwa makalahnya semudah dibaca seperti posting blog, tetapi memberikan informasi yang lebih banyak. Makalah itu menjelaskan algoritma sederhana untuk memperkirakan kardinalitas himpunan pada data streaming.
Contoh implementasi Python
Diberikan contoh implementasi Python untuk algoritma streaming. Dengan kode yang sederhana, pembaca bisa memahami dan mempraktikkan algoritma tersebut.
Berguna untuk refactoring sistem
Disebutkan sebagai metode yang menarik yang bisa menggantikan pendekatan HyperLogLog saat melakukan refactoring sistem yang menghitung dengan memasukkan jumlah kunjungan ke tabel.
Metode yang efisien dalam penggunaan memori
Disebutkan bahwa ilmuwan komputer telah menemukan cara memperkirakan ukuran subset dengan metode yang efisien dalam penggunaan memori.
Diskusi tentang Chernoff Bound
Dibahas variasi Chernoff Bound yang digunakan dalam makalah. Disebutkan bahwa belum pasti apakah variasi ini merusak ketepatan pembuktiannya.
Perbedaan antara estimasi elemen unik dan penghitungan
Disebutkan bahwa memperkirakan jumlah elemen unik dan benar-benar menghitungnya adalah dua hal yang sangat berbeda, sehingga judulnya dianggap kurang tepat.
Pengenalan algoritma stream yang efisien
Diperkenalkan algoritma yang efisien dan mudah diimplementasikan untuk menemukan k item teratas dalam stream. Makalah Karp, Shenker & Papadimitriou direkomendasikan.
Pentingnya berpikir kreatif
Disebutkan bahwa contoh "berpikir di luar kebiasaan" sangat menyenangkan, serta ditekankan bahwa menemukan pertanyaan yang tepat penting untuk memecahkan masalah. Diharapkan berbagai contoh dapat membantu menginternalisasi dan menerapkan cara berpikir kreatif.