Seznamte se: pypy (diskuse)

[unknown_]

[Vallhala]~>python a.py
Pystone(1.1) time for 50000 passes = 1.25
This machine benchmarks at 40000 pystones/second
[Vallhala]~>

Pentium M 1.7 GHz, FreeBSD 7.0-CURRENT

[paskma]

Pystone(1.1) time for 50000 passes = 0.87 This machine benchmarks at 57471.3 pystones/second

Core2 @1.86 GHz. Nejrychlejší komp, ke kterému mám přístup.

[xxx]

nema tam ke konci byt spis omega(n^2). (Teda ne z by to O(n^2) vylucovalo, ze je to i ta omega :)

[Marek Bernát]

Podľa mňa chcel autor povedať len toľko, že je to asymptoticky horšie ako lineárne. Tá big-O notation sa niekedy zneužíva na strašné veci

[paskma]

Jop, něco takového jsem chtěl říct . S tím, že "horší než lineární" není dost výstižné, protože O(n log(n)) je na "obyčejná" data vždy v pohodě. O(n^2) už umí udělat pěknou paseku. Kdo nevěří, ať si nechá seřadit bubble-sortem trapný milion integerů.

[Marek Bernát]

Hm, ale to už nemá s asymtotickosťou v nekonečne takmer nič spoločné. Ty sa snažíš namerať reálnu záťaž pre konečné n. A tam už zavážia aj konštanty apod. Konkrétne, ak máš časovú zložitosť T_n = 10^6 n log(n), tak platí T_n ∈ O(n log n), ale pre n = 10^6 to bude stále pomalšie ako nejaké S_n = n^2. Na druhej strane sa dá namietať, že v praxi tie riadiace konštanty nebývajú také zbesilé

Skrátka, aby som to zhrnul, tak o tom, akú zložitosť majú algoritmy v pypy, sa nedá povedať prakticky nič. Ale aspoň som si zopakoval asymptoty

[paskma]

Ale jasné. Ty jsi určitě tak ve třeťáku na výšce (MFF?), jsi aktuálně nasáklý tou teorií a vidíš, že moje povídání z pohledu téhle teorie není tak úplně košer.

Ale já jsem to psal z čistě inženýrského pohledu. Já si prostě myslím že je tam něco nelineárního, protože si nedovedu představit, že by tam byl milionkrát lineární průchod (jak jsi ostatně poznamenal).

Dneska pokračuju ve čtení dokumentace. Mají tam nějaký graf (uzly bloky kódu, hrany skoky) a ty uzly se snaží poskládat aby byl co nejmenší počet skoků. Teorii grafů jsem sice už skoro zapomněl, ale nějakým tím polynomem mi to smrdí.

[Marek Bernát]

Odhalil si ma, som na MFF Ale je to komplikovanejšie, lebo informatika ma prestala baviť, tak som prešiel na fyziku. Takže teóriou nasiaknutý nie som; O-notáciu som používal naposledy keď som riešil informatické súťaže na strednej. A to bolo už dáávno

To je dobre, že si sa dal na dokumentáciu. Ak sa dá niekde zistiť, akú to má zložitosť, tak asi tam. A idem sa na to pozrieť aj ja, znie to zaujímavo.

[Marek Bernát]

Aha, sorry, neviem prečo som si tú tvoju omega asocioval s Theta

Btw, O(n^2) a omega(n^2) sa vylučujú. Nevylučovalo by sa to s Omega(n^2). Potom by sme dostali tú Theta ako prienik. Dúfam, že zasa neblúznim