Avatar
Luboš Běhounek (Satik):

Vaším úkolem bude seřadit zadané velké množství (řádově stovky tisíc až milióny) náhodně vygenerovaných slov co nejrychleji.

Jak by měla vypadat struktura aplikace:

  1. Program se zeptá na počet slov
  2. Program v textové podobě vygeneruje (využitím standardní funkce random (nebo její obdoby) vybraného jazyku) zadaný počet slov, přičemž slovo může obsahovat pouze ascii znaky 'a'-'z' a jejich počet v jednom slově je také náhodný a je v rozmezí 1-4 znaků. Slova se mohou opakovat.
  3. Spustí se časovač, který měří dobu výpočtu
  4. Spustí se řadící funkce
  5. Spočítá se a vypíše celkový čas řazení
  6. Program se zeptá, jestli chceme seřazená slova vypsat na disk (pro rychlou kontrolu správnosti), a vypíše je do souboru, pokud vybereme ano (ideálně textová podoba, každé slovo na vlastní řádek, WIN-style zalamování řádků) :)

Program může být napsán v jakémkoliv jazyce, který je přeložitelný do něčeho spustitelného ve Windows.

Spustitelný soubor včetně zdrojových kódů mi posílejte na mail ulu-mulu@seznam.cz

Čas máte do pátku 25.01.2013 17:30, kdy zhruba začíná Devbook.cz sraz.
Pokud tam bude internet, tak sem hned napíšu seznam výsledků :) .

Řešitelé s řešením rychlejším než moje řešení mají na devbook srazu večeři ode mě zdarma (pokud se tento pátek srazu nezúčastníte, výhra se přenáší na příští srazy).

Pokud bude vaše řešení nejhůře 2x pomalejší než moje, máte u mě na srazu alespoň drink (také se přenáší).

Případné dotazy a nejasnosti do komentářů, nápady a diskuzi řešení si prosím nechte až po vyhlášení ;)

Odpovědět  +2 20.1.2013 16:41
:)
Avatar
Odpovídá na Luboš Běhounek (Satik)
Luboš Běhounek (Satik):

Dodatek k řazení: kratší slova by měla být ve výstupu před delšími slovy.
Např.

a
aa
aaa

Nahoru Odpovědět 20.1.2013 17:27
:)
Avatar
Pavel Vosyka
Člen
Avatar
Pavel Vosyka:

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? :)

Nahoru Odpovědět 20.1.2013 18:15
"nikdy nepiš nic 2x"
Avatar
Odpovídá na Pavel Vosyka
Luboš Běhounek (Satik):

Varianta 2:

a
aa
aaa
b
bb
bbb

Mám tu Wamp, takže PHP to být může :)

Nahoru Odpovědět 20.1.2013 18:18
:)
Avatar
Michael Olšavský:

Můžu použít více vláken?

 
Nahoru Odpovědět 20.1.2013 20:03
Avatar
Luboš Běhounek (Satik):

doublepost

Editováno 20.1.2013 20:05
Nahoru Odpovědět 20.1.2013 20:05
:)
Avatar
TomBen
Redaktor
Avatar
TomBen:

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. :)

Nahoru Odpovědět 20.1.2013 20:35
Za posledních 200 miliónů let se nic zvláštního nestalo, akorát dinosauři vymřeli a opice se naučily programovat.
Avatar
Drahomír Hanák
Tým ITnetwork
Avatar
Odpovídá na TomBen
Drahomír Hanák:

To není zrovna extra výkon (resp. jde to o dost líp) :P

 
Nahoru Odpovědět 20.1.2013 20:54
Avatar
TomBen
Redaktor
Avatar
Nahoru Odpovědět 20.1.2013 20:57
Za posledních 200 miliónů let se nic zvláštního nestalo, akorát dinosauři vymřeli a opice se naučily programovat.
Avatar
TomBen
Redaktor
Avatar
TomBen:

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. :D

Nahoru Odpovědět 20.1.2013 21:02
Za posledních 200 miliónů let se nic zvláštního nestalo, akorát dinosauři vymřeli a opice se naučily programovat.
Avatar
Luboš Běhounek (Satik):

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? :D

Nahoru Odpovědět 20.1.2013 21:23
:)
Avatar
Frunta
Redaktor
Avatar
Odpovídá na Luboš Běhounek (Satik)
Frunta:

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? :D

Editováno 20.1.2013 21:44
 
Nahoru Odpovědět 20.1.2013 21:42
Avatar
Luboš Běhounek (Satik):

Pro porovnání: zatím jsem na 32ms pro seřazení 50 000 slov

Nahoru Odpovědět 20.1.2013 21:47
:)
Avatar
Odpovídá na Frunta
Luboš Běhounek (Satik):

V čem to programuješ? Zkoušeli jsme zabudované řazení u kolekcí v Jave/C# a časy byly kolem 100ms :)

Nahoru Odpovědět 20.1.2013 21:49
:)
Avatar
Odpovídá na Frunta
Luboš Běhounek (Satik):

A nepočítáš do té doby i generování těch slov? :D

Nahoru Odpovědět 20.1.2013 21:52
:)
Avatar
Fugiczek
Redaktor
Avatar
Odpovídá na Luboš Běhounek (Satik)
Fugiczek:

Až na to že Java měla +-90ms a C# 150ms. Java vede! :D

 
Nahoru Odpovědět 20.1.2013 21:54
Avatar
Frunta
Redaktor
Avatar
Odpovídá na Luboš Běhounek (Satik)
Frunta:

Počítám pouze generování čísel. :D
Programuji v C++.

Editováno 20.1.2013 21:57
 
Nahoru Odpovědět 20.1.2013 21:55
Avatar
Odpovídá na Frunta
Luboš Běhounek (Satik):

Zajimalo by me, co na generovani slov tak trva, muzes to poslat? (Cas se pocita az u razeni, takze tohle klidne zverejnit muzes)

A tady je kdyztak verze, co na generovani dat pouzivam ja:
http://pastebin.com/eFLgvnpY

Nahoru Odpovědět 20.1.2013 22:10
:)
Avatar
Odpovídá na Luboš Běhounek (Satik)
David Jančík [sczdavos]:

A to si děláš vlastní sortící metodu? Já sme zkoušel to na těch kolekcích a mám časy řazení u 100k slov kolem 190ms. Ale taky to dost záleží na stroji na kterým to pustíš, sem přepnul z úspornýho režimu kde mi to trvalo seřadit 650ms za vysokej výkon a zrychlení bylo fakt velký.

Generování 100k slov mi trvá kolem 50ms.

Editováno 20.1.2013 22:12
Nahoru Odpovědět 20.1.2013 22:11
Čím více času dostaneš, tím méně ho máš.
Avatar
Odpovídá na David Jančík [sczdavos]
Luboš Běhounek (Satik):

Jj, vlastni sort, ty sorty v kolekcich jsou univerzalni a umej sortovat vsechno, ale maj taky docela velkou rezii.

A vlastni algoritmus si muzu prizpusobit a optimalizovat podle dat a situace.

Nahoru Odpovědět 20.1.2013 22:14
:)
Avatar
Frunta
Redaktor
Avatar
Odpovídá na Luboš Běhounek (Satik)
Frunta:

Nejspíše to mám plné neefektivních a zbytečných součástek.

http://pastebin.com/he2kvb0H

 
Nahoru Odpovědět 20.1.2013 22:17
Avatar
Odpovídá na Frunta
Luboš Běhounek (Satik):

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 :) .

Nahoru Odpovědět 20.1.2013 22:28
:)
Avatar
Luboš Běhounek (Satik):

Trocha statistik k řazení slov dle zadaných kritérií:

Velikost souboru : 50 000 slov
Procesor : Intel Core 2 Quad Q9550 2,8GHz

Nativni sort PHP : 230ms
Nativni sort C# 32bit : 155ms
Nativni sort C# 64bit : 145ms
Nativni sort java : cca 90 ms
C++ vlastni sort 32bit : 6 ms

Nahoru Odpovědět 20.1.2013 22:42
:)
Avatar
Odpovídá na Luboš Běhounek (Satik)
David Jančík [sczdavos]:

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 :D

Nahoru Odpovědět 20.1.2013 22:56
Čím více času dostaneš, tím méně ho máš.
Avatar
Odpovídá na David Jančík [sczdavos]
Luboš Běhounek (Satik):

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 :D

Editováno 20.1.2013 23:17
Nahoru Odpovědět 20.1.2013 23:13
:)
Avatar
Kit
Redaktor
Avatar
Odpovídá na Luboš Běhounek (Satik)
Kit:

100k slov mi připadá pro můj Atom málo. Nebylo by lepší soutěžit s 10M slovy? Jak dlouhá mají být ta slova?

Nahoru Odpovědět 21.1.2013 8:54
Vlastnosti objektů by neměly být veřejné. A to ani prostřednictvím getterů/setterů.
Avatar
Odpovídá na Luboš Běhounek (Satik)
David Jančík [sczdavos]:

Tak sem to udělal jak si říkal, dal sme tam pole charů a zbytek vypustil. Ale to řazení pak trvalo ještě dýl asi o 20ms. A to jsem zkoušel celkem rychlé metody řazení. Tak nevim, asi budu muset přemigrovat na jiné jazyk.

Nahoru Odpovědět 21.1.2013 9:24
Čím více času dostaneš, tím méně ho máš.
Avatar
Kit
Redaktor
Avatar
Odpovídá na David Jančík [sczdavos]
Kit:

Zkus raději přemigrovat na jiný algoritmus. Bubblesort se na tohle opravdu nehodí :)

Nahoru Odpovědět 21.1.2013 9:46
Vlastnosti objektů by neměly být veřejné. A to ani prostřednictvím getterů/setterů.
Avatar
Odpovídá na Kit
David Jančík [sczdavos]:

Já sme nebublinkoval :D 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.

Nahoru Odpovědět  +1 21.1.2013 10:03
Čím více času dostaneš, tím méně ho máš.
Avatar
Kit
Redaktor
Avatar
Odpovídá na David Jančík [sczdavos]
Kit:

Také záleží na typu procesoru a celkovém výkonu počítače. Když jsem zkoušel různé jazyky na různých PC, tak na jednom vítězilo C++, na jiném Java.

Nahoru Odpovědět 21.1.2013 10:56
Vlastnosti objektů by neměly být veřejné. A to ani prostřednictvím getterů/setterů.
Avatar
Lubos857
Člen
Avatar
Lubos857:

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 :-D

Nahoru Odpovědět 21.1.2013 10:57
Protože bagr nežere cukr.
Avatar
Odpovídá na Kit
Luboš Běhounek (Satik):

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 :)

Lubos857 :
Základ už mám, teď už jen ladím drobnosti, možná ještě to zkusím přepsat do asm.

Nahoru Odpovědět 21.1.2013 11:14
:)
Avatar
Lukáš Hruda (Luckin):

Processor Inlel Core Duo (2.4GHz)
100 000 slov - generování 31 - 32 ms, řazení 31 - 32 ms
1 000 000 slov - generování 330 - 360 ms, řazení 660 - 720 ms
10 000 000 slov - generování - cca 3.5 s, řazení - cca 10.5 s
Psáno v C++.
Kompilováno v g++ (Dev-C++) se zapnitou maximální optimalizací.

 
Nahoru Odpovědět 21.1.2013 16:03
Avatar
Odpovídá na Lukáš Hruda (Luckin)
Luboš Běhounek (Satik):

To uz je docela slusny, zatim nejlepsi vysledek :)

Myslím, že hlavní měření můžeme provést na 10M nebo 100M slovech.

Nahoru Odpovědět 21.1.2013 16:17
:)
Avatar
Odpovídá na Luboš Běhounek (Satik)
Lukáš Hruda (Luckin):

Myslim že 10M je akorát, 100M už je moc, to může trvat i několik minut.

 
Nahoru Odpovědět 21.1.2013 16:32
Avatar
Odpovídá na Lukáš Hruda (Luckin)
Luboš Běhounek (Satik):

Zatím jsem na 7 ms (řazení) pro 100k čísel, zadání jsem schválně napsal tak, aby bylo možné oproti běžnému sortování použít hodně drastické optimalizace.

Jinak napsáno a zkompilováno to mám v MSVS 2008.

Editováno 21.1.2013 16:36
Nahoru Odpovědět 21.1.2013 16:34
:)
Avatar
Lukáš Hruda (Luckin):

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 :D

 
Nahoru Odpovědět 21.1.2013 16:39
Avatar
Odpovídá na Lukáš Hruda (Luckin)
Luboš Běhounek (Satik):

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ů :)

Nahoru Odpovědět 21.1.2013 16:44
:)
Avatar
Odpovídá na Luboš Běhounek (Satik)
Lukáš Hruda (Luckin):

Jinak, měřil jsem to funkcí clock(), takže u těch 100k to asi nebude moc přesný, může to bejt 30, stejně tak 10 nebo 50. Proto jsem sem hodil i ty vyšší čísla, u těch už by to mělo bejt dostatečně přesný.

 
Nahoru Odpovědět 21.1.2013 16:46
Avatar
Luboš Běhounek (Satik):

Koukni na funkce queryperformance, ty to umějí přesněji.

Nahoru Odpovědět 21.1.2013 16:47
:)
Avatar
Odpovídá na Lukáš Hruda (Luckin)
Michael Olšavský:

Co je to za algoritmus???? =-O :-D Mě to quicksortem(nebo alespoň napodobeninou) trvá 1 000 000 slov v c# zhruba 5 sekund!

 
Nahoru Odpovědět  +1 21.1.2013 17:33
Avatar
Kit
Redaktor
Avatar
Odpovídá na Michael Olšavský
Kit:

Tak to jsem si myslel, že se svým naprosto neoptimalizovaným Radixsortem v Javě na Atomu 1.6 GHz a časy

 100000 ...  361 ms generování,  248 ms sort
1000000 ... 2958 ms generování, 1608 ms sort

jsem patlal.

Neberte to jako konečné řešení. Javu se teprve učím a právě jsem dostal nápad, jak to radikálně zrychlit.

Nahoru Odpovědět 21.1.2013 17:45
Vlastnosti objektů by neměly být veřejné. A to ani prostřednictvím getterů/setterů.
Avatar
Odpovídá na Michael Olšavský
Lukáš Hruda (Luckin):

Je to Quick sort... záleží taky dost na tom jak máš napsaný porovnání řetězců a prohození, nesmíš je kopírovat celý.

 
Nahoru Odpovědět 21.1.2013 18:01
Avatar
Odpovídá na Michael Olšavský
Luboš Běhounek (Satik):

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? :)

Nahoru Odpovědět  +1 21.1.2013 18:07
:)
Avatar
Lubos857
Člen
Avatar
Lubos857:

Ač to nechápu, tak věřím :-D

Nahoru Odpovědět 21.1.2013 18:20
Protože bagr nežere cukr.
Avatar
Odpovídá na Lubos857
Luboš Běhounek (Satik):

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á :D

Nahoru Odpovědět 21.1.2013 19:00
:)
Avatar
Fugiczek
Redaktor
Avatar
Fugiczek:

Jen tak pro představu, základní funkce v Javě na řazení pole mi trvá 160ms a funkce na řazení kolekce 50ms při 50k slov na i5-2410M 2.30GHz.

 
Nahoru Odpovědět 21.1.2013 19:26
Avatar
TomBen
Redaktor
Avatar
TomBen:

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ě.

Nahoru Odpovědět 21.1.2013 21:49
Za posledních 200 miliónů let se nic zvláštního nestalo, akorát dinosauři vymřeli a opice se naučily programovat.
Avatar
Odpovídá na TomBen
Luboš Běhounek (Satik):

Kdyžtak mi napiš zprávou, jaký postup jsi použil, třeba jsme použili stejný :)

Nahoru Odpovědět 21.1.2013 21:55
:)
Avatar
TomBen
Redaktor
Avatar
Nahoru Odpovědět 21.1.2013 21:56
Za posledních 200 miliónů let se nic zvláštního nestalo, akorát dinosauři vymřeli a opice se naučily programovat.
Avatar
Odpovídá na TomBen
Luboš Běhounek (Satik):

Sakra, chlape, tebe je na ten Gamemaker skoda :)

Nahoru Odpovědět  +2 21.1.2013 22:14
:)
Avatar
TomBen
Redaktor
Avatar
Odpovídá na Luboš Běhounek (Satik)
TomBen:

Game Maker by si zasloužil víc takových a nebyl by to pak
takový ušmudlánek. 8-)

Nahoru Odpovědět 21.1.2013 22:16
Za posledních 200 miliónů let se nic zvláštního nestalo, akorát dinosauři vymřeli a opice se naučily programovat.
Avatar
Luboš Běhounek (Satik):

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 :)

Nahoru Odpovědět 21.1.2013 22:21
:)
Avatar
TomBen
Redaktor
Avatar
Odpovídá na Luboš Běhounek (Satik)
TomBen:

10M ... 111.45s
20M ... 222.82s

Při vysokých počtech asi narazím na hranice GM pro práci
s datovými strukturami a musel bych přepsat další vestavěné funkce.
Uvidíme, zkusím pak rozjet 500M, jestli se to nepodělá.

Nahoru Odpovědět 21.1.2013 22:53
Za posledních 200 miliónů let se nic zvláštního nestalo, akorát dinosauři vymřeli a opice se naučily programovat.
Avatar
Odpovídá na TomBen
Luboš Běhounek (Satik):

500 M asi ne, to nenacpes do pameti, pokud je vysledek z GM 32bit.

Ja v 32bit C++ muzu radit max tak 480M.

Nahoru Odpovědět 21.1.2013 23:11
:)
Avatar
Odpovídá na Luboš Běhounek (Satik)
Lukáš Hruda (Luckin):

Tak mě napadá otázka. Smí se řazení spojit s genrováním? Tzn, že se vygeneruje slovo a hned se zařadí na správný místo?

 
Nahoru Odpovědět 21.1.2013 23:23
Avatar
Odpovídá na Luboš Běhounek (Satik)
Lukáš Hruda (Luckin):

Škoda, to by otevřelo dost nových možností :D ...třeba použití mediánu jako pivot u quick sortu.

 
Nahoru Odpovědět 22.1.2013 0:04
Avatar
Odpovídá na Lukáš Hruda (Luckin)
Luboš Běhounek (Satik):

Nebo třeba rovnou pole vygenerovat seřazené :D

Nahoru Odpovědět 22.1.2013 0:17
:)
Avatar
Lukáš Hruda (Luckin):

Je tam podmínka že znaky a délka mají bejt náhodný, takže ho těžko vygenreueš už seřazený :D

 
Nahoru Odpovědět 22.1.2013 0:20
Avatar
Michael Olšavský:

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. :)

 
Nahoru Odpovědět 22.1.2013 19:30
Avatar
Odpovídá na Luboš Běhounek (Satik)
Lukáš Hruda (Luckin):

Tak jsem se u řazení dostal na následující čísla.

100 000 : 8 ms
1 000 000 : 50 - 55 ms
10 000 000 : 460 - 500 ms
100 000 000 : cca 4,8 s (ale generování trvá přes půl minuty)

Nic rychlejšího už mě nenapadá.

Editováno 23.1.2013 18:39
 
Nahoru Odpovědět 23.1.2013 18:39
Avatar
Odpovídá na Lukáš Hruda (Luckin)
Luboš Běhounek (Satik):

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.

Nahoru Odpovědět 23.1.2013 18:56
:)
Avatar
Odpovídá na Luboš Běhounek (Satik)
Lukáš Hruda (Luckin):

Poslal sem ti to i se zdrojákem. Myslim že kód pochopíš snadno.

 
Nahoru Odpovědět 23.1.2013 19:12
Avatar
Odpovídá na Lukáš Hruda (Luckin)
Luboš Běhounek (Satik):

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 :)

Nahoru Odpovědět 23.1.2013 19:29
:)
Avatar
Odpovídá na Luboš Běhounek (Satik)
Lukáš Hruda (Luckin):

Na sraz nejdu, ale celkem rád bych viděl tvuj algoritmus, můžeš mi ho poslat na mail? :)

 
Nahoru Odpovědět 23.1.2013 19:48
Avatar
Lukáš Hruda (Luckin):

Dík... moc se v tom nevyznam :D 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

Editováno 23.1.2013 20:50
 
Nahoru Odpovědět 23.1.2013 20:50
Avatar
Odpovídá na Luboš Běhounek (Satik)
Lukáš Hruda (Luckin):

Jinak musim uznat že to zadání je dost dobře vymyšlený.

 
Nahoru Odpovědět 23.1.2013 21:56
Avatar
Luboš Běhounek (Satik):

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 :D .

Nahoru Odpovědět  +1 23.1.2013 23:32
:)
Avatar
Odpovídá na Luboš Běhounek (Satik)
Lukáš Hruda (Luckin):

Taky bych sem moh pak hodit to svoje, sice to neni tak rychlý, ale je to kratší a jednodušší. :)

 
Nahoru Odpovědět  +1 23.1.2013 23:57
Avatar
Odpovídá na Luboš Běhounek (Satik)
Lukáš Hruda (Luckin):

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 :D

 
Nahoru Odpovědět 24.1.2013 16:22
Avatar
Odpovídá na Lukáš Hruda (Luckin)
Luboš Běhounek (Satik):

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í.

Nahoru Odpovědět 24.1.2013 18:35
:)
Avatar
Odpovídá na Luboš Běhounek (Satik)
Lukáš Hruda (Luckin):

Ta změna na char možná lehce pomohla, ale nijak zvlášť. Zkrácení na 4 znaky nepomohlo vůbec a ty řetězce nikde nenuluju, rovnou je přepisuju...

Ještě mě napadla jedna optimalizace, mělo by to ale jeden problém, ve výstupnim poli by všechny stejný řetězce měly stejnou adresu, tzn pokud by se jeden změnil, změnily by se všechny stejný. Navíc by to na rychlosti bylo znát jenom u velkých čísel, kde by bylo hodně řetězců stejných.

Editováno 24.1.2013 19:15
 
Nahoru Odpovědět 24.1.2013 19:11
Avatar
Lukáš Hruda (Luckin):

Edit 19:15 :
Navíc by to nešlo bez memory leaků. Správná dealokace paměti by hrozně moc snížila rychlost... :D

 
Nahoru Odpovědět 24.1.2013 19:18
Avatar
Odpovídá na Lukáš Hruda (Luckin)
Luboš Běhounek (Satik):

BTW přístup do pole counts nemáš thread-safe, když v jednu chvíli obě vlákna (při tom inkrementování) přistoupěj na stejný index, tak se taky může stát, že se počet zvýší celkově jen o jedničku.

Nahoru Odpovědět 24.1.2013 19:22
:)
Avatar
Odpovídá na Lukáš Hruda (Luckin)
Luboš Běhounek (Satik):

A ještě jednu docela velkou optimalizaci tam můžeš udělat.

Při výpisu si můžeš tu hodnotu cacheovat.
Když třeba se řetězec s id 123456 opakoval desetkrát, tak ty tam desetkrát ten řetězec vypočítáš z toho čísla. Přitom by stačilo si ho předvypočítat jednou a pak ho už jen použít.

EDIT: a nejlepší na tom je, že si ten řetězec můžeš uložit jako jeden int a ten tam vlepovat jedním přiřazením (mám to tak ve svém kódu).

Editováno 24.1.2013 19:27
Nahoru Odpovědět 24.1.2013 19:26
:)
Avatar
Odpovídá na Luboš Běhounek (Satik)
Lukáš Hruda (Luckin):

Na stejnej index se nikdy dostat nemůžou, kdyby ano, tak by se tam dostaly pokaždý a naopak by to tu hodnotu započítalo 2x. Každý vlákno má svojí půlku kterou projíždí, do tý druhý půlky se nikdy nedostane.
To s tim počítánim z jednoho čísla by právě šlo obejít tak, že bych jenom kopíroval pointer, pak mi tam ale zůstane halda nedealokovaný paměti.
Ta metoda s int mě nenapadla...

Editováno 24.1.2013 20:09
 
Nahoru Odpovědět 24.1.2013 20:08
Avatar
Odpovídá na Lukáš Hruda (Luckin)
Luboš Běhounek (Satik):

Číst ze stejnýho pole nemůžou, každý má svoji půlku, právěže ten problém je ale inkrementace hodnot v poli countArray, kde se to stát může.

Nahoru Odpovědět 24.1.2013 20:16
:)
Avatar
Odpovídá na Luboš Běhounek (Satik)
Lukáš Hruda (Luckin):

Máš pravdu, to bych měl nějak ošetřit.

 
Nahoru Odpovědět 24.1.2013 20:42
Avatar
Odpovídá na Lukáš Hruda (Luckin)
Luboš Běhounek (Satik):

buďto můžeš využít něčeho takovéhohle: http://msdn.microsoft.com/…s.85%29.aspx
(ale netuším, jaký to má vliv na rychlost)

Nebo třeba udělat si pro každé vlákno vlastní countArray a pak je nakonec sečíst (to zase můžeš udělat vícevláknově - jedno vlákno třeba horní půlku, druhé dolní)

Nahoru Odpovědět 24.1.2013 21:01
:)
Avatar
David Čápka
Tým ITnetwork
Avatar
Nahoru Odpovědět  +1 24.1.2013 21:04
Miluji svou práci a zdejší komunitu, baví mě se rozvíjet, děkuji každému členovi za to, že zde působí.
Avatar
Don
Člen
Avatar
Odpovídá na David Čápka
Don:

Já teda nevím, ale v pekle to začalo. Teď už to jde do nebes :D

 
Nahoru Odpovědět 24.1.2013 21:11
Avatar
Odpovídá na Luboš Běhounek (Satik)
Lukáš Hruda (Luckin):

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ášť.

 
Nahoru Odpovědět 24.1.2013 21:32
Avatar
Odpovídá na Lukáš Hruda (Luckin)
Luboš Běhounek (Satik):

Ano, takhle jsem to sčítání polí myslel :)

Nahoru Odpovědět 24.1.2013 21:41
:)
Avatar
Odpovídá na Luboš Běhounek (Satik)
Lukáš Hruda (Luckin):

Poslal sem ti na mail poslední verzi, víc zesložiťovat už to nebudu, mam na práci i jiný věci :D ...po pátku sem hodim tu původní verzi, tu co běžela na jednom vlákně.

 
Nahoru Odpovědět 24.1.2013 21:45
Avatar
Odpovídá na Lukáš Hruda (Luckin)
Luboš Běhounek (Satik):

Trva to porad stejne dlouho, mozna bys musel to pole znaku zarovnavat na ctverice misto na petice :D

Nahoru Odpovědět 24.1.2013 22:16
:)
Avatar
Odpovídá na Luboš Běhounek (Satik)
Lukáš Hruda (Luckin):

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. :D

 
Nahoru Odpovědět 24.1.2013 22:22
Avatar
Luboš Běhounek (Satik):

Ahoj, tak jsem tu (konečně) s výsledky.

Podmínky jsem upravil tak, aby se dal i na řazení řetězců použít counting sort, který má lineární složitost, takže hlavně u velkých množství slov je neskutečně rychlý. Pro svoje řešení jsem kvůli rychlosti zvolil C++.

Nejblíže se dostal Luckin, jehož (taktéž jednovláknová) C++ verze counting sortu u 10 000 000 slov trvala 290ms (moje 170ms).

Speciální ocenění získává TomBen, který, ač využívá GameMaker, také přišel na to, že se dá použít counting sort a sesortování 10 M slov mu trvalo 111 sekund, což se asi bude blížit limitům gamemakeru.

Tady je zdroják mé verze, kód je mírně komentován, kdyby jste měli nějaký dotaz nebo jste tam našli nějakou chybu, tak to tu prosím napište do komentářů.
http://www.itnetwork.cz/dev-lighter/65

Díky všem za účast, zapojilo se vás nakonec docela dost.
Myslíte, že byl rozsah tak akorát nebo byste dali na příště přednost něčemu většímu/menšímu?.

Nahoru Odpovědět 27.1.2013 21:48
:)
Avatar
Lukáš Hruda (Luckin):

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

 
Nahoru Odpovědět 27.1.2013 22:22
Avatar
Odpovídá na Luboš Běhounek (Satik)
Michael Olšavský:

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.

 
Nahoru Odpovědět 28.1.2013 8:02
Děláme co je v našich silách, aby byly zdejší diskuze co nejkvalitnější. Proto do nich také mohou přispívat pouze registrovaní členové. Pro zapojení do diskuze se přihlas. Pokud ještě nemáš účet, zaregistruj se, je to zdarma.

Zobrazeno 92 zpráv z 92.