Czy istnieje jakieś badanie lub teoria łącząca wyszukiwanie binarne i wyszukiwanie interpolacyjne?

Właśnie przeczytałem Czy ten algorytm nadal może być uważany za algorytm wyszukiwania binarnego? i przypomniałem sobie, że kilka lat temu napisałem indeksatora / wyszukaj pliki dziennika, aby znaleźć wpisy dziennika w dużych plikach tekstowych według okna daty / godziny.

Robiąc to, postanowiłem spróbować poszukać interpolacji (nie wiedziałem, że tak to się nazywa, sam natknąłem się na ten pomysł). Następnie z jakiegoś powodu kontynuowałem pomysł na przemian kroków interpolacji z krokami podziału binarnego: w kroku 0 interpolowałem, aby wybrać punkt testowy, a następnie krok 1 wziąłem dokładny punkt środkowy itp.

Następnie przeprowadziłem testy porównawcze systemu za pomocą czystego wyszukiwania interpolacji, czystego wyszukiwania binarnego i mojej próby kombinacji. Podejście naprzemienne było wyraźnym zwycięzcą, zarówno pod względem czasu, jak i liczby testów wymaganych przed znalezieniem zestawu losowo wybranych czasów.

Zainspirowany połączonym pytaniem, właśnie przeprowadziłem szybkie wyszukiwanie „naprzemiennego wyszukiwania interpolacji i wyszukiwania binarnego” i nic nie znalazłem. Próbowałem także „zabezpieczonego wyszukiwania interpolacji”, jak sugerowałem w komentarzu do jednej z odpowiedzi.

Czy natknąłem się na coś znanego? Czy jest jakieś teoretyczne uzasadnienie, że jest ono szybsze w przypadku niektórych rodzajów danych? Pliki dziennika były zwykle duże jak na razie (np. 1–2 GB tekstu i być może 10 milionów wierszy do przeszukiwania), a rozkład dat / godzin w nich był złożony z dużymi skokami aktywności, ogólnymi godzinami szczytu i spokojnymi czasami. W moich testach porównawczych próbowałem znaleźć równomierny rozkład czasów docelowych.

Czy natknąłem się na coś znanego?

$O(log\ log\ n)$$O(log\ n)$

• Wyszukiwanie introspektywne to twoja metoda (iteracja między wyszukiwaniem interpolacyjnym a wyszukiwaniem binarnym). Nie mam dalszych szczegółów.

• Wyszukiwanie interpolacyjno-binarne (IBS) N. Santoro, JB Sidney (1985).

  Ogólna idea jest taka, że ​​wyszukiwanie interpolacji jest przydatne tylko wtedy, gdy przeszukiwana tablica jest większa niż określony próg. Gdy rozważany segment wyszukiwania jest mniejszy niż próg zdefiniowany przez użytkownika, wyszukiwanie binarne jest stosowane bezwarunkowo. Odwrotnie, powyżej tego progu stosowany jest krok wyszukiwania interpolacji, a następnie etap wyszukiwania binarnego.

  Ma to wiele wspólnych punktów z twoim podejściem.

• Wyszukiwanie adaptacyjne (AS) Biagio Bonasera, Emilio Ferrara, Giacomo Fiumara, Francesco Pagano, Alessandro Provetti

  Używając słów autorów:

  [Interpolacja-wyszukiwanie binarne] opracowało podobne rozwiązanie, które łączy (ale nie łączy) interpolację i wyszukiwanie binarne. Chociaż asymptotyczna złożoność jest taka sama, istnieją pewne wyraźne różnice.

  [SKALECZENIE]

  Można więc wykazać, że dla dowolnego wejścia AS nie podejmie więcej podstawowych operacji niż IBS.

  Algorytm może wydać nawet podwójną liczbę operacji niż „proste” wyszukiwanie interpolacyjne w starannym znalezieniu najlepszej połowy segmentu wyszukiwania, co z kolei będzie oznaczało, że potrzeba mniej iteracji (ale masz jeszcze większy narzut) .

Przeplatanie dwóch algorytmów w celu uzyskania najlepszego z obu światów jest znaną techniką, chociaż zwykle określa się je jako uruchamianie ich równolegle i zwracanie odpowiedzi, gdy tylko jedno z nich zakończy się.

Chociaż teoretycznie szybsze, wyszukiwanie interpolacyjne ma dwie wady w porównaniu do wyszukiwania binarnego:

• Ma straszną (liniową) najgorszą wydajność

• Narzut związany z obliczeniem punktu środkowego jest dość duży; iteracja wyszukiwania binarnego jest setki razy szybsza niż wyszukiwanie z interpolacją

Spodziewałbym się, że najbardziej efektywne jest podejście polegające na wyszukiwaniu interpolacji, gdy zasięg jest duży, i przełączeniu się na wyszukiwanie binarne, gdy zasięg staje się mały. Byłoby miło, gdybyś mógł spróbować tego eksperymentu.

$\log n$$\log \log n$$\log n$$\log \log n$

Myślę, że twoje wyniki można wytłumaczyć dwoma zjawiskami:

• Połączenie z wyszukiwaniem binarnym pozwala uniknąć najgorszego zachowania

• Pozytywny efekt przejścia na wyszukiwanie binarne w małym zestawie danych