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