-
X-Received: by 10.182.117.40 with SMTP id kb8mr231448obb.7.1461876062358; Thu, 28 Apr
2016 13:41:02 -0700 (PDT)
X-Received: by 10.182.117.40 with SMTP id kb8mr231448obb.7.1461876062358; Thu, 28 Apr
2016 13:41:02 -0700 (PDT)
Path: news-archive.icm.edu.pl!agh.edu.pl!news.agh.edu.pl!newsfeed2.atman.pl!newsfeed.
atman.pl!goblin3!goblin1!goblin.stu.neva.ru!sq19no2132270igc.0!news-out.google.
com!uv8ni218igb.0!nntp.google.com!i5no784232ige.0!postnews.google.com!glegroups
g2000goo.googlegroups.com!not-for-mail
Newsgroups: pl.comp.programming
Date: Thu, 28 Apr 2016 13:41:01 -0700 (PDT)
Complaints-To: g...@g...com
Injection-Info: glegroupsg2000goo.googlegroups.com; posting-host=178.37.232.66;
posting-account=xjvq9QoAAAATMPC2X3btlHd_LkaJo_rj
NNTP-Posting-Host: 178.37.232.66
User-Agent: G2/1.0
MIME-Version: 1.0
Message-ID: <6...@g...com>
Subject: Wyszukiwanie
From: "M.M." <m...@g...com>
Injection-Date: Thu, 28 Apr 2016 20:41:02 +0000
Content-Type: text/plain; charset=ISO-8859-2
Content-Transfer-Encoding: quoted-printable
Xref: news-archive.icm.edu.pl pl.comp.programming:209347
[ ukryj nagłówki ]
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ą?
Pozdrawiam
Następne wpisy z tego wątku
- 30.04.16 23:23 Wojciech Muła
- 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