Czy istnieje algorytm, który jest szybszy niż wyszukiwanie binarne, do wyszukiwania w posortowanych wartościach tablicy?Szybsze niż wyszukiwanie binarne dla uporządkowanej listy
w moim przypadku, mam posortowanej wartości (mogą być dowolne wartości typu) w A tablicy, muszę wrócić n jeżeli wartość Szukałem w zakresie A[n] and A[n+1]
Można zrobić lepiej niż O (log n), jeśli wartości są liczbami całkowitymi, w którym to przypadku najgorszy możliwy czas wykonania, jaki można osiągnąć, w zakresie n, to O (sqrt (log n)). W przeciwnym razie nie ma sposobu na pokonanie O (log n), chyba że istnieją wzorce w sekwencji wejściowej. Istnieją dwa podejścia do pokonania O (log n) w przypadku liczb całkowitych.
Po pierwsze, można użyć Y szybko drzew, które działają poprzez przechowywanie w tabeli mieszania wszystkie prefiksy dla których są przechowywane co najmniej jedną liczbę z tym prefiksem. Umożliwia to wyszukiwanie binarne w celu znalezienia długości najdłuższego zgodnego prefiksu. Dzięki temu możesz znaleźć następcę elementu, którego szukasz w czasie O (log w), gdzie w jest liczbą bitów w słowie. Są jednak pewne szczegóły, które pozwolą na wykonanie tej pracy i wykorzystają tylko przestrzeń liniową, ale nie są one takie złe (patrz link poniżej).
Po drugie, można użyć drzew fuzyjnych, które używają bitowych trików, aby umożliwić wykonywanie porównań W^O (1) w stałej liczbie instrukcji, co daje czas działania O (log n/log w).
optymalny kompromis między tymi dwoma strukturami danych ma miejsce, gdy log w = sqrt (log n), dając czas pracy wyjścia (sqrt (log n)).
Szczegółowe informacje dotyczące powyższego, patrz wykłady 12 i 13 oczywiście Erik Demaine za: http://courses.csail.mit.edu/6.851/spring07/lec.html
Chciałbym dowiedzieć się więcej o drzewach syntezy jądrowej. Być może zechcesz je wytłumaczyć: http://stackoverflow.com/questions/3878320/understanding-fusion-trees – xscott
@xcott Nie jestem pewien, czy nie przesadzasz z optymalizacją, chyba że piszesz profesjonalną bibliotekę liczników. –
tak i nie. Tak, są wyszukiwania, które są średnio szybsze niż wyszukiwanie bisekcji. Ale uważam, że wciąż są one O (lg N), tylko z niższą stałą.
Chcesz zminimalizować czas potrzebny na znalezienie elementu. Zasadniczo pożądane jest stosowanie mniejszej liczby kroków, a jednym ze sposobów podejścia jest maksymalizacja oczekiwanej liczby elementów, które zostaną wyeliminowane na każdym etapie. Przy pomocy bisekcji eliminuje się dokładnie połowę elementów. Możesz zrobić to lepiej, jeśli wiesz coś o rozkładzie pierwiastków. Ale algorytm wybierania elementu partycji jest zwykle bardziej skomplikowany niż wybór punktu środkowego, a ta dodatkowa złożoność może przytłoczyć wszelkie oszczędności czasu, które można uzyskać dzięki mniejszej liczbie kroków.
Naprawdę, w takim przypadku lepiej jest zaatakować efekty drugiego rzędu, takie jak lokalizacja pamięci podręcznej, niż algorytm wyszukiwania. Na przykład, podczas wykonywania wielokrotnego wyszukiwania binarnego, te same kilka elementów (pierwszy, drugi i trzeci kwartyl) są używane BARDZO często, więc umieszczenie ich w pojedynczej linii pamięci podręcznej może znacznie przewyższyć losowy dostęp do listy.
Dzielenie każdego poziomu na powiedzmy 4 lub 8 równych sekcji (zamiast 2) i przeszukiwanie liniowe może być szybsze niż wyszukiwanie bisekcji, ponieważ wyszukiwanie liniowe nie wymaga obliczenia partycji, a także ma mniej zależności danych, które mogą powodować stragany z pamięci podręcznej.
Ale wszystkie z nich nadal należą do O (lg N).
Na jednej liście uporządkowanej nie ma. Ale są o wiele szybsze wyszukiwania; potrzebujesz tylko innej struktury danych niż uporządkowana lista. Hash byłby praktycznie stały w czasie wyszukiwania, kosztem znacznie większej ilości pamięci. Podejście hybrydowe może przyjąć podejście słownika. – tchrist
@tchrist: Problem wymaga znalezienia pary elementów, które ściśle wiążą poszukiwany wpis, który w ogóle nie znajduje się na liście. Hashowanie znajduje tylko dokładne dopasowania. –
Ups, masz rację. Jakoś czytałem tylko pierwsze zdanie, nie drugie. – tchrist
Zawsze można umieścić je w tabeli mieszania, a następnie wyszukiwania będzie O (1). Będzie to jednak wymagało dużej ilości pamięci i jeśli będziesz dodawać elementy, może być konieczne ponowne wygenerowanie tabeli mieszania. Re-bucketing to O (n), ale zostanie zamortyzowany do O (1). Zasadniczo zależy to od tego, czy możesz sobie pozwolić na tę przestrzeń i potencjalne chybienia pamięci podręcznej.
Możliwe, że jego tablica nie zawiera wartości n, ale zawiera dwie wartości o wartości n. Nie jest oczywiste, że hashing ma tutaj zastosowanie. – xscott
Och, tęskniłem za tym.Ale wciąż możesz się najpierw spieszyć i wrócić do wyszukiwania binarnego, jeśli wartość nie znajduje się w zestawie kluczy. Ale to dodatkowa złożoność. Ogólnie rzecz biorąc nie można zrobić nic lepszego niż entropia rozkładu wartości. Jeśli znasz rozkład, możesz użyć drzewa Huffman, aby zdecydować, gdzie podzielisz. – srean
Jeśli wartości na liście są równomiernie rozłożone, można wypróbować podział ważony zamiast podziału binarnego, np. jeśli pożądana wartość jest jedną trzecią drogi od aktualnego dolnego limitu do aktualnej wartości, możesz wypróbować element, który jest również trzecią częścią drogi. Może to źle wpłynąć na listy, w których wartości są gromadzone.
Potrzebna jest jeszcze większa optymalizacja. Nie chcesz wybierać elementu najbliżej miejsca, w którym odgadniesz odpowiedź, chcesz przetestować punkt między odgadywaną lokalizacją a centrum listy, tak aby przy p> .5 wyeliminować więcej niż połowę listy. Dokładny optymalny punkt podziału zależy od rozkładu wartości na liście. –
To, co opisujesz, to właśnie szukanie interpolacji. @Najlepszym sposobem na zaimplementowanie swojej sugestii jest drzewo Huffman – srean
Jedną z możliwości jest potraktowanie jej jak odnalezienia korzenia funkcji. Zasadniczo znalezienia:
a[i] <= i <= a[i + 1]
jest równoznaczne z:
a[i] - i <= 0 <= a[i + 1] - i
Następnie można spróbować czegoś podobnego metody Newtona i tak dalej. Tego rodzaju algorytmy często zbiegają się szybciej niż wyszukiwanie binarne, ale nie wiem, które algorytmy są zbieżne dla wszystkich danych wejściowych.
Metoda Newtona wymaga funkcji różniczkowalnej, więc najpierw trzeba by dopasować interpolujący splajn. Jeśli wartości są jednomodalne, całkiem dobrze się zachowują, może się rozejść i działać zupełnie dziwacznie. – srean
Tak. Możesz użyć liniowego splajnu, a pochodna w dowolnym punkcie to: f '(i) = a [i + 1] - a [i] – xscott
Liniowe splajny są liniowe, więc jego pochodna nie będzie ciągła. Trzeba przejść przynajmniej do kwadratu. To nie jest biggie. To okaże się podobne do [http://en.wikipedia.org/wiki/Interpolation_search] – srean
W poszukiwaniu binarnym podzielić listę na dwie „podlist” i szukać tylko podmenu, które mogą zawierać wartość. W zależności od tego, jak duża jest twoja tablica, możesz zobaczyć przyspieszenie, jeśli podzielisz tablicę na więcej niż dwa spojenia.
Można określić, który obszar tablicy trzeba szukać, utrzymując wskaźnik, że szukać w pierwszej kolejności. Jak w książce telefonicznej dużego miasta, gdzie można zobaczyć z zewnątrz, gdzie trzeba zacząć szukać. (Mam problem z wyrażeniem mojego pomysłu w tekście i nie znalazłem jeszcze angielskiego linku, który wyjaśnia to lepiej).
Przede wszystkim miara przed wykonaniem optymalizacji.
Czy naprawdę potrzebujesz zoptymalizować to wyszukiwanie?
Jeśli tak, to po drugie, myślę o złożoności algorytmicznej pierwszy. Na przykład. możesz użyć drzewa (jak np. std::map, powiedz) zamiast tablicy? Jeśli tak, to zależy od względnej częstotliwości wstawiania/usuwania w porównaniu z wyszukiwaniami, ale założenie posiadania posortowanej tablicy pod ręką wskazuje, że wyszukiwania są częste w porównaniu do zmian zestawu danych, więc byłoby sensowne wykonanie trochę dodatkowej pracy dla wstawiania/usuwania, dzięki czemu każde wyszukiwanie jest szybsze - mianowicie czas logarytmiczny.
Jeśli okaże się, że rzeczywiście czasy wyszukiwania są wąskim gardłem, które wymagają adresowania, i nie, żadna zmiana reprezentacji danych nie jest możliwa, a lista jest krótka, wówczas wyszukiwanie liniowe będzie generalnie szybsze, ponieważ ma mniej pracy na porównanie.
W przeciwnym razie, jeśli lista jest dłuższa i nie jest znany żaden konkretny rozkład wartości, a wartości nie mogą być traktowane jako wartości liczbowe, a zużycie pamięci powinno być stałe (np. Wykluczenie tworzenia tablicy mieszającej) , a następnie wyszukiwanie binarne produkuje 1 bit informacji na porównanie i jest prawdopodobnie najlepsze, co możesz zrobić dla pierwszego wyszukiwania.
Cheers & HTH.
Jeśli masz ogromną liczbę liczb do znalezienia, a przez jakąś rzecz są one również posortowane, możesz to zrobić w O (n + m) gdzie m to liczba liczb do znalezienia. Zasadniczo po prostu typowy algorytm scalania, z niewielkimi modyfikacjami do zapisu, która wartość każdej zaznaczonej cyfry zostanie wstawiona wcześniej, gdyby miała zostać wstawiona do tablicy.
Możesz zawsze kompromis przestrzeń ... i czas innych operacji.Zakładając, że wszystkie twoje elementy mają stały rozmiar p bitów, możesz stworzyć ogromną tablicę, która przechowuje, dla każdej możliwej możliwej wartości, indeks aktualnie zapisanej następnej większej wartości. Ta tablica musi składać się z 2^p * lg (n) bitów, gdzie n to wartości liczbowe przechowywane. Każde wstawienie lub usunięcie to O (2^p), ale zwykle około 2^p/n, ponieważ musisz przejrzeć wszystkie te indeksy.
Ale twoje wyszukiwanie to teraz O (1)!
OK, OK, to naprawdę niepraktyczne. Ale dzielenie danych wejściowych na bloki w podobny sposób może zmniejszyć stałą przed logiem. Możliwie.
Co z następującym algo? nazywa się wyszukiwanie eksponencjalne i jest jedną z odmian wyszukiwania binarnego. http://en.m.wikipedia.org/wiki/Exponential_search
Wyszukiwanie elementu k w posortowanej tablicy A o rozmiarze n. Wyszukiwanie A [2^i] dla i = 0, 1, 2, ... dopóki nie przekroczysz pozycji k w A., a następnie przeszukaj binarnie część lewej (niższej) tablicy niż i.
int exponential_search(int A[], int key)
{
// lower and upper bound for binary search
int lower_bound = 0;
int upper_bound = 1;
// calculate lower and upper bound
while (A[upper_bound] < key) {
lower_bound = upper_bound;
upper_bound = upper_bound * 2;
}
return binary_search(A, key, lower_bound, upper_bound);
}
to algo będzie działał na O (log IDX) gdzie idx jest indeksem k w A. (oba stpes są w logu idx). W najgorszym przypadku, algo jest w O (log idx), jeśli k jest jednym z największych elementów A lub większym niż jakikolwiek element A. Mnożnikowa stała jest większa niż dla wyszukiwania binarnego, ale algo działa szybciej w przypadku bardzo dużych tablice i podczas wyszukiwania danych, które są na początku tablicy.
Chciałbym mieć pojęcie o minimalnym rozmiarze n, w którym to algo staje się lepsze od wyszukiwania binarnego, ale nie wiem.
Należy zauważyć, że mnożenie tutaj może być zastąpione prostą zmianą binarną; to naprawdę tanie. –
Chociaż w ogólnym przypadku nie można zrobić lepiej niż O (log N), można to przynajmniej zoptymalizować, a tym samym znacznie zmniejszyć stałą proporcjonalności przed O (log N).
Jeśli konieczne jest wielokrotne wyszukiwanie w tej samej tablicy, można je wektoryzować za pomocą rozszerzeń SIMD, co dodatkowo obniża koszty obliczeń.
W szczególności, jeśli mamy do czynienia z tablicami liczb zmiennoprzecinkowych, które spełniają określone właściwości, istnieją sposoby na skonstruowanie specjalnego indeksu, który następnie pozwala przeszukiwać tablicę w O (1).
Wszystkie powyższe aspekty są omawiane z wynikami testów w: Cannizzo, 2015, Fast and Vectorizable Alternative to Binary Search in O(1) Applicable to a Wide Domain of Sorted Arrays of Floating Point Numbers Papier pochodzi z kodem źródłowym na github.
Jeśli masz komputer kwantowy, możesz spróbować http://pl.wikipedia.org/wiki/Grover%27s_algorithm :) –
@David: Lista jest posortowana, więc algorytm Grover'a jest gorszy niż wyszukiwanie bisekcji. O (sqrt N)> O (lg N) –
maszyna stanu działała dla mnie na dużych danych, ale złożoność/pamięć dla stanów budynku jest znacznie większa niż sortowanie. – technosaurus