Nejvhodnější algoritmus pro druhé (n-té) nejvyšší číslo pole (diskuse)

[Martin]

Pole N čísel můžeš na místě sestavit do binární haldy (to jde v čase O(N)), pak z ní K-krát odebrat maximum (pro odebrání maxima potřebuješ čas O(log(N)), takže pro nalezení K-tého největšího prvku potřebuješ čas O(N + K * log(N)).

[Kyosuke]

+1 A Freshmouse by si konečně mohl koupit ty "správný amíky". (A já bych si je měl přečíst. )

[freshmouse]

Jaký správný Amíky?

(Mimochodem, včera jsem si koupil k Vánocům Návrhový vzory od Pecinovskýho, jak jste mi je minule někdo doporučoval. Babička měla v knihkupectví jistou slevu, a tak mi řekla, ať si vyberu nějakou knížku. Já bral tuhle. Mimochodem, ta knížka je asi dost horký zboží, už ji nikde moc nemaj. Včera jsem před spaním dal tak sto stránek, a musím říct, že se mi to líbí. Je to psaný hodně zajímavou formou. Rozhodně jsem její koupí neprohloupil.)

[bazil]

udělal bych to ještě jinak, hodil bych pole do binárního vyhledávacího stromu (časová náročnost O(N)), při tom bych si zapamatoval, kam se mě ukládá nějvětší číslo pole (tohle nezvýší časovou náročnost ne?), nastavil bych si kořen na nejvyšší číslo (pokud by strom měl obousměrné ukazatele(jooo jak ukazatele udělat v javě, mno nic no), tak je časová náročnost teoreticky 1) a pak bych provedl průchod stromem, a to o počtu n kroků (kde n je n-té největší číslo) s tím, že bych se vydal dycky po té větvi, v které by leželo větší číslo (časová náročnost n) ... a nebo tu oba mluvíme o stejné věci jen jinak??

[Martin Tůma]

Nemluvíte. To co navrhuješ ty je blbost. Obecný binární vyhledávací strom má MIN i MAX vždy v listu. Takže odtamtud se těžko vydáš "dolů". (A kdyby tě snad napadlo jít "nahoru", tak n kroků ti taky nezaručuje nalezení n-tého prvku)

Jinak obecně se pod O(N*log(N)) nelze dostat, neboť nalezení n-tého prvku z podstaty věci vyžaduje seřazení pole a to rychleji (pomocí algoritmů založených na porovnávání) než O(N*log(N)) nelze provést.

[MJ]

Jinak obecně se pod O(N*log(N)) nelze dostat, neboť nalezení n-tého prvku z podstaty věci vyžaduje seřazení pole a to rychleji (pomocí algoritmů založených na porovnávání) než O(N*log(N)) nelze provést.

Proč by to vlasně mělo vyžadovat seřazení pole? A proč by ho pak nemělo vyžadovat nalezení druhého největšího prvku?

P.S.: Samozřejmě existuje lineární algoritmus

[Martin]

Ach jo, já veděl, že existuje ještě lepší řešení. Ale že jsem ho viděl minulý semestr na Tvé přednášce, to už mě nenapadlo. Jsem to ale ostuda.

[bazil]

ježiš, můžu se stydět? teď sem si uvědomil můj strašlivej omyl při přerovnávání toho stromu, aby představoval setříděný pole ... mě to hned nedošlo tak brzo ráno/pozdě v noci

[MJ]

udělal bych to ještě jinak, hodil bych pole do binárního vyhledávacího stromu (časová náročnost O(N)), [...]

Tohle určitě v lineárním čase stihnout nejde, na vytvoření vyhledávacího stromu je potřeba čas alespoň Ω(N log N). Ale tady je vyhledávací strom overkill.

[Martin]

Zajímalo by mě, jak se takový binární vyhledávací strom vyrábí v lineárním čase. To by se mohlo celkem hodit, prozradíš mi to (pokud to není velké tajemství)?

[freshmouse]

Hmm, díky. Fakt vás ma tom Matfyzu asi něco učí!

Sice moc nerozumím tomu, co říkáš, ale rozhodně už jsem inspirován. Podívám se po tom.

[happy barney]

mne osobne sa pozdáva Fibonacci heap, hlavne vďaka jeho náročnosti pri spájaní viacerých "háld" (ble, to slovo sa mi nepáči)

[Martin]

Nemyslíš si, že programovat kvůli úloze nalezení K-tého největšího prvku Fibonacciho haldu je trochu zbytečné? Jako cvičení by to bylo určitě přínosné, ale jinak... já třeba vím jen to, že něco takového existuje, že je to lepší než binární halda (takže může urychlit spoustu algoritmů, třeba Dijkstru), ale to je asi tak všechno. Myslím, že pro začátek freshmousovi postačí prachobyčejná halda binární.

[happy barney]

no ... Fibonacci heap nie je na naprogramovanie zložitý, možno i jednoduchší, aj keď pochopenie princípu môže byť náročnejšie.

pomocou toho pdf to imho naprogramuje aj začiatočník

[Martin]

Pokud by tě to opravdu zajímalo (což je chvályhodné), tak tohle dělává i pan docent Töpfer na přednášce z Programování I. Mělo by tam být vše o binární haldě a operacích na ní (včetně hezkého důkazu, že se dá z pole halda vytvořit v lineárním čase, pokud bys tomu nevěřil – já tomu třeba nevěřil do té doby, než jsem si ten důkaz tehdy přečetl ) a probíral i vyhledání K-tého nejmenšího prvku (to je principiálně úplně stejná uloha jako hledání K-tého největšího prvku, akorát při ní máš haldu "obráceně" ).

A že je ten čas vánoční, tak udělám dobrý skutek a najdu tu přednášku za tebe. Tady to je, přeju příjemnou zábavu.

Hmm, díky. Fakt vás ma tom Matfyzu asi něco učí!

No jak jsem si tak přečetl MJův příspěvek výše, tak nevím nevím.

[Josef Kufner]

Nejlepší by bylo to udělat už při načítání/sestavování pole a držet si indexy, kde co je.

[Jirka P]

Určitě existuje. Jednak je tu velmi profláklý O(N) algoritmus, který se učí snad všude (medián mediánů). S jeho efektivitou je to ale všelijaké a člověk si s tím musí dost pohrát. Pak jsou modifikace třídících algoritmů (např qsort -> zahodit půlku, kde ten prvek určitě není).

Viz Wikipedii.

[freshmouse]

O(N) algoritmus, který se učí snad všude.

Hmm, tak já o tom snad ani neslyšel. Naše algoritmizace začala slovy "otevřete si Netbeans"... No, to trošku přeháním, ale je fakt, že jsme se hned učili spíš Javu než algoritmizovat.

Pak jsou modifikace třídících algoritmů (např qsort -> zahodit půlku, kde ten prvek určitě není).

Mrknu na to.

[andree]

ten upraveny quicksort sa na toto pouziva asi najcastejsie... je to relativne rychle, lahko naprogramovatelne a prehladne

[Tom.š Ze.le.in]

IMHO neexistuje. Nejlepší algoritmus podle mne závisí tom, zda n je malé (v porovnání s rychlou pamětí kterou na to jsme ochotni vyčlenit) nebo ne. Zda se všechny prvky vejdou do paměti nebo ne. A i na dalších podmínkách zadání - space vs. speed, zda to to pole musí přežít a pod.

[wake]

Když se google cítí jako lucka při zaklínadle algorithm finding nth smallest number, vypadne z něj tohle.

[MJ]

To je pěkný algoritmus, pokud se ovšem smíříme s tím, že má lineární časovou složitost jen v průměrném případě.

[MJ]

Možnosti, jak vybrat k-tý největší z n prvků, jsou asi tak tyto:

• pole setřídit: čas O(n log n), paměť O(n)
• algoritmus šitý na míru konkrétnímu k (třeba ten výše pro k=2): čas O(n), paměť O(1)
• pamatovat si v poli k zatím nejvyšších prvků, které jsme viděli, a nový vždy do tohoto pole zatřídit: čas O(nk), paměť O(k)
• použít pro totéž vyhledávací strom nebo lépe haldu: čas O(n log k), paměť O(k)
• postavit haldu pro všech n prvků (to jde lineárně) a pak k-krát smazat minimum: čas O(n log n), paměť O(n)
• modifikovaný QuickSort – vyberu si pivot, rozházím prvky na menší a větší a všimnu si, že jednu z částí mohu zahodit: čas O(n) v průměrném případě, paměť O(n)
• rekurzivní trik s pěticemi, kterým lze předchozí algoritmus zrychlit na O(n) v nejhorším případě
• různé algoritmy pro konkrétní typy hodnot – třeba pro integery z rozsahu [0,U] lze použít Van Emde-Boasovy stromy: čas O(n log log U), paměť O(U).

Viz třeba poznámky k přednášce o algoritmech a datových strukturách (trochu nekompletní, ale zrovna vybírání je tam popsané docela podrobně).

[Kyosuke]

Hmm, u té haldy přes všechny prvky platí čas O(n.log n) i pro k << n?

[Ondrej 'SanTiago' Zajicek]

Ne, to bude O(n+k*log(n)).

[MJ]

Jo jo, upsal jsem se.

[elviin]

O(nlog k)

   using namespace std;

   partial_sort(
      size_coll.begin(), 
      size_coll.begin() + GREATEST_K_ELEMENT, 
      size_coll.end(), 
      greater<size_type>() 
   );

   cout << size_coll.at(GREATEST_K_ELEMENT - 1) << endl;

Funkcni prog. je na pastebin.com.

[zde]

Vezmu normální insert sort, jen omezím tu vnitřní smyčku, aby se nedotřiďovalo celé pole, a bude to dělat přesně to co potřebujete.

[srigi]

Mno keby sa jednalo o C-ko, velmi vyhodne by som nasadil pointeri. Hlavne teda pri hladani druheho najvyssieho prvku bu bola ucinnost velmi vysoka (staci si po najdeni noveho MAX do pomocneho pointra odkladat adresu predchadzajuceho prvku). Pri hladani k-teho prvku z mnoziny n cisel by sa tiez naslo nejake krasne riesenie s max. dvoma for () {}

[Josef Kufner]

Ještě je důležité nezapomenout na případ, kdy je kontrolovaný prvek menší než dočasné maximum, ale větší než předposlední maximum.

[peter]

Pokial sa bavime o casovej narocnosti O(..), tak ta nejake pointery nezachrania. Najlepsie co sa da dosiahnut je to O(n) a az potom si to mozes optimalizovat trebarz aj v assembleri. Dva fory byvaju O(n^2), co je o dost horsie. (radovo 1000 krokov vs. milion)

[Josef Kufner]

Ono to nebude O(n^2), ale O(n*k).

[peter]

No ked k=konst. tak O(n*k)=O(n), ze. Ale ja som myslel k-ty prvok, az teraz som si uvedomil co bol povodny problem. Tam je skutocne najjednoduchsie prejst cele pole a nechavat si okrem maxima aj stare maximum.