Diskuze: Soutěž v programování :)
Jakože:
a
b
c
aa
bb
aaa
bbb
nebo:
a
aa
aaa
b
bb
bbb
c
Dá se to chápat různě 
... a ještě dotaz máš ve windows nainstalované PHP?
Luboš Běhounek Satik:20.1.2013 18:18
Varianta 2:
a
aa
aaa
b
bb
bbb
Mám tu Wamp, takže PHP to být může
Jen pro zajímavost:
sortovací funkce v Game Makeru udělá 50000 slov za 140.81 vteřiny
na 1 vlákně o 2.3Ghz za výše uvedených podmínek.
Měli byste být lepší, ať svému oblíbenému jazyku neuděláte ostudu.
GM obecně plýtvá výkonem kde jen může. Faktem je, že Mark Overmars
asi nečekal využití GM v jiných oblastech než PacMan & company. 
Prave jsem zkusil svuj radici algoritmus a trochu me ten cas vydesil,
premyslim, jestli ma cenu to optimalizovat, zkusil jste to jeste nekdo, abych
mel od ceho se odrazit?
Luboš Běhounek Satik:20.1.2013 21:49
V čem to programuješ? Zkoušeli jsme zabudované řazení u kolekcí v
Jave/C# a časy byly kolem 100ms
Luboš Běhounek Satik:20.1.2013 22:28
Myslim, ze to generovani je az zbytecne moc robustne napsane urcite hodne
zpomaluje treba ten stringstream, pouzij tu moji verzi, taky to neni zadna
slava, ale bezi to rychleji
.
David Jančík:20.1.2013 22:56
Hmm, já sme se 100k se dostal na 70ms. Ale to brzdí ta kolekce. I když do kompareru dám jen return 1; tak se pod 20ms nedostanu. Zítra ju vyhodim a uvidim co se s tím dá udělat.
Jinak dobrej nápad s tou soutěží 
Ale C++ to nevyhraje, ani kdybych měl dělat ve Fortranu, Lue nebo
nějakym takovym jazyce, kterej by měl bejt safra rychlej
Luboš Běhounek Satik:20.1.2013 23:13
Ja misto stringu pouzivam nulou ukoncene pole charu jako se pouzivaly nekde
pred 20-30 lety a misto kolekci pole, takze rezie temer nulova
A taky porovnavas 100k slov vs 50k slov (coz jsem teda zatim testoval jen
kvuli tomu GM ), pokud nemas
linearni slozitost algoritmu, tak 100k slov bude trvat vice nez dvojnasobek casu
nez razeni 50k slov
Ja se dobrovolne porazit nenecham, i kdybych to mel prepsat cely do asm
David Jančík:21.1.2013 10:03
Já sme nebublinkoval
Ale taky sem zkoušel quick sort, ale nic moc. Pak sem zkoušel přes LINQ ten
mě vycházel dycky nejrychlejš, ale na to C++ sme se furt nedostal.
Nejrychlejác sem to měl kolem 30ms 50k slov.
Luboš Běhounek Satik - Máš už hotový referenční program? Potřeboval bych se
tě na něco zeptat ohledně mého řešení a nechtěl bych nějak ovlivnit to
tvoje, kdybys na něm ještě pracoval
Luboš Běhounek Satik:21.1.2013 11:14
Odpovědi na tvé otázky najdeš nahoře - 50k slov jsem tu zkoušel jen
kvůli porovnání s gamemakerem, jinak to asi milióny nebo desetimilióny
budou
Neaktivní uživatel :
Základ už mám, teď už jen ladím drobnosti, možná ještě to zkusím
přepsat do asm.
Luboš Běhounek Satik:21.1.2013 16:17
To uz je docela slusny, zatim nejlepsi vysledek
Myslím, že hlavní měření můžeme provést na 10M nebo 100M slovech.
Mě napad ještě jeden způsob jak porovnat řetezce, otázka je ale jestli
bude rychlejší, spíš bych řek že ne, ale vyzkoušim to
Luboš Běhounek Satik:21.1.2013 16:44
No, teoreticky můžeme řadit až něco kolem 400M slov (teď jsem to
zkoušel na svém alg. a zvládá to), ale záleží dost na tom, jaká je
paměťová náročnost zvolených algoritmů
Michael Olšavský:21.1.2013 17:33
Co je to za algoritmus???? =-O Mě to quicksortem(nebo alespoň napodobeninou) trvá 1 000 000 slov
v c# zhruba 5 sekund!
Luboš Běhounek Satik:21.1.2013 18:07
C# má nějakou režii oproti C++ navíc a má některé vlastnosti, které se občas nehodí - např. ta, že všechny pole při vytváření vynuluje, což někdy není potřeba a zbytečně to snižuje výkon.
Používání low-level konstrukcí (char[] místo string, pole místo kolekcí) může taky urychlit výpočet, protože se sníží režie.
Míst k optimalizacím je tam spousta.
Když napíšu, že 10 000 000 slov řadím v jednom vlákně na 2,8GHz
procesoru za méně než 200ms, budete mi to věřit?
Luboš Běhounek Satik:21.1.2013 19:00
V pátek sem hodím zdrojáky a lehce povysvětlím, co a jak dělám, pokud
mě někdo nepřekoná
Hm, tak jsem vyvinul algoritmus na míru tomu zadání.
Je trochu atypický, ale vypadá, že dělá co má.
Přinutil jsem s tím GameMaker udělat 1M za 11.13sec. To sice není
bůhvíco,
ale u gml kódu to bude pravděpodobně fyzikální hranice. Pro srovnání
je
třeba uvést, že třídění stejného množství pomocí vestavěné
funkce
( označované v návodech za rychlou ) jsem včera po třech hodinách
vypnul, protože hrozilo, že počítač obroste lišejníkem.
V rychlejších jazycích by ten princip třídil zřejmě celkem neskutečně.
Luboš Běhounek Satik:21.1.2013 21:55
Kdyžtak mi napiš zprávou, jaký postup jsi použil, třeba jsme použili
stejný
Zobrazeno 50 zpráv z 92.