On Monday, May 2, 2016 at 8:07:19 AM UTC+2, M.M. wrote:
> > Po pierwsze zapomnij o wyszukiwaniu interpolacyjnym. Dla
> > niejednostajnych rozkładów danych jest wolniejsze niż
> > binarne.
> Zapominam o dosłownym stosowaniu wyszukiwania interpolacyjnego. Ciekawy
> jednak jestem jakby działało 'wyszukiwanie adaptatywne' - tę nazwę
> wymyśliłem w tej chwili. Jaki algorytm mógłby się kryć za wyszukiwaniem
> adaptatywnym? Byłaby to kombinacja wyszukiwania binarnego i interpolacyjnego.
> Wyszukiwanie binarne dzieli zbiór (prawie) na pół (N/2,N/2).
> Interpolacyjne może nawet podzielić zbiór na (N-1,1). Wystarczyłoby dać
> jakieś ograniczenie M z przedziału np. od 0.1 do 0.9. Następnie
> zbiór byłby dzielony na ( N*M , N*(1-M) ). Pozostaje tylko ustalić
> optymalną wartość M. Ilość wyszukiwań dla takiego algorytmu wahałaby się
> pomiędzy Log2N a Log10N.

No tak, tylko wtedy wchodzą obliczenia zmiennoprzecinkowe i może
się okazać, że nie będzie szybciej (w czasie, bo asymptotycznie to może :) ).

Pomyśl może o jakiś drzewach samoorganizujących, które nie przechowywałyby
jednak wszystkich elementów, ale podprzedziały (całe tablice, mówiąc
obrazowo). Takie drzewo byłoby płytkie, więc nie byłoby dużego narzutu
na dereferencje wskaźników. I po dojściu do liścia odpalałbyś już jakieś
wyszukiwanie w tablicy.

> > Ja bym został przy binarnym, raczej w ogólnym przypadku
> > szybciej tego nie zrobisz. Masz przy 1 milionie elementów
> > 20 porównań, naprawdę ciężko to przebić. Ale chętnie
> > bym się mylił w tym miejscu. :)
> W ogólnym pewnie się nie mylisz. Ale jakby z każdym wyszukiwaniem
> coraz lepiej dopasować wartość M, to może dla niektórych przypadków
> dałoby się zejść do 6 wyszukiwań dla miliona?

Twoje pytanie zainspirowało mnie do mieszanego podejścia
wyszukiwania binarnego i liniowego. Jak w binarnym dochodzimy
do wąskiego przedziału (kilka, kilkanaście elementów), to
przechodzimy na liniowe. Liczba odczytów z pamięci będzie taka
raczej taka sama, za to liczba operacji mniejsza. I to daje
dobre efekty, tu masz kod:

https://github.com/WojciechMula/simd-search/blob/mas
ter/binsearch-linear.cpp

w.