Posts tagged ‘sets’

Kwitnące zbiory

2011-06-30 22:03

Przedstawię dzisiaj interesującą strukturę danych, będącą pewnego rodzaju uogólnieniem lub modyfikacją kontenerów typu bitset. Nazywa się ona filtrem Blooma (Bloom filter) i stanowi przykład struktury probabilistycznej, czyli działającej… czasami ;) Nie niweluje to aczkolwiek w żaden sposób jej przydatności, o czym zresztą opowiem dalej.

Filtr Blooma to tablica bitowa, w której przechowujemy pewien zbiór. Liczba owych bitów – i to jest pierwsza różnica w stosunku do bitsetunie jest równa liczbie wszystkich możliwych elementów zbioru. Wręcz przeciwnie, zwykle jest ona znacznie, znacznie mniejsza.
Drugą różnicą jest reprezentacja elementu, która dla odmiany zajmuje więcej miejsca. Definiuje je określona z góry liczba bitów, rozrzuconych po całej tablicy i ustawionych na 1. Sposób owego rozmieszczenia jest określony przez zestaw funkcji haszujących, przyjmujących element zbioru jako swój argument i zwracających indeks jednej z pozycji w tablicy. Owych funkcji jest zaś tyle, ile bitów reprezentacji.


Poglądowe przedstawienie filtru Blooma

Jak wyglądają operacje na tak zaimplementowanych zbiorze? Sprawdzenie przynależności jest proste, bo sprowadza się do obliczenia wartości wszystkich funkcji haszujących dla danego elementu i upewnieniu się, że na zwróconych przez nie pozycjach tablicy jest zapisana jedynka. Dodawanie, jak można się domyślić, polega na ustawieniu tychże jedynek. A co wobec tego z usuwaniem elementu?
Otóż usuwania… nie ma :) Jest to zamierzony efekt, konsekwencja założeń które czynią filtr Blooma strukturą probabilistyczną. Dopuszcza ona mianowicie fałszywe pozytywy. Są to przypadki, w których filtr odpowiada pozytywnie na pytanie o przynależność elementu, gdy w rzeczywistości element ten do zbioru nie należy. Jest to jednak jedyny rodzaj dopuszczalnych błędów. Wykluczone są w szczególności sytuacje odwrotne: gdy element jest w zbiorze, ale filtr odpowiada coś przeciwnego (byłby to z kolei fałszywy negatyw). Usuwanie – polegające na wyzerowaniu odpowiednich bitów – mogłoby jednak do dopuścić do takiej sytuacji. Wynika to z faktu, że każdy z bitów w tablicy odpowiada za przechowywanie więcej niż jednego elementu.

Przypuszczam, że wobec powyższych cech filtrów Blooma pojawiają się dwa pytania, z których jedno dotyczy częstotliwości pojawiania się fałszywych pozytywów. Zależy to oczywiście od rozmiaru tablicy (m), liczby funkcji haszujących (k), a także liczby elementów będących aktualnie w zbiorze (n). Ogólny wzór jest, jak widać, raczej nieoczywisty ;)
Dlatego pozwolę sobie raczej przejść do drugiego pytania: o zastosowania. Te są całkiem rozliczne – dotyczą chociażby przyspieszania dostępu do dużych kolekcji danych. Jeśli koszt wczytania danych odpowiadających danemu kluczowi jest spory (bo wymaga np. odczytu z dysku lub sieci), wówczas utrzymywanie w pamięci filtru Blooma może znacząco polepszyć efektywność poprzez szybkie odrzucanie zapytań o nieistniejące klucze. Oczywiście filtr będzie czasami się mylił, ale jego użycie i tak pozwoli ograniczyć liczbę drogich odwołań co najmniej o rząd wielkości.

Przykładową implementację filtru Blooma – wykorzystującą do haszowania generator liczb pseudolosowych – można zobaczyć choćby tutaj.

Tags: , ,
Author: Xion, posted under Programming » 4 comments

C# i zbiory

2010-06-08 16:39

Dłuższy czas temu popełniłem notkę o tym, że w C# (lub szerzej: w .NET) brakuje pewnych struktur danych, które niekiedy bywają przydatne. Jedną z nich jest bardzo prosty rodzaj pojemnika: zbiór.
Zbiory (w programowaniu) to kontenery, które przechowują elementy niepowtarzające się i umożliwiają szybkie sprawdzenie, czy jakaś wartość do danego zbioru należy. ‘Szybkie’ oznacza tu złożoność logarytmiczną (względem rozmiaru pojemnika) lub lepszą. Podstawowa różnica w stosunku do zbiorów matematycznych jest natomiast taka, iż te drugie mogą zawierać elementy różnych rodzajów, podczas struktura danych o tej nazwie przechowuje obiekty jednego typu.

W C++ zbiór implementuje STL-owa klasa std::set. W C# z kolei – jak napisałem na początku – jej odpowiednika nie ma. Takowy trzeba by dopiero napisać, co w przypadku tego języka jest raczej zaskakujące :) Tym niemniej da się to zrobić w miarę prosto, używając do tego… klasy Dictionary. Pomysł polega na tym, żeby całkowicie zignorować tę jej część, która kluczom w słowniku pozwala przypisywać wartości. Zamiast tego interesują nas wyłącznie same klucze jako elementy naszego zbioru. Zarys klasy opartej o tę ideę może wyglądać choćby tak:

  1. public class Set<T> : ICollection<T>, IEnumerable<T>
  2. {
  3.     private Dictionary<T, object> set;
  4.  
  5.     public Set() { set = new Dictionary<T, object>(); }
  6.  
  7.     public void Add(T item) { set.Add(item, null); }
  8.     public void Clear() { set.Clear(); }
  9.     public bool Contains(T item) { return set.ContainsKey(item); }
  10.     public void CopyTo(T[] array, int arrayIndex)
  11.         { set.Keys.CopyTo(array, arrayIndex); }
  12.     public int Count    { get { return set.Count; } }
  13.     public bool IsReadOnly  { get { return false; } }
  14.     public bool Remove(T item) { return set.Remove(item); }
  15.  
  16.     public IEnumerator<T> GetEnumerator()
  17.         { return set.Keys.GetEnumerator(); }
  18.     IEnumerator IEnumerable.GetEnumerator()
  19.         { return (set.Keys as IEnumerable).GetEnumerator(); }
  20. }

Skorzystanie ze słownika (klasy Dictionary) sprawia, że kluczowa operacja Contains (sprawdzenie przynależności) jest bardzo szybka. MSDN podaje, że wydajność odpowiadającej jej operacji słownikowej ContainsKey “zbliża się do O(1)”. Mamy tu też oczywiście niezbędne metody do dodawania i usuwania elementów, a także kilka innych związanych z implementowanymi interfejsami ICollection i IEnumerable, które pozwalają na przykład na iterowanie po zbiorze pętlą foreach.
Można naturalnie jeszcze ulepszyć tę klasę, dodając nowe konstruktory, metody i implementując następne interfejsy (na przykład ISerializable). Nie jest to trudne, bo polega głównie na wywoływaniu odpowiadających metod obiektu Dictionary lub jego kolekcji kluczy. Dopiero operacje matematyczne – jak suma i iloczyn zbiorów – wymagałoby nieco większej ilości kodu.
Ale przecież dla chcącego nic trudnego :)

Tags: , ,
Author: Xion, posted under Programming » 4 comments
 


© 2017 Karol Kuczmarski "Xion". Layout by Urszulka. Powered by WordPress with QuickLaTeX.com.