Video: [PBO] Class n obyek spidol -versi coding class 2024
Belajar menghitung objek dalam aliran dapat membantu Anda menemukan item yang paling sering atau memberi peringkat pada kejadian biasa dan tidak biasa. Algoritma ini memanfaatkan fungsi hash dan perkiraan sketsa. Hal itu terjadi setelah menyaring objek duplikat dan menghitung elemen berbeda yang muncul di arus data.
Anda menggunakan teknik ini untuk memecahkan masalah seperti menemukan kueri paling sering di mesin pencari, item terlaris dari pengecer online, halaman yang sangat populer di situs web, atau saham yang paling mudah menguap (dengan menghitung waktu stok adalah dijual dan dibeli).
Anda menerapkan solusi untuk masalah ini, Skrip Count-Min, ke arus data. Ini hanya memerlukan satu data dan menyimpan sesedikit mungkin informasi. Algoritma ini diterapkan dalam banyak situasi dunia nyata (seperti menganalisis lalu lintas jaringan atau mengelola arus data terdistribusi). Resepnya memerlukan penggunaan sekumpulan fungsi hash, masing-masing terkait dengan vektor bit, dengan cara yang menyerupai filter Bloom, seperti yang ditunjukkan pada gambar:
- Inisialisasi semua vektor bit menjadi nol di semua posisi.
- Terapkan fungsi hash untuk setiap vektor bit saat menerima objek dari arus. Gunakan alamat numerik yang dihasilkan untuk kenaikan nilai pada posisi itu.
- Terapkan fungsi hash ke objek dan ambil nilainya pada posisi yang terkait saat diminta memperkirakan frekuensi suatu objek. Dari semua nilai yang diterima dari vektor bit, Anda mengambil yang terkecil sebagai frekuensi arus.
Karena tabrakan selalu mungkin saat menggunakan fungsi hash, terutama jika vektor bit yang terkait memiliki beberapa slot, memiliki beberapa vektor bit di tangan meyakinkan Anda bahwa setidaknya satu dari mereka menyimpan nilai yang benar. Nilai pilihan harus paling kecil karena tidak dicampur dengan angka positif palsu akibat tabrakan.
