streamalism.org

1. Áttekintés

Ebben a cikkben a Bloom szűrőkonstrukciót fogjuk megvizsgálni Gujávafa könyvtár. A Bloom szűrő egy memória-hatékony, valószínűségi adatszerkezet, amellyel megválaszolhatjuk a kérdést hogy egy adott elem halmazban van-e vagy sem.

Nincsenek hamis negatívumok Bloom szűrővel, tehát amikor visszatér hamis, 100% -ban biztosak lehetünk abban, hogy az elem nincs a halmazban.

Bloom-szűrő azonban hamis pozitív eredményt adhat vissza, tehát amikor visszatér igaz, nagy a valószínűsége annak, hogy az elem a készletben van, de nem lehetünk 100% -ig biztosak benne.

A Bloom-szűrő működésének részletesebb elemzéséhez áttekintheti ezt az oktatóanyagot.

2. Maven-függőség

Használni fogjuk Guava Bloom szűrőjének megvalósítását, ezért tegyük hozzá a gujávafa függőség:

 com.google.guava guava 29.0-jre 

A legújabb verzió megtalálható a Maven Central oldalon.

3. Miért érdemes használni a Bloom szűrőt?

A Bloom szűrő az úgy tervezték, hogy helytakarékos és gyors legyen. Használatakor megtehetjük adja meg a hamis pozitív válaszok valószínűségét, amelyeket elfogadhatunk és ennek a konfigurációnak megfelelően a Bloom szűrő a lehető legkevesebb memóriát foglalja el.

Ennek a helytakarékosságnak köszönhetően a Bloom szűrő könnyen elfér a memóriában még hatalmas számú elem esetén is. Néhány adatbázis, köztük a Cassandra és az Oracle, ezt a szűrőt használja első ellenőrzésként, mielőtt lemezt vagy gyorsítótárat használna, például amikor egy adott azonosítóra vonatkozó kérés érkezik.

Ha a szűrő visszaadja, hogy az azonosító nincs, az adatbázis leállíthatja a kérelem további feldolgozását, és visszatérhet az ügyfélhez. Ellenkező esetben a lemezre megy és visszaadja az elemet, ha megtalálható a lemezen.

4. Bloom szűrő létrehozása

Tegyük fel, hogy Bloom szűrőt szeretnénk létrehozni legfeljebb 500-ig Egész számok és hogy el tudjuk tolerálni a hamis pozitív eredmények egy százalékos (0,01) valószínűségét.

Használhatjuk a BloomFilter osztály a Gujávafa könyvtár ennek elérése érdekében. Át kell adnunk azon elemek számát, amelyeket várhatóan beillesztünk a szűrőbe, és a kívánt hamis pozitív valószínűséget:

BloomFilter szűrő = BloomFilter.create (Csatornák.integerFunnel (), 500, 0,01);

Most adjunk hozzá néhány számot a szűrőhöz:

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

Csak három elemet vettünk fel, és meghatároztuk, hogy a beszúrások maximális száma 500 lesz, tehát a Bloom szűrőnk nagyon pontos eredményeket kell hoznia. Teszteljük a mightContain () módszer:

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

Ahogy a neve is sugallja, nem lehetünk 100% -ban biztosak abban, hogy egy adott elem valóban szerepel a szűrőben, amikor a módszer visszatér igaz.

Mikor mightContain () visszatér igaz példánkban 99% -ban biztosak lehetünk abban, hogy az elem benne van a szűrőben, és egy százalék valószínűséggel hamis pozitív az eredmény. Amikor a szűrő visszatér hamis, 100% -ban biztosak lehetünk abban, hogy az elem nincs jelen.

5. Túltelített Bloom szűrő

Amikor megtervezzük a Bloom szűrőnket, fontos, hogy ésszerűen pontos értéket adjunk meg a várható elemszámra. Ellenkező esetben a szűrőnk a kívántnál jóval nagyobb arányban ad vissza hamis pozitív eredményt. Lássunk egy példát.

Tegyük fel, hogy létrehoztunk egy kívánt százalékos hamis pozitív valószínűségű szűrőt, és néhány elem várható értéke öt, de ezután 100 000 elemet illesztettünk be:

BloomFilter szűrő = BloomFilter.create (Funnels.integerFunnel (), 5, 0,01); IntStream.range (0, 100_000) .forEach (szűrő :: put); 

Mivel a várható elemek száma olyan kicsi, a szűrő nagyon kevés memóriát foglal el.

Mivel azonban a vártnál több elemet adunk hozzá, a A szűrő túltelítetté válik, és sokkal nagyobb a valószínűsége, hogy hamis pozitív eredményeket ad vissza mint a kívánt egy százalék:

assertThat (filter.mightContain (1)). isTrue (); assertThat (filter.mightContain (2)). isTrue (); assertThat (filter.mightContain (3)). isTrue (); assertThat (filter.mightContain (1_000_000)). isTrue ();

Vegye figyelembe, hogy a mayContatin () módszer visszatért igaz még egy olyan értékért is, amelyet nem illesztettünk be korábban a szűrőbe.

6. Következtetés

Ebben a gyors bemutatóban megvizsgáltuk a Bloom szűrő adatstruktúrájának valószínűségi jellegét - a Gujávafa végrehajtás.

Ezeknek a példáknak és kódrészleteknek a megvalósítását megtalálhatja a GitHub projektben.

Ez egy Maven projekt, ezért könnyen importálhatónak és futtathatónak kell lennie.