Wyszukiwanie interpolacyjne

Gdy szukasz „Taylor” w książce telefonicznej, nie otwierasz jej w środku: otwierasz ją blisko końca, bo T jest późno w alfabecie. Wyszukiwanie interpolacyjne robi to samo z liczbami. Zgaduje, gdzie powinna być szukana wartość, na podstawie jej wielkości, a przy równomiernie rozłożonych danych to zgadywanie jest zaskakująco trafne.

Posortowany rząd słupków z linią od pierwszego do ostatniego słupka i próbą w miejscu, gdzie wysokość szukanej wartości przecina tę linię
Posortowany rząd słupków z linią od pierwszego do ostatniego słupka i próbą w miejscu, gdzie wysokość szukanej wartości przecina tę linię

Idea

Wyszukiwanie binarne zawsze sprawdza środek, niezależnie od tego, czego szuka. Wyszukiwanie interpolacyjne korzysta z wartości. Jeśli pozostała część listy biegnie od 10 do 100, a szukana wartość to 70, leży ona w dwóch trzecich drogi od pierwszej wartości do ostatniej, więc próba trafia w dwie trzecie długości. Jako wzór: próba jest na miejscu lo + (target − a[lo]) / (a[hi] − a[lo]) × (hi − lo). Po próbie zostaje część po właściwej stronie, dokładnie jak w wyszukiwaniu binarnym, i szacowanie zaczyna się od nowa.

Dwa przykłady

W liście 10, 20, 30, 40, 50, 60, 70, 80, 90, 100 szukanie 70 od razu sprawdza miejsce 7: znalezione w 1 próbie, gdy wyszukiwanie binarne potrzebuje 4. Teraz weź 1, 2, 3, 4, 5, 6, 7, 8, 9, 999 i szukaj 9. Przez 999 każde oszacowanie trafia blisko początku: wyszukiwanie sprawdza 1, 2, 3 i tak dalej, po jednym miejscu, i potrzebuje 9 prób, gdy binarne potrzebuje 3.

Jak szybko działa

Gdy wartości są rozłożone równomiernie albo losowane z rozkładu równomiernego, każda próba zmniejsza pozostałą część z około n do około √n. Daje to średnio około log₂(log₂ n) prób: około 5 nawet dla miliarda wartości, wobec 30 przy wyszukiwaniu binarnym. Gdy wartości są rozłożone bardzo nierówno, próba może usunąć zaledwie jedną wartość, a najgorszy przypadek to n prób, tak źle jak wyszukiwanie liniowe. Każda próba kosztuje też dzielenie, więc w praktyce opłaca się głównie wtedy, gdy próby są kosztowne, na przykład odczyty z dysku.

Historia i warianty

W. W. Peterson opisał wyszukiwanie interpolacyjne w 1957 roku jako sposób wyszukiwania rekordów w pamięci o dostępie swobodnym. Średnią log log n dla równomiernie rozłożonych kluczy udowodnili w 1978 roku Perl, Itai i Avni. Praktyczne wersje chronią się przed złymi danymi, dodając kroki binarne, na przykład wyszukiwanie interpolacyjno-sekwencyjne lub interpolacyjno-binarne, tak aby najgorszy przypadek pozostał bliski log n.

Sprawdź w praktyce

Otwórz aplikację, wybierz wartość w polu Szukaj i naciśnij Krok. Każda próba pokazuje, jak daleko między dwiema wartościami na końcach leży szukana wartość i na które miejsce to wskazuje. Ustaw Rozkład na Równomierny, a większość wyszukiwań kończy się po jednej próbie; ustaw Skośny, a próby pełzną wzdłuż początku listy. Ostatni kafelek pokazuje, ilu kroków potrzebowałoby wyszukiwanie binarne dla tej samej wartości.

Często zadawane pytania

Jaka jest złożoność czasowa wyszukiwania interpolacyjnego?

Średnio O(log log n) dla równomiernie rozłożonych wartości i O(n) w najgorszym przypadku. Potrzebuje O(1) dodatkowej pamięci i posortowanej listy.

Czym różni się wyszukiwanie interpolacyjne od binarnego?

Wyszukiwanie binarne zawsze sprawdza środek tego, co zostało. Wyszukiwanie interpolacyjne sprawdza miejsce, gdzie szukana wartość powinna być, sądząc po wartościach na obu końcach. Na równomiernie rozłożonych wartościach jest dużo lepsze, a na skośnych może być dużo gorsze.

Jakie dane pasują do wyszukiwania interpolacyjnego?

Posortowane klucze liczbowe rozłożone dość równomiernie: kolejne ID z niewielką liczbą luk, znaczniki czasu regularnych zdarzeń lub zahaszowane klucze. Pasuje do danych, w których próba jest kosztowna, a trochę arytmetyki tanie.

Dlaczego aplikacja oferuje różne rozkłady?

Bo rozkład decyduje o tym, jak dobre są oszacowania. Przy równomiernych wartościach wyszukiwanie interpolacyjne wydaje się niemal magiczne, a skośne wartości pokazują jego słabość. Porównanie ich z liczbą kroków wyszukiwania binarnego najlepiej pokazuje, kiedy użyć którego.

Chcesz wypróbować?

Otwórz PictorX w swojej przeglądarce — do uruchomienia nie jest wymagana żadna instalacja ani karta kredytowa.

Wypróbuj wyszukiwanie interpolacyjne