Vydělávej až 160.000 Kč měsíčně! Akreditované rekvalifikační kurzy s garancí práce od 0 Kč. Více informací.
Hledáme nové posily do ITnetwork týmu. Podívej se na volné pozice a přidej se do nejagilnější firmy na trhu - Více informací.

Diskuze: Soutěž v programování :)

Aktivity
Avatar
TomBen
Tvůrce
Avatar
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:21.1.2013 22:14

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

Nahoru Odpovědět
21.1.2013 22:14
https://www.facebook.com/peasantsandcastles/
Avatar
TomBen
Tvůrce
Avatar
Odpovídá na Luboš Běhounek Satik
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. 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:21.1.2013 22:21

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
https://www.facebook.com/peasantsandcastles/
Avatar
TomBen
Tvůrce
Avatar
Odpovídá na Luboš Běhounek Satik
TomBen:21.1.2013 22:53

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:21.1.2013 23:11

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
https://www.facebook.com/peasantsandcastles/
Avatar
Lukáš Hruda
Tvůrce
Avatar
Odpovídá na Luboš Běhounek Satik
Lukáš Hruda:21.1.2013 23:23

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
Nahoru Odpovědět
22.1.2013 0:02
https://www.facebook.com/peasantsandcastles/
Avatar
Lukáš Hruda
Tvůrce
Avatar
Odpovídá na Luboš Běhounek Satik
Lukáš Hruda:22.1.2013 0:04

Š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
Luboš Běhounek Satik:22.1.2013 0:17

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

Nahoru Odpovědět
22.1.2013 0:17
https://www.facebook.com/peasantsandcastles/
Avatar
Lukáš Hruda
Tvůrce
Avatar
Lukáš Hruda:22.1.2013 0:20

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ý:22.1.2013 19:30

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
Lukáš Hruda
Tvůrce
Avatar
Odpovídá na Luboš Běhounek Satik
Lukáš Hruda:23.1.2013 18:39

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

Nahoru Odpovědět
23.1.2013 18:56
https://www.facebook.com/peasantsandcastles/
Avatar
Lukáš Hruda
Tvůrce
Avatar
Odpovídá na Luboš Běhounek Satik
Lukáš Hruda:23.1.2013 19:12

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

Nahoru Odpovědět
23.1.2013 19:29
https://www.facebook.com/peasantsandcastles/
Avatar
Lukáš Hruda
Tvůrce
Avatar
Odpovídá na Luboš Běhounek Satik
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? :)

 
Nahoru Odpovědět
23.1.2013 19:48
Avatar
Nahoru Odpovědět
23.1.2013 20:26
https://www.facebook.com/peasantsandcastles/
Avatar
Lukáš Hruda
Tvůrce
Avatar
Lukáš Hruda:23.1.2013 20:50

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
Lukáš Hruda
Tvůrce
Avatar
Odpovídá na Luboš Běhounek Satik
Lukáš Hruda:23.1.2013 21:56

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:23.1.2013 23:32

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
23.1.2013 23:32
https://www.facebook.com/peasantsandcastles/
Avatar
Lukáš Hruda
Tvůrce
Avatar
Odpovídá na Luboš Běhounek Satik
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šší. :)

 
Nahoru Odpovědět
23.1.2013 23:57
Avatar
Lukáš Hruda
Tvůrce
Avatar
Odpovídá na Luboš Běhounek Satik
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 :D

 
Nahoru Odpovědět
24.1.2013 16:22
Avatar
Odpovídá na Lukáš Hruda
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í.

Nahoru Odpovědět
24.1.2013 18:35
https://www.facebook.com/peasantsandcastles/
Avatar
Lukáš Hruda
Tvůrce
Avatar
Odpovídá na Luboš Běhounek Satik
Lukáš Hruda:24.1.2013 19:11

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
Tvůrce
Avatar
Lukáš Hruda:24.1.2013 19:18

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
Luboš Běhounek Satik:24.1.2013 19:22

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
https://www.facebook.com/peasantsandcastles/
Avatar
Odpovídá na Lukáš Hruda
Luboš Běhounek Satik:24.1.2013 19:26

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
https://www.facebook.com/peasantsandcastles/
Avatar
Lukáš Hruda
Tvůrce
Avatar
Odpovídá na Luboš Běhounek Satik
Lukáš Hruda:24.1.2013 20:08

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
Luboš Běhounek Satik:24.1.2013 20:16

Čí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
https://www.facebook.com/peasantsandcastles/
Avatar
Lukáš Hruda
Tvůrce
Avatar
Odpovídá na Luboš Běhounek Satik
Lukáš Hruda:24.1.2013 20:42

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
Luboš Běhounek Satik:24.1.2013 21:01

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
https://www.facebook.com/peasantsandcastles/
Avatar
David Hartinger
Vlastník
Avatar
Odpovídá na Luboš Běhounek Satik
David Hartinger:24.1.2013 21:04

Tady to vede do pekel koukám... :D

Nahoru Odpovědět
24.1.2013 21:04
You are the greatest project you will ever work on.
Avatar
Don
Člen
Avatar
Odpovídá na David Hartinger
Don:24.1.2013 21:11

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
Lukáš Hruda
Tvůrce
Avatar
Odpovídá na Luboš Běhounek Satik
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ášť.

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

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

Nahoru Odpovědět
24.1.2013 21:41
https://www.facebook.com/peasantsandcastles/
Avatar
Lukáš Hruda
Tvůrce
Avatar
Odpovídá na Luboš Běhounek Satik
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 :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
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 :D

Nahoru Odpovědět
24.1.2013 22:16
https://www.facebook.com/peasantsandcastles/
Avatar
Lukáš Hruda
Tvůrce
Avatar
Odpovídá na Luboš Běhounek Satik
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. :D

 
Nahoru Odpovědět
24.1.2013 22:22
Avatar
Luboš Běhounek Satik:27.1.2013 21:48

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
https://www.facebook.com/peasantsandcastles/
Avatar
Lukáš Hruda
Tvůrce
Avatar
Lukáš Hruda:27.1.2013 22:22

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

 
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 42 zpráv z 92.