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.
Drahomír Hanák:20.1.2013 20:54
To není zrovna extra výkon (resp. jde to o dost líp) 
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?
Frunta:20.1.2013 21:42
Chtěl bych se zeptat, jestli je vylosovaných 100 000 slov za jednu minutu a
třicet osm sekund (1:38) dobrý čas, nebo jsem mimo ligu?
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 21:52
A nepočítáš do té doby i generování těch slov?
Fugiczek:20.1.2013 21:54
Až na to že Java měla +-90ms a C# 150ms. Java vede!
Frunta:20.1.2013 21:55
Počítám pouze generování čísel.
Programuji v C++.
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
Kit:21.1.2013 9:46
Zkus raději přemigrovat na jiný algoritmus. Bubblesort se na tohle opravdu
nehodí
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ý
Luboš Běhounek Satik:21.1.2013 22:14
Sakra, chlape, tebe je na ten Gamemaker skoda
TomBen:21.1.2013 22:16
Game Maker by si zasloužil víc takových a nebyl by to pak
takový ušmudlánek. 
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.
Luboš Běhounek Satik:22.1.2013 0:17
Nebo třeba rovnou pole vygenerovat seřazené
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...
Don:24.1.2013 21:11
Já teda nevím, ale v pekle to začalo. Teď už to jde do nebes
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ášť.
Luboš Běhounek Satik:24.1.2013 21:41
Ano, takhle jsem to sčítání polí myslel
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 92 zpráv z 92.