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.