PostgreSQL

[radim.kubacki na rtscs.cz]

> -----Původní zpráva-----
> Od:	Pavel Kankovsky 
> Odesláno:	1. října 1999 10:31
> Komu:	linux na linux.cz
> Předmět:	Re: PostgreSQL
> 
> On Fri, 1 Oct 1999, Oto tapik Buchta wrote:
> 
> > No mne by hlavne zajimalo, jestli ten dotycny vi, jak dlouho mu bude
> > trvat sort na 10^10 zaznamech. I pri slozitosti n.log(n) (zatim imho
> > nejlepsi, ceho se da dosahnout) je to neco kolem 10^11 kroku.
> 
> Da se dokazat, ze O(n log n) je asymptoticky nejlepsi mozna slozitost,
> pokud se vyuziva pouze porovnavani prvku (to je btw dulezity
> predpoklad...ve specialnich situacich lze tridit i s linearni slozitosti).
> 
> Dukaz je celkem jednoduchy: mame-li seznam n prvku, pak muze prijit v n!
> ruznych setridenich. Tj. algoritmus musi byt schopen provest n! ruznych
> permutaci, tj. musi provest alespon O(log n!) rozhodnuti, jak dal (na
> zaklade porovnani prvku), coz se za pouziti Stirlingova vzorce da
> prepocitat na O(n log n).
> 
> Snad tato mala comp-sci odbocka nikomu nebude vadit.
> 
Ja myslim, ze nevadi. Stoji za to uvedomit si ten predpoklad. 
IMHO se ale trideni 10 miliard zaznamu v databazi nebude delat quicksortem,
i kdyz ten v prumeru pracuje O(n log n). Ty data se totiz nevejdou do pameti
a porovnavat je na disku a tam je i prehazovat je pekna blbost.

V praxi se asi pouzije merge-sort. Na zacatku setridim kousky, ktere se
vejdou do pameti a ty potom slevam ve vetsi kusy. 
Anebo mam na to treba index (prip. si ho vytvorim, to se ale u trideni asi
nevyplati, u spojeni nekdy jo).

Celkove to ale urcite bude trvat dost dlouho, mozna to spocita za domaci
ukol. Myslim, ze iniciator tohoto threadu je uz z te myslenky vylecen.
Napsat aplikaci pracujici s takovym objemem dat neni uplna hracka. Snad mu
pokrok v hw pomuze. (Za par let :).)

Radim