-
Data: 2016-04-30 23:23:09
Temat: Re: Wyszukiwanie
Od: Wojciech Muła <w...@g...com> szukaj wiadomości tego autora
[ pokaż wszystkie nagłówki ]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.
Następne wpisy z tego wątku
- 02.05.16 08:07 M.M.
- 06.05.16 12:12 Wojciech Muła
- 07.05.16 08:48 M.M.
- 07.05.16 16:10 M.M.
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 <=