Autor Wątek: Bardzo szybki HASH wielu elementów  (Przeczytany 3735 razy)

Offline counterClockWise

  • Użytkownik

# Sierpień 11, 2011, 11:30:01
Nie wiem czy umieściłem temat w dobrym dziale, ale chyba tak, bo szukam teoretycznego mechanizmu na rozwiązanie problemu.

Powiedzmy, że mam N domen pewnych elementów, N może być dowolnie duże i nie jest znane w momencie kompilacji. W ramach swojej domeny elementy mogą mieć przypisane unikalne ID np.
Domena1 = [0,1,2,3,4,5]
Domena2 = [0,1,2,3]
...
DomenaN = [0,1,2,3,4,5,6,7]

Oczywiście element "0" w Domenie1 nie musi i zwykle nie jest tym samym co element "0" w Domenie2.

Teraz chciałbym zdefiniować k-elementowe relacje na elementach z powyższych domen w taki sposób, żeby można było relacje przechowywać w Hashmapie/Słowniku (z pewnych dalszych powodów). Relacja to k-elementowy wektor zawierający ID elementów z poszczególnych domen.
Nie musi to być prosta, pojedyncza Hashmapa, ale jakaś struktura, która na podstawie klucza sprawdzi czy istnieje relacja w czasie bliskim stałemu.

Problemem jest właśnie konstrukcja takiej struktury albo klucza, bo:
a) Oczywiście mogę zrobić stringa w tylu String.Join(" ", ...), który skonwertuje każdą składową wektora do stringa a następnie połączy z jakimś ustalonym znakiem oddzielającym. Dla każdej relacji mogę przechować jakie domeny łączy (w sensie które pozycje odpowiadają którym domenom), więc to wystarczy, aby stworzyć unikalny zapis.
Ale takie rozwiązanie - operowanie na stringach i łączenie ich tyle razy jest skrajnie niewydajne. Sprawdzone empirycznie - operując na dużych zbiorach (na takich jak w praktyce muszę) operacje trwają kilka sekund, a wierzę, że można zejść do czasów rzędu 50-100ms.
 
b) Nie wchodzi w grę także stworzenie jednej liczby tak jak w N-wymiarowych tablicach, bo już np. dla 9 domen, gdzie w każdej jest po 100 elementów liczba bajtów potrzebna do zapisania takiej liczby byłaby ogromna, rzędu 100^9.

Podsumowując - otrzymuję za darmo Hashmapy przechowujące identyfikatory dla domeny.
Potrzebuję stworzyć coś w stylu Hashmapy, która będzie przechowywała wektory takich identyfikatorów. Dodatkowo dana Hashmapa wie która składowa wektora powiązana jest z którą domeną.

Jakieś pomysły? Inspiracje? Naprowadzenia?

Offline Mr. Spam

  • Miłośnik przetworów mięsnych

Offline hashedone

  • Użytkownik

# Sierpień 11, 2011, 11:55:22
Nie da się zrobić nic mniejszego niż połączenie tego w jedną dużą liczbę. To samo robisz robiąc dużego stringa, tyle że marnujesz pamięć (liczby jako string nie są optymalnie zapisywane. Niestety dopóki wystąpienia wszystkich relacji są prawdopodobne nie może być mowy o kompresji bezstratnej, a kompresja stratna w takim przypadku przypisze kilka relacji do jednego hasha - tego nie chcesz. Ew. możesz użyć dowolnej funkcji hashującej i pakować relacje w grupy o takim samym hashu. Żeby sprawdzić czy w mapie istnieje relacja najpierw liczysz jej hash, a potem szukasz jej tylko w śród relacji o tym hashu - jeśli dobrze dobierze się funkcję hashującą (tak że relacje rozłożą się równomiernie po hashach) powinno być znacznie szybciej.

Offline Liosan

  • Redaktor

# Sierpień 11, 2011, 12:23:27
Przychodzi na myśl jeszcze trzymanie tych relacji w drzewie. Jeśli znajdziemy porządek leksykograficzny na parze (domena, ID), to możemy te relacje k-elementowe reprezentować jako uporządkowane ciągi takich par. Takie ciągi można trzymać w drzewie prefiksowym - strukturze używanej m.in. do szybkiego wyszukiwania w tekście. Wtedy można stwierdzić, że jeśli istnieje liść reprezentujący sekwencję odpowiadającą szukanej relacji, to dana relacja istnieje :-)

Jeden problem to szerokość drzewa - pesymistycznie, korzeń mógłby zawierać po jednym dziecku na każdy możliwy początek sekwencji, czyli de facto dla wszystkich możliwych IDów. Jeśli zależy Ci na szybkości operacji na tej strukturze, musiałbyś odpowiednio dobrać strukturę do trzymania wskaźników na dzieci. Może hashmapa, może AssocVector (jak w Loki), może zwykły wektor z wyszukiwaniem binarnym? Drugi problem to jeśli zmieni się układ domen, to może być potrzebna przebudowa całego drzewa, a to będzie boleć. Bardzo.

Byłoby łatwiej ocenić przydatność tego rozwiązania, gdybyś podał spodziewane N, liczbe IDów w domenie, k, to czy k jest stałe, czy zmienia się układ domen, czy mogą dochodzić nowe, itp :)

Inny pomysł który warto tutaj rozważyć to Bloom Filter - nie rozwiąże problemu, ale małym kosztem może znacznie przyspieszyć odpytywanie.

Liosan

Offline counterClockWise

  • Użytkownik

# Sierpień 11, 2011, 14:12:18
Wielkie dzięki za inspirujące pomysły. Chciałbym jakoś ogólniej przedstawić problem, ale jest tak duży, że ma sens omówienie tylko tego podproblemu, którego dotyczy temat.

Byłoby łatwiej ocenić przydatność tego rozwiązania, gdybyś podał spodziewane N, liczbe IDów w domenie, k, to czy k jest stałe, czy zmienia się układ domen, czy mogą dochodzić nowe, itp :)

Ok, to postaram się trochę nakreślić :)

Przede wszystkim - chciałbym przygotować możliwie wydajne struktury do rozwiązania problemu.
1. Na etapie kompilacji wiem tylko że istnieją relacje i co to jest
2. Raz na początku dostaję opis (np. z pliku), z którego mogę jednoznacznie zdefiniować już konkretne relacje operujące na domenach
3. W trakcie działania programu, ponieważ skład domen może się zmieniać muszę ewaluować relacje, które w bieżącym momencie są prawdziwe.

Punkt 1 i 2 mogą wykonywać się bardzo długo. Chciałbym jak najwięcej przygotować tam żeby ewaluacja w punkcie 3. była możliwie szybka.
Chcę utworzyć procedurę ewaluowania relacji spełnionych w danym momencie.

Jak to wygląda (w uproszczeniu):

Dostaję pewne domeny podstawowe zawierające unikalne elementy. Można wprowadzić porządek. Spodziewana ilość domen podstawowych to około 10. Spodziewana maksymalna ilość elementów w każdej domenie to od 2 do 300. Średnio raczej około 30. Bieżący "skład" domeny - czyli które elementy w danym momencie występują zmienia się w czasie.

Mam relacje I typu, które łączą ze sobą domeny w wektor. Może być ich sporo np. 500. Wektor wygląda np tak:
R1 (I typ)= [D1, D2, D3-"5", D2]

W pierwszym indeksie jest bieżący skład domeny D1
W drugim indeksie jest bieżący skład domeny D2
W trzecim indeksie jest element ID=5 z Domeny D3.

Mam relacje II typu, które łączą ze sobą relacje I typu mówiąc, które ich podwektory R muszą się zgadzać np.

R (II typ) = R1 ^ R2, gdzie R1[0] = R2[1], R1[0,1] = R2[1,2]

R1[0] = R2[1] oznacza przefiltrowanie tych wystąpień relacji R1 i R2 w których elementy z 0 indeksu są równe elementom z relacji R2 znajdujących się na indeksie 1.

R1[0,1] = R2[1,2] oznacza przefiltrowanie tych wystąpień relacji R1 i R2, w których elementy mają aż dwie odpowiednie domeny wspólne.

Taka część wspólna powoduje utworzenie nowej relacji R, która może zawierać dowolne (znane dopiero po wczytaniu schematu) wybrane przez siebie przefiltrowane domeny.

Bez wchodzenia w szczegóły:
- wychodzimy od domen podstawowych
- przeróżne relacje przekształcają te domeny - ograniczają, powiększają
- masa operacji w runtime wymaga znalezienia części wspólnych pewnych wektorów z dwóch zbiorów - trochę przypomina to wyrażenia regularne. np.

Zbiór1: S1 => (x1,x2,x3,x4) = { (1,2,3,4), (1,3,4,5), (5,1,3,2)}
Zbiór2: S2 =>(y1,y2,y3) = { (3,2,1), (4,3,2)}

i w runtime musimy np. znaleźć takie elementy zawarte w zbiorach 1 i 2, w których np.
(S1.x1 == S2.y1 && S1.x2 == S2.y2 && S1.X3 = "5")

Wszelkie "zapytania" znane są na etapie 2 (w runtime, ale raz na początku) natomiast wszelkie wystąpienia domen podstawowych, a co za tym idzie każdych kolejnych, które od nich zależą zmieniają się w czasie i nie są znane.

Chciałbym hashować ze sobą takie podwektory, o których może paść zapytanie - tzn. z relacji wynika, że trzeba sprawdzać ich obecność, zwłaszcza, że podstawowe domeny otrzymuje już w postaci HashSetów dla pojedynczych elementów - czy istnieje czy nie.

Problem mam rozwiązany, w sensie rozwiązanie jest poprawne, ale niedostatecznie wydajne - bo za każdym razem jak mam przeciąć ze sobą dwie relacje to robię n^2 przeszukiwanie (dla każdego elementu z jednej sprawdzam czy istnieje taki, w drugiej, który zawiera szukany podwektor). W ten sposób buduję zbiory elementów spełniających warunki. Jest za wolno. Myślę, że można to zrobić sprytniej.







« Ostatnia zmiana: Sierpień 11, 2011, 14:17:51 wysłana przez counterClockWise »

Offline Krzysiek K.

  • Redaktor
    • DevKK.net

# Sierpień 11, 2011, 14:21:47
A mógłbyś napisac konkretnie do czego to ma służyć? Bo wątpię, żeby końcowy użytkownik operował na pojęciach "domena" i "relacja".

Offline owyn

  • Użytkownik

# Sierpień 11, 2011, 14:46:15
Powiedzmy, że masz wektor vec = (v1, v2, ..., vn), gdzie wartości v1, ..., vn można łatwo zamienić na wartość liczbową. Hasha z wektora można policzyć np. tak:
t = 17;
c = 37;
for (v in vec) {
  t = t * c + toInt(v);
}
return t;

Offline Krzysiek K.

  • Redaktor
    • DevKK.net

# Sierpień 11, 2011, 14:55:14
@owyn: Proponował bym użycie większej wartości 'c', bo przy tak małej łatwo o kolizje. Ja z reguły wklepuję po prostu przypadkową 8-cyfrową liczbę nieparzystą.

Offline counterClockWise

  • Użytkownik

# Sierpień 11, 2011, 16:08:44
A mógłbyś napisac konkretnie do czego to ma służyć? Bo wątpię, żeby końcowy użytkownik operował na pojęciach "domena" i "relacja".

Interpreter reguł logicznych zapisanych w określonym formacie. Coś podobnego do Prologa, ale to nie Prolog. Można przeprowadzić formalną konwersję do Prologa, ale przez to traci się wykorzystanie pewnych specyficznych założeń formatu, dzięki którym można mocno optymalizować.

Moje obecne rozwiązanie osiąga statystycznie wydajność taką jak Prolog (który jest znacznie bardziej ogólny), a czasami trochę większą. Zrobiłem dużo specyficznych-pod-problem optymalizacji, ale chyba korzystam z wielu innych niewydajnych mechanizmów - profiler pokazał mi, że wąskim gardłem jest iterowanie po listach. Intuicja podpowiada mi, że to powinno działać nawet do 10x szybciej. Zbyt wiele razy szukam pasujących do siebie elementów w dwóch wektorach, zamiast operować na hashach albo innych sprytnych trickach. Tablicowanie nie wchodzi w grę, bo ilość kombinacji rośnie... kombinatorycznie :(

Wydajność jest tutaj sprawą absolutnie kluczową, inaczej już bym to zostawił.


Offline Krzysiek K.

  • Redaktor
    • DevKK.net

# Sierpień 11, 2011, 16:45:34
Listy? Zmiłuj się. Toż to najbardziej niewydajne stworzenie, jakie człowiek wymyślił. Gdyby cache Twojego kompa umiał mówić, to nie chciałbyś tego słuchać. :)

Cytuj
Zbyt wiele razy szukam pasujących do siebie elementów w dwóch wektorach, zamiast operować na hashach albo innych sprytnych trickach.
Jeżeli tych elementów jest jak mówiłeś rzędu wielkości 500, to ja bym zmienił listy w tablice bitów. Żeby w dwóch tablicach bitów znaleźć wspólny element wystarczą opecacje bitowe, dzięki czemu nie tylko cache się cieszy, ale masz "zrównoleglenie" obliczeń x32 (bo tyle bitów ma int).

Offline Kos

  • Użytkownik
    • kos.gd

# Sierpień 11, 2011, 16:52:43
A rozważałeś użycie bloom filtera lub czegoś w tym stylu?

(sugestia w ciemno, trochę jak "have you tried logarithms" z xkcd, ale a nuż pomoże :))

Offline counterClockWise

  • Użytkownik

# Sierpień 11, 2011, 17:07:08
Listy? Zmiłuj się. Toż to najbardziej niewydajne stworzenie, jakie człowiek wymyślił. Gdyby cache Twojego kompa umiał mówić, to nie chciałbyś tego słuchać. :)

Cytuj
Zbyt wiele razy szukam pasujących do siebie elementów w dwóch wektorach, zamiast operować na hashach albo innych sprytnych trickach.
Jeżeli tych elementów jest jak mówiłeś rzędu wielkości 500, to ja bym zmienił listy w tablice bitów. Żeby w dwóch tablicach bitów znaleźć wspólny element wystarczą opecacje bitowe, dzięki czemu nie tylko cache się cieszy, ale masz "zrównoleglenie" obliczeń x32 (bo tyle bitów ma int).

Tylko to nie jest takie proste, bo dopóki mam podstawowe elementy, unikam list. Problem się pojawia, gdy dynamicznie stworzone są kolekcje zawierające wektory, gdzie każda składowa to podzbiór tych elementów. Takie wektory ciężko sensownie unikalnie nazwać albo przypisać adres w tablicy, żeby potem w innym miejscu umieć je pobrać na podstawie spełnialności z innym wektorem (bez przeszukiwania).

Teoretyczna maksymalna liczba w ogóle wszystkich możliwych elementów jest liczbą przeogromną, bo w grę wchodzą dowolne permutacje i kombinacje z powtórzeniami. No cóż, walczę dalej.

Kos: Tak, ale bloom filter w przypadku jednej z odpowiedzi TAK/NIE może się mylić, prawda? Potrzebuję formalnej dokładności zarówno w pozytywnej jak i negatywnej odpowiedzi.

Offline Xender

  • Użytkownik

# Sierpień 11, 2011, 17:22:41
Co do filtru blooma: można go użyć, aby wykluczyć dopasowanie, a jeśli wynik będzie pozytywny użyć dokładnego testu.

Offline kabum

  • Użytkownik

# Sierpień 11, 2011, 20:46:41
a ja w php robie tak :
$slownik[md5(serialize($wektor))]=$wektor;:P

Offline Xirdus

  • Redaktor

# Sierpień 11, 2011, 20:56:13
php
Zauważ, że autorowi chodzi o szybki sposób :P

Offline hashedone

  • Użytkownik

# Sierpień 11, 2011, 21:07:33
Poza tym przy tej ilości wektorów sumy md5 będą się powtarzać a to może skutecznie wysypać program (a właściwie prawdopodobnie bardzo szybko wysypie).