On Friday, May 6, 2016 at 12:12:14 PM UTC+2, Wojciech Muła wrote:
> 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.

Muszę dobrze przeanalizować stosunek wyszukiwań do modyfikacji. W ogóle
drzewa wyszukiwań binarnych mają zarówno dobrą złożoność (pesymistyczną)
wstawiania, usuwania i wyszukiwania.

W pewnym momencie na pewno będę miał bardzo mało modyfikacji i bardzo
dużo wyszukiwania. Wtedy drzewko pewnie będzie opłacało się zamienić na
tablicę. Czy będzie się opłacało zastosować 'adaptatywny podział' zamiast
ciągle dzielić na pół - tego nie wiem, może będzie tak jak napisałeś, że
obliczenia zmiennoprzecinkowe pochłoną potencjalny zysk.


>
> > > 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

Myślę że standardowa metoda z biblioteki QT do wyszukiwania binarnego tak
działa, czyli wyszukuje metodą pełnego przeglądu gdy jest mało danych, albo
gdy przedział jest mały. Zastąpiłem pełen przegląd właśnie tą metodą i
na małych zbiorach danych nie zaobserwowałem dużych zmian w czasie
działania programu. Niestety nie mam na razie jednoznacznych pomiarów
czasu, ponieważ program daje inne wyniki po zastosowaniu metody wyszukiwania
binarnego.

Pozdrawiam