-
X-Received: by 10.157.5.180 with SMTP id 49mr332499otd.10.1462051389363; Sat, 30 Apr
2016 14:23:09 -0700 (PDT)
X-Received: by 10.157.5.180 with SMTP id 49mr332499otd.10.1462051389363; Sat, 30 Apr
2016 14:23:09 -0700 (PDT)
Path: news-archive.icm.edu.pl!news.icm.edu.pl!newsfeed.pionier.net.pl!feeder.erje.net
!2.us.feeder.erje.net!news.glorb.com!11no323700qgt.0!news-out.google.com!k10ni2
08igv.0!nntp.google.com!sq19no853397igc.0!postnews.google.com!glegroupsg2000goo
.googlegroups.com!not-for-mail
Newsgroups: pl.comp.programming
Date: Sat, 30 Apr 2016 14:23:09 -0700 (PDT)
In-Reply-To: <6...@g...com>
Complaints-To: g...@g...com
Injection-Info: glegroupsg2000goo.googlegroups.com; posting-host=37.47.166.9;
posting-account=VFwkXwoAAADdT4-lLKRZrMYkTjizGoyn
NNTP-Posting-Host: 37.47.166.9
References: <6...@g...com>
User-Agent: G2/1.0
MIME-Version: 1.0
Message-ID: <b...@g...com>
Subject: Re: Wyszukiwanie
From: Wojciech Muła <w...@g...com>
Injection-Date: Sat, 30 Apr 2016 21:23:09 +0000
Content-Type: text/plain; charset=ISO-8859-2
Content-Transfer-Encoding: quoted-printable
Xref: news-archive.icm.edu.pl pl.comp.programming:209349
[ ukryj 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-09 Chess
- 2024-05-09 Vitruvian Man - parts 7-11a
- 2024-05-09 Drukara laserowa
- 2024-05-09 Chess
- 2024-05-09 sedzia Szmydt
- 2024-05-09 Chess
- 2024-05-09 [newbie] Jaki multimetr za 2-4 stówy?
- 2024-05-09 Chcą poł. tunelem Europę z Afryką - 27km za 6GEUR
- 2024-05-09 Gorzów Wielkopolski => Konsultant/Wdrożeniowiec Comarch ERP XL <=
- 2024-05-09 Kraków => Senior PHP Developer (Symfony) <=
- 2024-05-09 Vitruvian Man - parts 7-11a
- 2024-05-09 Vitruvian Man - parts 7-11a
- 2024-05-09 Chess
- 2024-05-09 Vitruvian Man - parts 7-11a
- 2024-05-09 szafka sieciowa