Jak powinien wyglądać dobry algorytm do wyszukiwania w posortowanym
ciągu? Można wyszukiwać binarnie lub metodą pełnego przeglądu.
Można także wyszukiwać interpolacyjnie. Każda z metod nadaje się
tylko do określonego przypadku. Metoda pełnego przeglądu jest
bardzo skuteczna dla małych ciągów. Interpolacyjne jest dobre
dla ogromnych ciągów dających się dobrze aproksymować jakąś
wzajemnie jednoznaczną funkcją. Wyszukiwanie binarne to stabilna
metoda, nawet pesymistycznie działa w czasie LogN, jednak
ma narzut liniowy. Zresztą interpolacyjne ma jeszcze większy
narzut.

Jak powinno wyglądać adaptatywne wyszukiwanie?

Czy może wyglądać tak: Pierwszy raz szukamy binarnie i
zapamiętujemy przybliżony czas. Potem szukamy metodą
pełnego przeglądu, jeśli czas jest większy, to
przerywamy i wyszukujemy binarnie. Potem z... nie
wiem ile... z 20 razy wyszukujemy binarnie, bo
działało najszybciej. Potem znowu jakaś próba... może z
wyszukiwaniem interpolacyjnym. Jeśli czas przekroczy
binarne, to przerywamy i znowu z 20 razy binarnie? Aha,
dane po każdym wyszukiwaniu mogą się zmienić co do
ilości i jakości.

Czy wystarczy zrobić to chamsko? Typu jeśli ilość danych
większa niż N to binarnie, a poza tym pełen przegląd?

Druga sprawa, czy interpoluje się tylko liniowo, czy
warto próbować jeszcze jakąś inną funkcją?

Pozdrawiam

do góry

On Thursday, April 28, 2016 at 10:41:03 PM UTC+2, M.M. wrote:
> Jak powinien wyglądać dobry algorytm do wyszukiwania w posortowanym
> ciągu? Można wyszukiwać binarnie lub metodą pełnego przeglądu.
> Można także wyszukiwać interpolacyjnie. Każda z metod nadaje się
> tylko do określonego przypadku. Metoda pełnego przeglądu jest
> bardzo skuteczna dla małych ciągów. Interpolacyjne jest dobre
> dla ogromnych ciągów dających się dobrze aproksymować jakąś
> wzajemnie jednoznaczną funkcją. Wyszukiwanie binarne to stabilna
> metoda, nawet pesymistycznie działa w czasie LogN, jednak
> ma narzut liniowy. Zresztą interpolacyjne ma jeszcze większy
> narzut.
>
> Jak powinno wyglądać adaptatywne wyszukiwanie?
>
> Czy może wyglądać tak: Pierwszy raz szukamy binarnie i
> zapamiętujemy przybliżony czas. Potem szukamy metodą
> pełnego przeglądu, jeśli czas jest większy, to
> przerywamy i wyszukujemy binarnie. Potem z... nie
> wiem ile... z 20 razy wyszukujemy binarnie, bo
> działało najszybciej. Potem znowu jakaś próba... może z
> wyszukiwaniem interpolacyjnym. Jeśli czas przekroczy
> binarne, to przerywamy i znowu z 20 razy binarnie? Aha,
> dane po każdym wyszukiwaniu mogą się zmienić co do
> ilości i jakości.
>
> Czy wystarczy zrobić to chamsko? Typu jeśli ilość danych
> większa niż N to binarnie, a poza tym pełen przegląd?
>
> Druga sprawa, czy interpoluje się tylko liniowo, czy
> warto próbować jeszcze jakąś inną funkcją?

Po pierwsze zapomnij o wyszukiwaniu interpolacyjnym. Dla
niejednostajnych rozkładów danych jest wolniejsze niż
binarne.

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. :)

Chociaż pytanie, co porównujesz? Jak masz typy proste (int, float),
gdzie porównania mapują się na instrukcje procesora, możesz
spróbować instrukcji SIMD. Przy czy to już dla naprawdę dużych
danych daje jakieś mierzalne efekty -- możesz zerknąć na mój
artykuł. Pobawiłem się tym, ale jeszcze nie stosowałem w praktyce:
http://0x80.pl/articles/simd-search.html

Patrząc z trochę innej strony: czy skoro dane w Twoim
zastosowaniu się zmieniają nawet co jedno wyszukanie, to
czy w ogóle sens je sortować? Może szybciej wyjdzie pominięcie
sortowania i szukanie liniowo za każdym razem.

w.

do góry

On Saturday, April 30, 2016 at 11:23:10 PM UTC+2, Wojciech Muła wrote:
> On Thursday, April 28, 2016 at 10:41:03 PM UTC+2, M.M. wrote:
> > Jak powinien wyglądać dobry algorytm do wyszukiwania w posortowanym
> > ciągu? Można wyszukiwać binarnie lub metodą pełnego przeglądu.
> > Można także wyszukiwać interpolacyjnie. Każda z metod nadaje się
> > tylko do określonego przypadku. Metoda pełnego przeglądu jest
> > bardzo skuteczna dla małych ciągów. Interpolacyjne jest dobre
> > dla ogromnych ciągów dających się dobrze aproksymować jakąś
> > wzajemnie jednoznaczną funkcją. Wyszukiwanie binarne to stabilna
> > metoda, nawet pesymistycznie działa w czasie LogN, jednak
> > ma narzut liniowy. Zresztą interpolacyjne ma jeszcze większy
> > narzut.
> >
> > Jak powinno wyglądać adaptatywne wyszukiwanie?
> >
> > Czy może wyglądać tak: Pierwszy raz szukamy binarnie i
> > zapamiętujemy przybliżony czas. Potem szukamy metodą
> > pełnego przeglądu, jeśli czas jest większy, to
> > przerywamy i wyszukujemy binarnie. Potem z... nie
> > wiem ile... z 20 razy wyszukujemy binarnie, bo
> > działało najszybciej. Potem znowu jakaś próba... może z
> > wyszukiwaniem interpolacyjnym. Jeśli czas przekroczy
> > binarne, to przerywamy i znowu z 20 razy binarnie? Aha,
> > dane po każdym wyszukiwaniu mogą się zmienić co do
> > ilości i jakości.
> >
> > Czy wystarczy zrobić to chamsko? Typu jeśli ilość danych
> > większa niż N to binarnie, a poza tym pełen przegląd?
> >
> > Druga sprawa, czy interpoluje się tylko liniowo, czy
> > warto próbować jeszcze jakąś inną funkcją?
>

Dzięki za odpowiedź, dzięki za artykuł. Podoba mi się pomysł z
wykorzystaniem długich rejestrów.

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





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



> Chociaż pytanie, co porównujesz? Jak masz typy proste (int, float),
> gdzie porównania mapują się na instrukcje procesora, możesz
> spróbować instrukcji SIMD. Przy czy to już dla naprawdę dużych
> danych daje jakieś mierzalne efekty -- możesz zerknąć na mój
> artykuł. Pobawiłem się tym, ale jeszcze nie stosowałem w praktyce:
> http://0x80.pl/articles/simd-search.html
Widać że daje. Dziękuję za artykuł. Podoba mi się pomysł z
wykorzystaniem SIMD.


> Patrząc z trochę innej strony: czy skoro dane w Twoim
> zastosowaniu się zmieniają nawet co jedno wyszukanie, to
> czy w ogóle sens je sortować? Może szybciej wyjdzie pominięcie
> sortowania i szukanie liniowo za każdym razem.
W moim zastosowaniu będą (chyba) trzy generalne przypadki użycia. W
jednym dane często będą się zmieniały, w drugim rzadko, w trzecim w
ogóle nie będą się zmieniały i wyszukiwanie może być 'gorącym punktem'.
Dlatego zamarzyło mi się 'wyszukiwanie idealne'. Co rozumiem przez
wyszukiwanie idealne? Ano coś takiego, że programista sam definiuje,
jaki procent czasu procesora ma być przeznaczony na auto-tuning.
Pewnie napisanie powyższego algorytmu byłoby bardzo trudne, albo
niemożliwe. Natomiast jest nadzieja, że opłaci się automatyczny
dobór parametru M. Jak dobierać te M? Może tak, że jeśli wyszukiwana
wartość znajduje się w większym przedziale, to M lekko zmieniamy w
kierunku wartości 0.5, a jeśli w mniejszym przedziale, to M zmieniamy
w kierunku 0.1 albo nawet 0.01. Np. raz modyfikujemy tak:
M = (M * 0.999) + 0.5 * 0.001
drugi raz tak:
M = (M * 0.999) + 0.01 * 0.001

Jeśli szukana wartość częściej będzie w mniejszym zbiorze, to M po
kilku tysiącach wyszukiwań osiągnie wartość 0.01, w przeciwnym razie
będzie oscylowało w okolicach 0.5.

Może się mylę, ale dostęp do danych w których wyszukujemy jest powolny, bo
to strzały w niebuforowaną pamięć. Wartość M zawsze procesor
będzie miał pod ręką, może nawet w rejestrze, więc operowanie na M nie
powinno dawać dużego narzutu liniowego.


Pozdrawiam

do góry

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.

do góry

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

do góry

On Friday, May 6, 2016 at 12:12:14 PM UTC+2, Wojciech Muła wrote:

> Twoje pytanie zainspirowało mnie do mieszanego podejścia
> wyszukiwania binarnego i liniowego.

Napisałem na szybko trochę niechlujnego kodu i zrobiłem
kilka pomiarów. Wygląda na to, że powyższe dwa podejścia
jednak opłaca się jeszcze mieszać z interpolacyjnym.
Rewelacyjnego przyspieszenia nie widać, ale z 20-30%
można przyspieszyć. Pozostaje kwestia dobierania parametrów
do danych i do maszyny :)

Pozdrawiam

do góry