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:
Program se zeptá na počet slov
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.
Spustí se časovač, který měří dobu výpočtu
Spustí se řadící funkce
Spočítá se a vypíše celkový čas řazení
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í
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?
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ý.
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
.
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
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
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.
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
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í.
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.
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ů
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ý.
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?
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ě.
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á.
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
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í.
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.
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.
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).
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...
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í)
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ě.
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.
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?.
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.