Czy można przyspieszyć tabelę mieszania, używając drzew wyszukiwania binarnego do oddzielnego tworzenia łańcuchów?

Chcę zaimplementować tabelę mieszania przy użyciu drzew wyszukiwania binarnego, aby zmniejszyć złożoność wyszukiwania w procesie oddzielnego łączenia łańcuchów od O (n) (przy użyciu listy połączonej) do O (log n) (przy użyciu BST). Czy można to zrobić, a jeśli tak, to w jaki sposób? Łatwiej byłoby zrozumieć, jeśli rozwiązanie jest krok po kroku, implementacja logiki.

Chcę skrócić czas wyszukiwania w tablicy mieszającej (kompilacja przy użyciu osobnego łączenia), ale jednocześnie nie chcę, aby czas wstawiania był dłuższy. W moim projekcie nie mogę zmienić funkcji skrótu w celu ograniczenia kolizji. Ale ze względu na skalowalność dochodzi do kolizji. Próbuję znaleźć rozwiązanie, aby móc jakoś pracować z najlepszym czasem dostępu i wstawiania w przypadku kolizji ... tj. W celu zarządzania bieżącym stanem rzeczy niż restrukturyzacji całego algorytmu. Jeśli się nie rozłoży, będzie musiał dokonać restrukturyzacji. Jakieś pomysły?

— Aviral
źródło

Tabele skrótów i drzewa wyszukiwania binarnego są różnymi kontenerami. Nie możesz więc robić tego, co sugerujesz (lub popełniasz błąd terminologiczny).

— Basile Starynkevitch

Myślę, że możesz umieścić parę wartości mieszania / wartości w każdym węźle w drzewie ... ale to byłaby albo zła tabela skrótów, albo złe drzewo binarne. Bez jakiegoś wyjaśnienia, dlaczego w ogóle chcesz to zrobić i do czego chcesz, aby wynik końcowy był w stanie, nie jestem pewien, czy to naprawdę możliwe.

— Ixrec

@AK_: Tak, jak powiedziałeś. Chcę poradzić sobie z kolizjami za pomocą drzewa wyszukiwania binarnego. poprawiłem trochę moje pytanie, aby było bardziej przejrzyste.

— Aviral

Zauważ, że przychodzi z karą O (n log n) za każdą wstawkę. Zasadniczo, gdy masz tablicę skrótów, która zaczyna się zapełniać (i masz łańcuchy dłuższe, niż możesz tolerować), odbudowujesz skrót. Jeśli regularnie spotykasz łańcuchy dłuższe niż 3 lub 4, coś jest nie tak.

Istnieje niezliczona liczba odmian tablicy mieszającej, które pozwalają ograniczyć kolizje, adresować i dynamicznie zmieniać rozmiar tabeli. Który pasuje do twoich wymagań, musisz się przyjrzeć. Twoje obecne podejście jest objęte osobnym

Odpowiedzi:

To, o co prosisz, jest możliwe, biorąc pod uwagę twoje ograniczenia.

Analiza

Siłą tabeli haszującej jest jej szybkie wyszukiwanie i szybkość wstawiania. Aby uzyskać tę prędkość, należy porzucić pozory porządku w tabeli: tzn. Wszystkie wpisy są pomieszane. Listę można zaakceptować jako pozycję tabeli, ponieważ podczas gdy przejście to O (n), listy są zwykle krótkie, zakładając, że tabela skrótów jest wystarczająco duża, a obiekty przechowywane w tabeli są mieszane przy użyciu algorytmu haszowania dobrej jakości.

Drzewo wyszukiwania binarnego (BST) ma szybkie wstawianie i wyszukiwanie w O (log ₂ n). Nakłada również ograniczenie na elementy, które przechowuje: musi być jakiś sposób na uporządkowanie elementów. Biorąc pod uwagę dwa elementy A i B przechowywane w drzewie, musi istnieć możliwość ustalenia, czy A występuje przed B lub czy mają równoważną kolejność.

Tabela skrótów nie nakłada takich ograniczeń: elementy tabeli skrótów muszą mieć dwie właściwości. Po pierwsze, musi istnieć sposób ustalenia, czy są one równoważne; po drugie, musi istnieć sposób obliczenia deterministycznego kodu skrótu. Zamówienie nie jest wymagane.

Jeśli elementy tablicy skrótów mają kolejność, możesz użyć BST jako wpisu tablicy skrótów do przechowywania obiektów z tym samym kodem skrótu (kolizje). Jednak ze względu na wyszukiwanie i wstawianie BST z logarytmem O (log ₂ n) oznacza to, że najgorszy przypadek dla całej struktury (tablica skrótu plus BST) jest technicznie lepszy niż użycie listy jako pozycji tabeli. W zależności od implementacji BST będzie wymagało więcej miejsca niż lista, ale prawdopodobnie niewiele więcej.

Należy pamiętać, że zwykle obciążenie ogólne i zachowanie BST nie przynosi niczego w rzeczywistości w sytuacjach rzeczywistych, takich jak segmenty tabeli mieszania, dlatego teoretycznie słaba wydajność listy jest akceptowalna. Innymi słowy, tabela skrótów kompensuje słabość listy, umieszczając mniej elementów na każdej liście (segmencie). Jednak : problem wyraźnie stwierdził, że tablica skrótów nie może się powiększyć, a kolizje występują częściej niż jest to typowe w tabeli skrótów.

Realizacja

Nie zamierzam tu umieszczać kodu, bo szczerze mówiąc, nie jest to naprawdę konieczne, a ty i tak nie podałeś języka.

Chciałbym po prostu skopiować dowolną standardową tabelę skrótów zawartą w standardowej bibliotece języka do nowej klasy, a następnie zmienić typ wiadra tabeli z listy na drzewo. W zależności od języka i standardowej biblioteki może to być bardzo trywialna rzecz.

Zwykle nie zalecałbym takiego kopiowania i wklejania. Jednakże, jest to łatwy sposób, aby uzyskać strukturę danych bitwy przetestowane bardzo szybko.

W kategoriach asymptotycznych użycie drzewa binarnego do obsługi kolizji nie zmienia oczekiwanej wydajności tabeli skrótów, pod warunkiem, że tabela skrótów już wykonała zwykłe sztuczki, aby osiągnąć wydajność amortyzacji O (1). Zmiana rozmiaru tablicy mieszającej w celu zapewnienia dobrej wydajności oznacza, że oczekiwane elementy na wiadro (wielkość drzew binarnych) również będą małe, więc w obu przypadkach otrzymujesz taką samą oczekiwaną amortyzację O (1). Nawet w najgorszym przypadku - bez określonego ograniczenia równoważenia, najgorszym przypadkiem drzewa binarnego jest to, że ostatecznie zachowuje się jak lista połączona.

— Steve314

@ Steve314 Należy pamiętać, że problem polega na tym, że występuje wiele kolizji, więc oczekuje, że wiadro będzie zawierało więcej elementów niż normalnie zawiera tabela mieszania.

Dobra uwaga - np. W przypadku tabeli skrótów o stałej wielkości z nieograniczonymi danymi, wydajność asymptotyczna tabeli skrótów jest taka sama jak wydajność asymptotyczna obsługi kolizji - tabela skrótów zmienia tylko stałe czynniki.

— Steve314

@ Steve314 racja, w zasadzie jeśli tabela skrótów nie może skutecznie ograniczyć liczby elementów w każdym segmencie, wydajność asymptotyczna obniża się do dowolnej struktury subdanych w każdym segmencie. Do mojej odpowiedzi dodałem akapit, aby to wyjaśnić.

Korzystanie z drzewa binarnego do obsługi kolizji w tabeli skrótów jest nie tylko możliwe - zostało już wykonane.

Walter Bright jest najlepiej znany jako wynalazca języka programowania D , ale napisał również wariant ECMAScript o nazwie DMDScript . W przeszłości nagłówek DMDScript (lub być może przodek - wydaje mi się, że pamiętam nazwę DScript) był taki, że jego tabele hasht zwykle przewyższały te w wielu podobnych językach. Powód - obsługa kolizji przy użyciu drzew binarnych.

Nie pamiętam dokładnie, skąd to pochodzi, ale użyte drzewa były naiwnymi drzewami podwójnymi, bez częściowego schematu równowagi (nie AVL, czerwono-czarny itp.), Co ma sens, ponieważ zakładanie, że sama tablica haszująca zmienia rozmiar, gdy robi się przepełniona i nie ma absurdalnie nieprawdopodobnych wskaźników kolizji haszujących, drzewa binarne powinny być zawsze małe. Zasadniczo najgorszy przypadek jest nadal taki sam, jak używanie połączonej listy do obsługi kolizji (z wyjątkiem płacenia ceny dwóch wskaźników na węzeł zamiast jednego), ale przeciętny przypadek zmniejsza liczbę wyszukiwań w każdym segmencie mieszania.

— Steve314
źródło