Wyszukiwanie interpolacyjne a wyszukiwanie binarne

Kiedy powinienem używać wyszukiwania interpolacyjnego zamiast wyszukiwania binarnego?

Na przykład mam posortowany zestaw danych, w jakich sytuacjach użyłbym wyszukiwania binarnego, aby znaleźć element w tym zestawie danych lub w jakiej sytuacji powinienem użyć wyszukiwania interpolacyjnego?

Jakie właściwości zestawu danych byłyby czynnikiem decydującym?

Oczywiście, aby przeprowadzić wyszukiwanie interpolacji, potrzebujesz jakiegoś klucza, dla którego znane jest więcej niż zamawianie - musisz być w stanie wykonać obliczenia na kluczach, aby oszacować prawdopodobną odległość, a nie tylko porównywać klucze, aby określić, który jest większy lub pomniejszy.

Jeśli chodzi o właściwości zestawu danych, dotyczy to głównie jednej właściwości: prawdopodobieństwo, że klucze są racjonalnie równomiernie (lub przynajmniej przewidywalnie) rozmieszczone w całym zakresie możliwości. Bez tego wyszukiwanie interpolacji może być wolniejsze niż wyszukiwanie binarne.

Weźmy na przykład zestaw danych z ciągami małych liter jako kluczami. Załóżmy, że masz klucz zaczynający się od „x”. Wyszukiwanie interpolacyjne wyraźnie wskazuje, że należy rozpocząć wyszukiwanie bardzo blisko końca zestawu. Jeśli jednak większość twoich klawiszy zaczyna się od „z”, a prawie żadna z niczego od „a” choć „y”, ten, którego szukasz, może być bardzo blisko początku zestawu. Może / może zająć znaczną liczbę iteracji, zanim wyszukiwanie zbliży się do początku, w którym znajduje się ciąg zaczynający się od „w”. Każda iteracja usunąłaby z analizy tylko ~ 10% zbioru danych, więc zajęłoby kilka iteracji, zanim zbliżyłaby się do początku, w którym klucze zaczynające się na „w”

Natomiast wyszukiwanie binarne rozpoczyna się na środku, do drugiej ćwiartki, drugiej ósmej i tak dalej. Na jego działanie prawie nie miałoby wpływu pochylenie klawiszy. Każda iteracja usuwa połowę zestawu danych z rozważań, tak jakby klucze były równomiernie rozłożone.

Pośpieszę jednak dodać, że tak naprawdę potrzeba dość wypaczonej dystrybucji, aby wyszukiwanie interpolacji było zauważalnie gorsze niż wyszukiwanie binarne. Może na przykład działać całkiem dobrze, nawet przy dużej liczbie zlokalizowanych klastrów.

Powinienem również wspomnieć, że wyszukiwanie interpolacji nie musi koniecznie używać interpolacji liniowej. Na przykład, jeśli wiadomo, że twoje klucze podążają za pewnym rozkładem nieliniowym (np. Krzywą dzwonową), dość łatwo jest wziąć to pod uwagę w funkcji interpolacji, aby uzyskać wyniki niewiele różniące się od równomiernego rozkładu.

Myślę, że pytanie brzmi, jak łatwo można wymyślić funkcję interpolacji, która faktycznie działa lepiej niż wyszukiwanie binarne.

Z Wikipedii w sprawie wyszukiwania interpolacji:

Wykorzystując notację big-O, wydajność algorytmu interpolacji na zestawie danych o rozmiarze N wynosi O (N); jednak przy założeniu równomiernego rozkładu danych w skali liniowej stosowanej do interpolacji, wydajność można wykazać jako O (log log N).

Praktyczne wyniki wyszukiwania interpolacji zależą od tego, czy zmniejszona liczba sond jest ważona przez bardziej skomplikowane obliczenia potrzebne dla każdej sondy. Może być przydatny do zlokalizowania rekordu w dużym posortowanym pliku na dysku, gdzie każda sonda wymaga wyszukiwania na dysku i jest znacznie wolniejsza niż arytmetyka interpolacji.

Struktury indeksu, takie jak B-drzewa, również zmniejszają liczbę dostępu do dysku i są częściej używane do indeksowania danych na dysku częściowo, ponieważ mogą indeksować wiele rodzajów danych i mogą być aktualizowane online. Mimo to wyszukiwanie interpolacyjne może być przydatne, gdy ktoś jest zmuszony przeszukać określone posortowane, ale nieindeksowane zestawy danych na dysku.

Wyszukiwanie binarne i wyszukiwanie interpolacyjne są uważane za metody wyszukiwania liniowego.

Oboje oczekują, że przeszukiwana lista zostanie posortowana według kolumny, której kluczem jest . To jest bardzo ważne.

Wyszukiwanie binarne działa na ciągi lub liczby, o ile są one przechowywane w posortowanej kolejności. Podstawową ideą wyszukiwania binarnego jest to, że opiera się on na badaniu środkowego elementu. Wyszukiwanie interpolacyjne jest wariantem. Zamiast używać dokładnie środkowego elementu, zgaduje, gdzie jest następny element do porównania z przekazaną wartością. Zobacz odniesienie dostarczone przez odpowiedź JB Kinga lub poniższe w tej odpowiedzi, aby dowiedzieć się, jak algorytm wyszukiwania interpolacji oblicza następną wartość klucza.

„Wyszukiwanie interpolacyjne działa tylko na elementach numerycznych ułożonych w uporządkowanej kolejności tablic o równomiernym rozkładzie (to znaczy odstęp między dowolnymi kolejnymi elementami jest w przybliżeniu stały” (cytat z odnośnika poniżej P 737, również porównanie wydajności różnych metod wyszukiwania liniowego) ).

Google Books - Classic Data Structures 2Nd Ed.