Czy filtry Bloom są w rzeczywistości szybsze niż skróty, nawet biorąc pod uwagę pamięć podręczną?

Filtry Bloom wyglądają naprawdę świetnie, jeśli weźmiesz pod uwagę, czy możesz ustalić, czy Int jest w zestawie z 99% pewnością w stałym czasie. Ale hashe mogą, z tą różnicą, że w skrócie większość czasu uzyskuje się dostęp do pamięci tylko raz. Dzięki filtrom kwitnienia musisz uzyskać do nich dostęp ~ 7 razy na żądanie w całkowicie odległych miejscach , aby mieć kilka braków pamięci podręcznej na żądanie.

Czy coś brakuje?

Brakuje sposobu, w jaki dwie struktury danych radzą sobie z kolizjami mieszania. Filtry Bloom nie przechowują rzeczywistych wartości, więc wymagana przestrzeń to stały rozmiar wyznaczonej tablicy. Zamiast tego, jeśli używasz tradycyjnego skrótu, próbuje on zapisać wszystkie podane wartości, więc rośnie z czasem.

Rozważ uproszczoną funkcję skrótu (tylko dla przykładu!) f(x) = x % 2. Teraz możesz wejść następujące liczby całkowite: 2, 3, 4, 5, 6, 7.

Standardowy skrót: podane wartości zostaną zaszyfrowane, a my skończymy z wieloma kolizjami z powodu f(2) = f(4) = f(6) = 0i f(3) = f(5) = f(7) = 1. Niemniej jednak skrót przechowuje wszystkie te wartości i będzie mógł powiedzieć, że 8nie jest w nim przechowywany. Jak to robi? Śledzi kolizje i przechowuje wszystkie wartości o tej samej wartości skrótu, a następnie, gdy je wywołujesz, dodatkowo porównuje zapytanie. Zapytajmy więc mapę o 8:, f(8) = 0więc przejdzie do wiadra, w którym już wstawiliśmy, 2, 4, 6i musi dokonać 3 porównań, aby powiedzieć, że 8nie było częścią danych wejściowych.

Filtr Bloom: Zwykle każda wartość wejściowa jest mieszana z króżnymi funkcjami skrótu. Ponownie, dla uproszczenia, załóżmy, że używamy tylko pojedynczej funkcji skrótu f. Potrzebujemy wtedy tablicy 2 wartości, a kiedy napotkamy dane wejściowe 2, oznacza to, że z powodu f(2) = 0ustawienia wartości tablicy w pozycji 0na wartość 1. To samo dzieje się w przypadku 4i 6. Podobnie 3, 5, 7każdy z wejść ustawia pozycję tablicy 1na wartość 1. Teraz pytamy, czy 8był częścią danych wejściowych: f(8) = 0a tablica w pozycji 0jest 1, więc filtr Bloom będzie fałszywie twierdził, że 8rzeczywiście był częścią danych wejściowych.

Aby uzyskać nieco bardziej realistyczny charakter, zastanówmy się nad dodaniem drugiej funkcji skrótu g(x) = x % 10. Dzięki temu wartość wejściowa 2prowadzi do dwóch wartości skrótu, f(2) = 0a g(2) = 2dwie odpowiadające pozycje tablicy zostaną ustawione na 1. Oczywiście tablica powinna mieć teraz przynajmniej rozmiar 10. Ale kiedy zapytamy o 8, sprawdzimy tablicę w pozycji z 8powodu g(8) = 8, i ta pozycja nadal będzie 0. Dlatego dodatkowe funkcje skrótu zmniejszają liczbę fałszywych alarmów.

Porównanie: Filtr Bloom używa kfunkcji skrótu, co oznacza, kże można uzyskać dostęp do losowych pozycji tablicy. Ale ta liczba jest dokładna. Zamiast tego hash gwarantuje ci tylko stały, zamortyzowany czas dostępu, ale może de-generować w zależności od charakteru twojej funkcji hash i danych wejściowych. Zwykle jest to szybsze, z wyjątkiem przypadków generowanych od nowa.

Jednak po kolizji skrótu standardowy skrót będzie musiał sprawdzić równość przechowywanych wartości z wartością zapytania. Ta kontrola równości może być dowolnie droga i nigdy nie nastąpi z filtrem Bloom.

Pod względem przestrzeni filtr Bloom jest stały, ponieważ nigdy nie ma potrzeby używania większej ilości pamięci niż wyznaczona tablica. Z drugiej strony, skrót rośnie dynamicznie i może być znacznie większy ze względu na konieczność śledzenia wartości kolizyjnych.

Kompromis: Teraz, gdy wiesz, co jest tanie, a co nie i w jakich okolicznościach, powinieneś być w stanie zobaczyć kompromis. Filtry Bloom są świetne, jeśli chcesz bardzo szybko wykryć, że wartość została wcześniej zauważona, ale może żyć z fałszywymi pozytywami. Z drugiej strony możesz wybrać mapę haszowania, jeśli chcesz zagwarantować poprawność za cenę niemożności dokładnego oszacowania czasu działania, ale możesz zaakceptować przypadki zdegenerowane zdegenerowane, które mogą być znacznie wolniejsze niż średnia.

Podobnie, jeśli masz ograniczone środowisko pamięci, możesz preferować filtry Bloom ze względu na gwarancję wykorzystania pamięci.

Przypadki użycia filtrów Blooma i skrótów są różne i w większości rozłączne, więc bezpośrednie porównanie nie ma sensu. Poza tym będzie to zależeć od technicznych szczegółów implementacji, ponieważ istnieje wiele sposobów radzenia sobie z kolizjami mieszania z różnymi kompromisami.

Filtr Bloom może odpowiedzieć, czy element jest w zestawie dla dużych zbiorów, z rozsądnym prawdopodobieństwem, ale nie do końca, przy użyciu niewielkiej ilości pamięci. Ogromne jak tryliony żywiołów. Ale nigdy nie są dokładne. Możesz ograniczyć liczbę fałszywych alarmów, używając więcej pamięci lub więcej funkcji skrótu.

Z drugiej strony tabele skrótów są dokładne, ale muszą przechowywać zestaw. Tak więc biliony elementów wymagałyby terrabytów pamięci (a to tylko biliony amerykańskie). Mogą także przechowywać dodatkowe dane dla każdego elementu, czego nie potrafią filtry Bloom.

Tak więc filtry Bloom są używane, gdy masz powolną metodę pozyskiwania danych dla niektórych członków (co obejmuje zapytania do serwera, odczyty z dysku itp.) Dużego zestawu (który nie zmieści się w pamięci lub przeniesienie go do klienta jest niepraktyczne lub inne) i chcą uniknąć uruchamiania wolnej operacji dla obiektów, których nie ma w zestawie.