Dlaczego wyszukiwanie binarne jest szybsze niż wyszukiwanie trójskładnikowe?

Przeszukiwanie tablicy elementów przy użyciu wyszukiwania binarnego zajmuje w najgorszym przypadku iteracje ponieważ na każdym kroku zmniejszamy połowę naszej przestrzeni wyszukiwania. Gdybyśmy zamiast tego użyli „wyszukiwania trójskładnikowego”, dwie trzecie naszej przestrzeni wyszukiwania przy każdej iteracji, więc najgorszy przypadek powinien zająć iteracji ... $N$ $\log_2 N$ $\log_3 N < \log_2 N$

Wygląda na to, że wyszukiwanie trójskładnikowe jest szybsze, więc dlaczego używamy wyszukiwania binarnego?

algorithms algorithm-analysis runtime-analysis search-algorithms binary-search Średni kwadrat
źródło

Czy nie można zastosować tego samego rozumowania dotyczącego wyszukiwania czwartorzędu? Lub nawet wyszukiwanie dziesiętne ... lub cokolwiek większego niż 2.

d'alar'cop

przeczytaj o B + Trees

arunmoezhi

Wyszukiwanie liniowe jest często szybsze niż wyszukiwanie binarne w przypadku małych i średnich problemów na nowoczesnym sprzęcie, ponieważ jest spójne z pamięcią podręczną i prawie wszystkie gałęzie są poprawnie prognozowane.

pseudonim

Również 2 * log_3 (N) = log_3 (N ^ 2), jeśli przemawia do Twojej intuicji.

PawelP

Ujmijmy to w intuicyjny sposób. Jeśli korzystanie z wyszukiwania opartego na 3 jest szybsze, ponieważ zmniejsza ono przestrzeń wyszukiwania przy każdej iteracji, to czy nie jest używane wyszukiwanie na podstawie milionów? Ale łatwo można zauważyć, że średnio trzeba wykonać 500 000 kontroli w każdej iteracji, aby ustalić milionowy wycinek zawierający cel. Oczywiste jest, że zmniejszenie przestrzeni wyszukiwania o połowę każdej iteracji i nie więcej, zapewnia niezawodnie najwięcej informacji w jednym kroku.

ErikE

Odpowiedzi:

Jeśli zastosujesz wyszukiwanie binarne, będziesz mieć wiele porównań. Jeśli zastosujesz wyszukiwanie trójskładnikowe, masz wiele porównań, ponieważ na każdym kroku musisz wykonać 2 porównania, aby przeciąć przestrzeń wyszukiwania na trzy części. Teraz, jeśli wykonasz matematykę, możesz zauważyć, że: Ponieważ wiemy, że , faktycznie uzyskujemy więcej porównań z wyszukiwaniem trójstronnym.

\log_{2} (n) + O (1)

$\log_2(n)+O(1)$

2 \cdot \log_{3} (n) + O (1)

$2 \cdot \log_3(n) + O(1)$

2 \cdot \log_{3} (n) + O (1) = 2 \cdot \frac{\log (2)}{\log (3)} \log_{2} (n) + O (1)

$2 \cdot \log_3(n) + O(1) = 2 \cdot \frac{\log(2)}{\log(3)} \log_2(n)+ O(1)$

2 \cdot \frac{\log (2)}{\log (3)} > 1

$2 \cdot \frac{\log(2)}{\log(3)} > 1$

Nawiasem mówiąc: -ary wyszukiwanie może mieć sens w przypadku, gdy porównania są dość kosztowne i można je zrównoleglać, ponieważ wówczas można zastosować komputery równoległe. $n$

Zauważ, że argument można dość łatwo uogólnić na wyszukiwanie -ary. Musisz tylko pokazać, że funkcja rośnie ściśle monotonicznie dla wartości całkowitych . $n$ $f(k) = (k-1) \cdot \frac{\log(2)}{\log(k)}$ $k$

DCTLib
źródło

A LHS jest liniowy, a RHS jest logarytmiczny, więc nie pomoże w żadnym czwartorzędu lub coś więcej .... Ładne wyjaśnienia .... Dzięki

The Mean Square

Ze względu na kompletność: zwróć uwagę, że miara abstrakcyjna, taka jak liczba porównań elementów, może, ale nie musi zdominować rzeczywistego środowiska wykonawczego. W szczególności może być konieczne rozważenie liczby braków w pamięci podręcznej, które możesz napotkać na długie tablice przy każdym wyszukiwaniu. (Tutaj się pokrywają. Po prostu to zauważam, ponieważ OP pyta: „dlaczego jest szybszy?”, I odpowiadając na to abstrakcyjnym miernikiem może być mylące dla niektórych algorytmów.)

Raphael

W wyszukiwaniu trójstronnym 1/3 czasu będziesz potrzebować tylko 1 porównania (wykonaj niższe porównanie: jeśli w dolnej trzeciej nie potrzebujesz drugiego porównania). To sprawia, że trójskładnikowy jest tylko o 5% wolniejszy niż 25% (w tym świecie, w którym zależy nam tylko na porównaniu). Nie jestem pewien, jak uogólnić to na n-ary, chociaż podejrzewam, że to nigdy nie staje się szybsze niż binarne.

Aaron Dufour,

@AaronDufour: Ponieważ można by przeprowadzić wyszukiwanie czwartorzędne, najpierw porównując do środkowego elementu, a następnie ignorując wynik innych porównań, jedynym sposobem, aby wyszukiwanie czwartorzędowe było szybsze, byłoby przeprowadzenie trzech porównań równolegle taniej niż dwóch porównań można wykonać sekwencyjnie.

supercat

@AaronDufour Ale amortyzujesz elementy, które chcesz wyszukać, i nie jest dla mnie jasne, dlaczego to jest w porządku. W najgorszym przypadku oba porównania można wykonać na każdym etapie.

Sasho Nikolov

DCTLib ma rację, ale na chwilę zapomnij o matematyce.

Według twojej logiki, n -ary powinno być najszybsze. Ale jeśli się nad tym zastanowić, n -ary jest dokładnie równe regularnemu wyszukiwaniu iteracyjnemu (tylko iteracja po liście 1 na 1, ale w odwrotnej kolejności). Najpierw wybierz ostatni (lub obok ostatniego) element z listy i porównaj tę wartość z wartością porównania. Następnie usuwasz ten element z listy, a następnie wybierasz ostatni element z nowej listy, który jest tuż przed ostatnią wartością w tablicy. Za każdym razem eliminujesz tylko 1 wartość na raz, dopóki nie znajdziesz swojej wartości.

Zamiast tego powinieneś pomyśleć o tym w ten sposób - jak mogę wyeliminować najwięcej wartości z listy przy każdej iteracji? W wyszukiwaniu binarnym zawsze eliminujesz połowę listy. W trójstronnym wyszukiwaniu istnieje możliwość (faktycznie 33,33% szansy), że możesz wyeliminować 2/3 listy, ale istnieje jeszcze większa szansa (66,66%), że wyeliminujesz tylko 1/3 listy. aby obliczyć O (n), musisz spojrzeć na najgorszy scenariusz, który wynosi 1/3, mniej niż 1/2. W miarę zbliżania się do n staje się jeszcze gorzej.

Wyszukiwanie binarne poprawi nie tylko najgorszy scenariusz, ale także poprawi się średni czas. Patrząc na oczekiwaną wartość (jaką część listy możemy usunąć średnio), używamy tej formuły:

(P_lower) x (część, którą możemy usunąć, jeśli jest niższa) + (P_higher) x (część, którą możemy usunąć, jeśli jest wyższa) = E

W przypadku wyszukiwania binarnego jest to .5x.5 + .5x.5 = .5 (zawsze usuwamy połowę listy). W przypadku wyszukiwań trójskładnikowych wartość ta wynosi .666x.333 + .333x.666 = 0,44, lub na każdym etapie prawdopodobnie usuniemy tylko 44% listy, co czyni ją mniej wydajną niż wyszukiwanie binarne. Wartość ta osiąga wartość szczytową na 1/2 (połowa listy) i zmniejsza się, im bardziej zbliżasz się do n (iteracja wsteczna) i 0 (iteracja zwykła).

Ok, więc skłamałem ... w grę wchodzi trochę matematyki, ale mam nadzieję, że to pomoże!

dberm22
źródło

To świetna odpowiedź.

The_Sympathizer,

Analiza granic pomaga zrozumieć trudną matematykę! n-arytowe wyszukiwanie sekwencyjne ma taki sam koszt wyszukiwania liniowego O (n).

shuva

-2

Uwaga: argument porównania log (N) vs 2 log (N) opiera się na naiwnej interpretacji algorytmu. Gdybym rzeczywiście usiadł i napisał to w zestawie x86, wyniki zostałyby odwrócone. Problemem jest użycie liczb całkowitych w przypadkach testowych w połączeniu z niewystarczająco inteligentnym kompilatorem, który nie może usunąć zbędnych porównań. Ponów próbę z ciągami znaków i odpowiednią funkcją porównania ciągów, a następnie zakoduj ją, aby wywoływała funkcję porównania raz na pętlę, a przekonasz się, że wyszukiwanie potrójne jest szybsze.

Jozuego
źródło

Oczywiście wyszukiwanie trójskładnikowe byłoby szybsze, gdybyś mógł to zrobić za pomocą tylko jednego porównania na iterację. Ale bez względu na ciągi lub liczby całkowite nie możesz.

FrankW

Porównania nie byłyby zbędne, a problem nie ma nic wspólnego z kompilatorem. Aby podzielić przestrzeń wyszukiwania na trzy części, potrzebujesz 2 porównań. W wyszukiwaniu binarnym wystarczy porównać tylko do środkowego elementu, a następnie dowiedzieć się, w której połowie przestrzeni wyszukiwania znalazłby się wynik. W przypadku wyszukiwania trójskładnikowego należy porównać z elementem 1/3 drogi przez lista ORAZ jedna 2/3 listy. Rodzaj danych, które porównujesz lub jakiego języka używasz, nie ma znaczenia. Oczywiście, jeśli przedmiot znajduje się na 1. 3. miejscu, możesz zatrzymać się po 1 porównaniu.

reirab

Na niektórych platformach wyszukiwanie trójskładnikowe może być szybsze, ponieważ pozwala procesorowi na więcej czasu na pobranie operandów z pamięci RAM przed potrzebą ich porównania. Zależy to jednak całkowicie od używanej platformy oraz jej opóźnień i pamięci podręcznych.

jpa

Cholera - zła definicja trójstronnego wyszukiwania.

Jozuego