-
Data: 2016-05-06 12:12:11
Temat: Re: Wyszukiwanie
Od: Wojciech Muła <w...@g...com> szukaj wiadomości tego autora
[ pokaż wszystkie nagłówki ]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.
Następne wpisy z tego wątku
Najnowsze wątki z tej grupy
- Do czego nadaje się QDockWidget z bibl. Qt?
- Bibl. Qt jest sztucznie ograniczona - jest nieprzydatna do celów komercyjnych
- Co sciaga kretynow
- AEiC 2024 - Ada-Europe conference - Deadlines Approaching
- Jakie są dobre zasady programowania programów opartych na wtyczkach?
- sprawdzanie słów kluczowych dot. zła
- Re: W czym sie teraz pisze programy??
- Re: (PDF) Surgical Pathology of Non-neoplastic Gastrointestinal Diseases by Lizhi Zhang
- CfC 28th Ada-Europe Int. Conf. Reliable Software Technologies
- Młodzi programiści i tajna policja
- Ada 2022 Language Reference Manual to be Published by Springer
- Press Release - AEiC 2023, Ada-Europe Reliable Softw. Technol.
- Ada-Europe - AEiC 2023 early registration deadline approaching
- Ada-Europe Int.Conf. Reliable Software Technologies, AEiC 2023
- Ile cykli zajmuje mnożenie liczb 64-bitowych?
Najnowsze wątki
- 2024-05-20 Fiat 125p wer. pikup - w PRL moszna było, w III Reczy [pospolitej] nie moszna
- 2024-05-19 Pożar salonu z chińskimi elektrykami
- 2024-05-18 LED
- 2024-05-19 ceny nieruchomości
- 2024-05-18 Szczecin => UX/UI Designer <=
- 2024-05-18 Warszawa => Mid PHP Developer (Laravel) <=
- 2024-05-18 Warszawa => Software .Net Developer <=
- 2024-05-18 Warszawa => Mid/Senior QA Engineer <=
- 2024-05-18 Ulm => Solution Architect (sichere Kommunikation und IoT-Loesungen <=
- 2024-05-18 Katowice => Head of Virtualization Platform Management and Operating S
- 2024-05-18 Warszawa => SAP WM Consultant / Execution <=
- 2024-05-18 Wrocław => Consultant/Implementer Comarch ERP XL <=
- 2024-05-18 Gdańsk => Head of International Freight Forwarding Department <=
- 2024-05-18 Warszawa => Account Manager (Recruitment Services) <=
- 2024-05-18 Łódź => Salesperson - CRM Systems <=