Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > pl.comp.programming > #28535

Re: Wyszukiwanie

Show all headers | View raw

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/master/binsearch-linear.cpp

w.

Back to pl.comp.programming | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

Wyszukiwanie "M.M." <mmarszik@gmail.com> - 2016-04-28 13:41 -0700
  Re: Wyszukiwanie Wojciech Muła <wojtek.mula@gmail.com> - 2016-04-30 14:23 -0700
    Re: Wyszukiwanie "M.M." <mmarszik@gmail.com> - 2016-05-01 23:07 -0700
      Re: Wyszukiwanie Wojciech Muła <wojtek.mula@gmail.com> - 2016-05-06 03:12 -0700
        Re: Wyszukiwanie "M.M." <mmarszik@gmail.com> - 2016-05-06 23:48 -0700
        Re: Wyszukiwanie "M.M." <mmarszik@gmail.com> - 2016-05-07 07:10 -0700

csiph-web