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.
źródło
prefetcht0
instrukcjami ) 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 .