Filter Bloom di Jawa dengan Jambu

Hari baik untuk semua

Kami meluncurkan kursus baru - "Algoritma untuk Pengembang" , yang dirancang bagi mereka untuk meningkatkan pengetahuan mereka tentang berbagai struktur dan algoritma untuk pemrosesan data, memecahkan masalah aljabar dan masalah pemrograman dinamis untuk berbagai bahasa. Jadi hari ini kami berbagi catatan kecil tentang pengoperasian filter Bloom di Jawa.

Pendahuluan

Pada artikel ini, kita akan melihat struktur filter Bloom dari perpustakaan Guava. Filter Bloom adalah struktur data probabilistik dengan penggunaan memori yang efisien yang dapat kita gunakan untuk menjawab pertanyaan "Apakah elemen ini di set?".

Tidak ada negatif palsu di filter Bloom, jadi jika itu mengembalikan false, Anda bisa 100% yakin bahwa elemen ini tidak ada di set.

Namun, filter Bloom dapat mengembalikan false positive , jadi ketika true dikembalikan, probabilitasnya tinggi sehingga elemen tersebut benar-benar ada di set, tetapi probabilitasnya tidak 100%.

Untuk mempelajari lebih lanjut tentang pengoperasian filter Bloom, lihat panduan ini .



Kecanduan maven

Kami akan menggunakan implementasi Guava dari filter Bloom, jadi tambahkan ketergantungan Guava
Versi terbaru dapat ditemukan di Maven Central .

<dependency> <groupId>com.google.guava</groupId> <artifactId>guava</artifactId> <version>22.0</version> </dependency> 

Mengapa menggunakan filter bloom?

Filter Bloom dirancang agar ekonomis dan cepat . Saat menggunakannya, kami dapat mengklarifikasi kemungkinan jawaban positif palsu yang siap kami terima , dan, sesuai dengan konfigurasi, filter Bloom akan mengambil memori sesedikit mungkin.

Karena ekonominya, filter Bloom mudah masuk ke memori bahkan dengan sejumlah besar elemen. Beberapa database, termasuk Cassandra dan Oracle, menggunakan filter ini untuk pemeriksaan awal sebelum mengakses disk atau cache, misalnya, ketika permintaan untuk ID tertentu diterima.

Jika filter mengatakan bahwa tidak ada ID, database dapat berhenti memproses permintaan dan kembali ke klien. Kalau tidak, permintaan pergi ke disk dan mengembalikan item yang ditemukan.

Membuat Filter Bloom

Misalkan kita ingin membuat filter Bloom untuk tidak lebih dari 500 bilangan bulat, dan kita dilipatgandakan oleh probabilitas positif palsu satu persen (0,01).

Untuk melakukan ini, kita bisa menggunakan kelas BloomFilter dari perpustakaan Guava. Penting untuk mentransfer jumlah elemen yang dilaporkan ke filter, dan probabilitas positif palsu yang diinginkan:

 BloomFilter<Integer> filter = BloomFilter.create( Funnels.integerFunnel(), 500, 0.01); 

Sekarang tambahkan beberapa angka ke filter:

 filter.put(1); filter.put(2); filter.put(3); 

Kami menambahkan hanya tiga elemen dan menentukan jumlah sisipan maksimum - 500, sehingga filter Bloom kami harus memberikan hasil yang cukup akurat. Uji dengan metode mightContain() :

 assertThat(filter.mightContain(1)).isTrue(); assertThat(filter.mightContain(2)).isTrue(); assertThat(filter.mightContain(3)).isTrue(); assertThat(filter.mightContain(100)).isFalse(); 

Seperti namanya, kita tidak dapat 100% yakin bahwa elemen ini benar-benar ada dalam filter jika metode tersebut mengembalikan true.

Dalam kasus kami, ketika mightContain() mengembalikan true, 99% bahwa elemen ada di filter, dan 1%, bahwa hasilnya adalah false positive. Jika filter mengembalikan false, Anda dapat 100% yakin bahwa elemennya hilang.

Filter Bloom berlebih

Saat mendesain filter Bloom, penting untuk memberikan nilai yang cukup akurat untuk jumlah elemen yang diharapkan. Kalau tidak, filter kami akan mengembalikan false positive lebih sering daripada yang kita inginkan. Pertimbangkan sebuah contoh.

Misalkan kita membuat filter dengan probabilitas false positive yang diinginkan sama dengan satu persen dan jumlah elemen yang diharapkan sama dengan lima, tapi kemudian kita memasukkan 100.000 elemen:

 BloomFilter<Integer> filter = BloomFilter.create( Funnels.integerFunnel(), 5, 0.01); IntStream.range(0, 100_000).forEach(filter::put); 

Mengharapkan begitu sedikit elemen, filter akan memakan sedikit memori.
Namun, setelah menambahkan jumlah elemen yang jauh lebih besar, filter menjadi terlalu jenuh dan memiliki probabilitas lebih tinggi untuk menghasilkan hasil positif palsu daripada satu persen yang diinginkan.

Perhatikan bahwa metode mightContatin() mengembalikan nilai true bahkan untuk nilai yang sebelumnya tidak kami masukkan ke filter.

Kesimpulan

Dalam tutorial singkat ini, kami melihat sifat probabilistik dari struktur data filter Bloom - menggunakan implementasi Guava.

Implementasi semua contoh dan cuplikan kode ini dapat ditemukan di proyek GitHub .

Ini adalah proyek Maven, jadi impor dan peluncuran seharusnya tidak sulit.

AKHIR

Kami menunggu komentar dan pertanyaan, yang, seperti biasa, dapat ditinggalkan di sini dan pergi ke hari open house ke guru kursus Mikhail Gorshkov .