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

14

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.

Neil Slater
źródło

Odpowiedzi:

5

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

O(losol losol n)O(losol 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) .

manlio
źródło
6

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.

lognloglognlognloglogn

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

Tom van der Zanden
źródło
3
Napisałeś: „iteracja wyszukiwania binarnego jest setki razy szybsza niż wyszukiwanie z interpolacją”. Należy zauważyć, że w przypadku OP różnica między obliczeniem punktu środkowego w tych dwóch metodach jest zmniejszona przez czas I / O niezbędny do odzyskania wartości punktu środkowego.
liori
@liori: Pierwsze kilka powtórzeń binarnych wyszukiwań tych samych danych może być bardziej przyjazne dla pamięci podręcznej, ponieważ używa się tych samych kilku elementów. Więc ćwierć i może ósme można oczekiwać, że pozostaną gorące w pamięci podręcznej. Rozpoczynanie od binarnego i przełączanie na interpolację po trzech iteracjach może mieć sens, jeśli zakresy są wystarczająco duże. (Lub jeśli możesz wykonać asynchroniczne operacje we / wy i użyć dowolnego wyniku, który pojawi się jako pierwszy).
Peter Cordes,
Również w przypadku wyszukiwania w pamięci brak pamięci podręcznej (opóźnienie ponad 200 cykli) ma kilka razy większe opóźnienie niż nawet 64-bitowy podział na liczby całkowite (32-96 motocykli), na przykład na Intel Haswell . 32-bitowy podział na liczby całkowite jest znacznie szybszy (22-29 motocykli). Przepustowość pamięci głównej jest zasobem współdzielonym dla wszystkich rdzeni, ale podział na liczby całkowite wykorzystuje tylko zasoby zduplikowane na każdym rdzeniu.
Peter Cordes,
2
Jednak opóźnienie pamięci jest znacznie gorsze niż przepustowość pamięci, ponieważ nawet wiele rozproszonych dostępów jest szybszych, jeśli są w locie. Wygrana polega na wstępnym pobraniu (z prefetcht0instrukcjami ) obu możliwości NEXT przed załadowaniem bieżącego punktu środkowego, w celu przeszukania w pamięci nowoczesnego sprzętu x86. Nie możesz tego zrobić, jeśli nie możesz przewidzieć następnego adresu pobierania z wyprzedzeniem. Więc praktyczne szczegóły implementacji może być znaczna, oprócz rozważań teoretycznych .
Peter Cordes,
@liori: Zdecydowanie I / O na punkt środkowy był głównym czynnikiem podczas indeksowania pliku dziennika, ponieważ był on odczytywany na żądanie w celu znalezienia rekordów. Prawdopodobnie istniały więcej niż dwa rzędy wielkości między obliczeniem przesunięcia w pliku a odczytaniem bloku - dlatego decydująca była liczba obliczonych punktów środkowych. Myślę, że jeśli teraz powielę bez pliku dziennika do indeksowania - spróbuję opublikować tutaj - że może nie być mierzalnej różnicy prędkości, ale może istnieć mierzalna „liczba potrzebnych punktów środkowych”.
Neil Slater,