Diskuze: Soutěž v programování :)
Zkus sem schválně ještě nějaký další násobky miliónu, kolik tvůj
sort zvládne maximálně a jaký budou časy a porovnal bych to s ostatníma
řešeníma 
Lukáš Hruda:22.1.2013 0:04
Škoda, to by otevřelo dost nových možností 
...třeba použití mediánu
jako pivot u quick sortu.
Je tam podmínka že znaky a délka mají bejt náhodný, takže ho těžko
vygenreueš už seřazený
Tak jsem se do toho dneska pustil s jiným algoritmem, a dostal jsem se u 1M
na 500 mls, ale na ta vaše čísla se asi nedostanu.
Luboš Běhounek Satik:23.1.2013 18:56
U mě generování taky trvá dýl než řazení
100M mám za 1,8 s
Můžeš mi zkusit poslat exáč, zkusím to na svém procesoru, ať jsou stejné podmínky.
Metodu evidentně používáme stejnou, takže rozdíl už je asi jen v implementaci.
Luboš Běhounek Satik:23.1.2013 19:29
Tvůj alg. na mém počítači (v závorce časy mého alg.)
1 000 000 33ms (27ms)
10 000 000 290ms (202ms)
100 000 000 2850ms (1890ms)
Už si nepamatuju, jestli jdeš na sraz, pokud ano, tak se připomeň, máš
u mě drink
Lukáš Hruda:23.1.2013 19:48
Na sraz nejdu, ale celkem rád bych viděl tvuj algoritmus, můžeš mi ho
poslat na mail?
Dík... moc se v tom nevyznam Pochopil sem žes použil stejnej řadící algoritmus jako já, ale
tvoje implementace je o dost složitější, asi bych hodně dlouho koumal jak
to funguje
Díky, po pátku to tu zveřejním a trochu popíšu, jen asi budu muset
vyhodit to goto, jinak mě Kit zabije .
Lukáš Hruda:23.1.2013 23:57
Taky bych sem moh pak hodit to svoje, sice to neni tak rychlý, ale je to
kratší a jednodušší.
Lukáš Hruda:24.1.2013 16:22
Bylo tu řečeno je multithreading je povolen, takže sem to ještě poněkud
zrychlil, počítam že tvuj procesor má alespoň 2 jádra. Pošlu ti to na
mail
Luboš Běhounek Satik:24.1.2013 18:35
Teď jsem už v Praze, tady mám k dispozici jednojádrový notebook a
dvoujádrový core i3 na 3 GHz,
10M té vícejádrové verze tu (na tom i3) trvalo 175ms (moje verze tu trvá
145ms - už se docela blížíš ), nemáš doma 4jádro, že by jsi to přepsal pro 4 jádra a zkusil
poměřit to u tebe?
Pár dalších tipů na optimalizaci:
Místo short intů můžeš použít zkusit použít (unsigned) char, i když to
asi na výkon vliv mít moc nebude.
Znaky bych neukládal jako pole polí znaků, ale jen jako pole znaků (i když
to je vnitřně vlastně fuk, stejně to pak bereš jako jedno velký pole).
Jedno slovo bych ukládal jen jako 4 znaky - tj. pokud je slovo dlouhé 4
znaky, tak na konci nemá nulu, když o tom víš předem, tak proč to
nevyužít
Memory alignment někdy dokáže taky trochu vylepšit rychlost a hlavně ti
umožní nějaké další optimalizace, jako třeba vymazat všechny 4 znaky na
nulu v podstatě jednou instrukcí.
Edit 19:15 :
Navíc by to nešlo bez memory leaků. Správná dealokace paměti by hrozně
moc snížila rychlost...
Lukáš Hruda:24.1.2013 21:32
Ty pole se nemusí sčítat, stačí ve výslednym přepočtu vždy sečíst
hodnotu na stejnym indexu v obou polích. ...což už vlastně dělá každý
vlákno zvlášť.
Lukáš Hruda:24.1.2013 21:45
Poslal sem ti na mail poslední verzi, víc zesložiťovat už to nebudu, mam
na práci i jiný věci
...po pátku sem hodim tu původní verzi, tu co běžela na jednom
vlákně.
Luboš Běhounek Satik:24.1.2013 22:16
Trva to porad stejne dlouho, mozna bys musel to pole znaku zarovnavat na
ctverice misto na petice
Lukáš Hruda:24.1.2013 22:22
Já sem tu velikost slov vrátil zpátky jak to bylo, rozdíl v rychlosti v
tom nebyl a takhle ty slova můžu aspoň normálně vypsat, když mají na
konci nulovej znak, nemusim je vypisovat znak po znaku... Změnil sem jenom ty
short int na char, ošetřil ty vlákna a udělal kopírování řetězců přes
int podle prvního, což rychlost trochu zvedlo, ale to sčítání polí kvůli
vláknům jí zase srazilo.
Tady je moje verze jak jsem slíbil
Jedno vlákno: http://www.itnetwork.cz/dev-lighter/66
Dvě vlákna: http://www.itnetwork.cz/dev-lighter/67
Michael Olšavský:28.1.2013 8:02
Tak to mam skoro stejne jako ty. Jen sem nepouzil lowendove konstrukce a mej
jse problem u counting sortu s prevedenim cisla zpatky na slova(znaky) 
Urcite bych ocenil dalsi soutez a muze to byt klide neco vetsiho.
Zobrazeno 42 zpráv z 92.