trideni textoveho souboru

[Pavel Kankovsky]

On Thu, 8 Jun 2000, Michal Krause wrote:

> To bych nerekl. Zrovna vcera jsem pri testovani map v C++ zkousel
> zjistit pocet unikatnich IP adres v souboru (to je takovy muj oblibeny
> test) a 13 MB soubor (1 milion radku) se timto zpusobem prechroustal za
> 18 vterin. Kombinace sort | uniq na tom pracovala nekolik minut.
> Je pravda, ze pametove naroky meho programku byly vyrazne vyssi

V tom je ten hacek. Je-li objem dat N, pak hasovanim (s vhodnou
hasovaci funkci a tabulkou velikosti O(N)) to lze profiltrovat v case
O(N), ale v nejhorsim pripade to muze vest k O(N) vypadkum stranky
a to naprosto nahodne rozlozenym po adresovem prostoru. Sort sice
potrebuje cas O(N log N), coz je teoreticky pomalejsi, ale k datum
pristupuje temer dokonale sekvencne (je pouzit algoritmus merge sort).
Mezi rychlosti nahodneho a sekvencniho pristupu je takovy propastny
rozdil, ze to ten logaritmicky clen *muze* snadno smazat.

Dalsi faktor stojici za uvahu je, jestli se v dane situaci vubec vyplati
snazit se usetrit nekolik minut casu pocitace za cenu nekolika minut prace
nutne na napsani toho programu. :)

> (protoze v tom souboru bylo zhruba 10% polozek unikatnich).

Coz znamena, ze jste v pameti mel pouze desetinu toho souboru, tj. 100 000
polozek o celkove velikosti 1.3 MB (nezapoctena rezie, ktera nemusi byt
zanedbatelna)...tedy pokud jste to nenaprogramoval nejak uchylne (od te
doby, co jsem na vlastni oci videl trideni s kubickou slozitosti, se
nedivim nicemu :> ). Zkuste to jeste jednou na souboru, kde budou vsechny
polozky unikatni.

--Pavel Kankovsky aka Peak  [ Boycott Microsoft--http://www.vcnet.com/bms ]
"Resistance is futile. Open your source code and prepare for assimilation."