szybkie b-drzewa

0

Mamy dużą listę haseł, może to być np. słownik z definicjami, albo i jakieś zdania,
np. baza przysłów, sentencji, czy dowolnych stringów;
100 a nawet i 500 tyś. pozycji.

Jest to zapisane w postaci zwykłego tekstu, każda linia to jeden rekord, np.:

krowa<tab>zwierzę domowe<tab>inne dane.
Aleksander Wielki<tab>starożytny władca.
pingwin<tab>ptak w smokingu.

itd.

Teraz chcę to posortować, w celu np. wyszukania podanego przez użytkownika hasła, albo dodania nowych pozycji,
czy też scalić dwa takie zbiory, i bez powtórek.

I jak to zrobić? Ważne żeby to było maksymalnie szybkie.

Wymyśliłem że B-drzewo będzie tu najlepsze, i chodzi mi o proste algorytmy dla takiego drzewa;
i jakoś nie widzę tego w sieci; są jakieś kody, ale to jakieś potwory - kod strasznie długi, nieczytelny, zero optymalizacji, itd.

Wystarczą dwie proste funkcje: szukania i dodawania, ewentualnie jeszcze usuwania z B-drzewa.

0

Najlepiej użyj baz danych.

0
_13th_Dragon napisał(a):

Najlepiej użyj baz danych.

Zbyt wolne bo/i rozrzutne pamięciowo.
Standardowe bazy nie są optymalizowane pod względem szybkości, lecz wielu innych kryteriów, związanych z bezpieczeństwem zwykle, które mnie tu nie interesuje wcale - dane mam zabezpieczone... w stu kopiach.

0

W takim razie zainteresuj się tym: http://pl.wikipedia.org/wiki/Skompresowane_drzewo_trie

0
_13th_Dragon napisał(a):

W takim razie zainteresuj się tym: http://pl.wikipedia.org/wiki/Skompresowane_drzewo_trie

Raczej mało użyteczne dla tak dużych zbirów.

Jak mówiłem, interesuje mnie funkcja szukania/dodawania do B-drzewa,
i nie do B+drzewa, bo tu są trzymane kopie kluczy, czyli z 200% większy nakład pamięci, co automatycznie spowolni działanie, pewnie z 5 razy.

Poza tym klucz ma być zmiennej długości, np. od 2 do 200, bo w przypadku zdań może tak wyjść.
Znaczy są przypadki długich kluczy, ale średni jest nieduży - z 20 znaków zaledwie,
zatem ustawienie długości klucza na stałe spowodowałoby przynajmniej aż 10-cio krotne użycie pamięci,
co nie stanowi istotnego problemu w standardowych bazach, ale to spowalnia działanie z 20 razy, albo i lepiej!

Klucz dł. 200 i razy 100 K = 20 mega, czyli taki rozmiar danych.
Zatem ze zmiennym wyjdzie tylko około 1 mega, co cache może pomieścić, więc nawet i 100 razy szybciej pójdzie!

0

Nie zrozumiałeś zasadę, przeczytaj jeszcze raz.
Przy dość rozbudowanym drzewie sumaryczny rozmiar pamięci zajmowanym przez drzewo będzie mniejszy lub znacznie mniejszy niż suma rozmiarów kluczy.
To przy B-Drzewie będziesz mieć średnio 200% nakład pamięci.

0

Ale co tu niby ma cache do rzeczy? o_O W jaki niby sposób miałby ci ten cache pomóc? Szczególnie skoro chciałbyś tam trzymać klucze. Mógłbyś trochę rozwinąć jak ty to widzisz?

Tak czy siak, jak dla mnie tablica hashująca pewnie byłaby dla ciebie znacznie lepsza, szczególnie skoro masz potencjalnie bardzo długie klucze.

0
_13th_Dragon napisał(a):

Nie zrozumiałeś zasadę, przeczytaj jeszcze raz.
Przy dość rozbudowanym drzewie sumaryczny rozmiar pamięci zajmowanym przez drzewo będzie mniejszy lub znacznie mniejszy niż suma rozmiarów kluczy.
To przy B-Drzewie będziesz mieć średnio 200% nakład pamięci.

Nawet gdyby tak było B-drzewo i tak będzie szybsze, bo to jest zwarte pamięciowo - duże bloki.
A w tych Patrycjach chyba potrzeba milionów wskaźników, czyli rozdrobnienie ekstremalne.

Kiedyś nawet próbowałem to implementować i tam wychodzą strasznie ilości pamięci... chyba lekko z 1000% tego co te stringi-klucze zajmują.

0
Shalom napisał(a):

Ale co tu niby ma cache do rzeczy? o_O W jaki niby sposób miałby ci ten cache pomóc? Szczególnie skoro chciałbyś tam trzymać klucze. Mógłbyś trochę rozwinąć jak ty to widzisz?

Masz duże bloki, a podczas operacji na drzewie chodzisz tylko kilku z nich, więc to musi być szybkie,
i w sumie całość nie musi siedzieć stale w cache, bo po wejściu w stronę zostanie ona tam i tak zaraz załadowana,
zatem dalsze operacje na stronie są już szybsze, a tych operacji jest sporo - szukanie, wsadzanie, kopiowanie, itp.

Shalom napisał(a):

Tak czy siak, jak dla mnie tablica hashująca pewnie byłaby dla ciebie znacznie lepsza, szczególnie skoro masz potencjalnie bardzo długie klucze.

Nie wiem. Ale samo liczenie tych hashów byłoby kosztowne, bo musisz każdy cały klucz przerobić, a podczas porównywania stringów zwykle wystarcza porównać kilka pierwszych liter, co też można sobie przyspieszyć np. traktując ten tekst jako tablice int32.

0

Kiepskiemu tancerzowi jaja wadzą, w mojej realizacji zajmowało to około 30% objętości kluczy. - _13th_Dragon 2014-12-27 17:47

Możemy to porównać co będzie szybsze:
ja zrobię to na B-drzewie, a Ty te patrycje i odpalimy to na tych samych danych.

1 użytkowników online, w tym zalogowanych: 0, gości: 1