Diskuze: Machr na C# .NET - Nejrychlejší shuffle
Theodor Johnson:16.9.2013 18:24
Aha, tak to asi na mém stroji ne, to bych se těch milionů nedočkal 
radši budu trochu realista a
maximálně tak 10k
Jan Vargovský:16.9.2013 18:54
100M mi prošlo vpohodě a doba kolem 5s
David Čápka Hartinger:16.9.2013 19:33
Já bych to asi nechal, když si někdo udělá svůj random a bude fungovat,
tak je to jeho plus 
Jakub Lásko[Saarix]:16.9.2013 20:22
Zajimavé, 5M mám skoro ihned (ani ne 1s), ale jakmile navrším data na
50M, tak to už je jiná písnička... 
Jakub Lásko[Saarix]:16.9.2013 20:42
Teď jsem docílil 1,2s na 100M záznamech, ale problém je že se tam
objevil vzorec
David Čápka Hartinger:16.9.2013 20:43
To už je asi moc do detailů Neplánuji to takhle zkoumat. Budu asi jen porovnávat jak se to
liší od původního pole + nějaký test stejného pole a porovnání
výsledků mezi sebou.
Michael Olšavský:17.9.2013 8:51
Jsem na 600ms(400 - 800) pro 100M, bez vzorce! 
David Čápka Hartinger:17.9.2013 16:38
Tu metodu jsem dal do zadání proto, abyste použili její hlavičku 
adas:17.9.2013 17:47
Aha ty to mas bodobne, tak pocky, vymyslim neco jineho.
Jsem si nevsiml
Michael Olšavský:17.9.2013 17:53
Ono jde něco jiného? Já to mám taky podobné, jen jsem si udělal svůj
Random. Je to profláklý
algoritmus (Fisher-Yates shuffle), už od roku 1964 se nevymyslelo nic lepšího
Má to časovou
náročnost O(n). Co jiného by jsi chtěl? Možná změnit pole na něco
jiného, ale pod tuhle časovou náročnost se myslím ani nedá dostat, pokud
chci manipulovat s celým polem. Tím, že projdu jen část, se samozřejmě
dostanu níže a můžu použít multi-threading, ale samotný algoritmus
zůstane z větší části nezměněný.
Jan Vargovský:17.9.2013 18:00
Jo, bude to spíše o štěstí než takhle včera jsem nad tím přemýšlel,
zkoušel a googloval snad 5 hodin a nakonec jsem zůstal u toho, co jsem
vymyslel jako první
Michael Olšavský:17.9.2013 18:07
Koukám na to. Jsem na tom podobně. Když ten algoritmus snad napadne
každého. Nebo alespoň já ho tak měl ještě předtím, než jsem ho našel.
Sice jsou asi tři druhy, ale rozdíl v tom moc nevidím. Spíš to bude o tom,
kdo má nejchytřejší Random a jak kdo vyřeší ty operace s čísly. Ještě
jsem zkoušel LINQ, je to několikanásobně rychlejší, ale OutOfMemory při kopírování zpět z
IEnumerable do pole.
Jan Vargovský:17.9.2013 18:25
Mi to neříkej celkově mi
tenhle úkol přijde trošku divný, kdyby v tom nebyla ta generika tak by se to
dalo možná nějak uspěchat
Michael Olšavský:17.9.2013 18:33
Nevadí, že mám naprosto "blbou" metodu random? Jakože není vůbec
vymakaná, ale náhodná čísla to jsou A je to zatím nejrychlejší
řešení. Ještě jsem našel něco podobného jako Silvinios, ale to jsem 1.
nevymyslel a 2. to bylo pomalejší.
Michael Olšavský:17.9.2013 18:37
Jsem si říkal, kde jsi sakra vytáhl ta čísla a on je to standart Céčka
pro rand() Ale pěkná
práce. U mě zatím nejrychlejší. Schválně, co vymyslí Luboš Běhounek Satik. To
bude zase síla. Už se těším.
Luboš Běhounek Satik:17.9.2013 18:41
Ja se asi nezucastnim, o vikendu nejsem u PC a do patecni pulnoci musime
dodelat s Lukáš Hruda hru do magickeho leta, Luckin uz pise pribeh...
Jan Vargovský:17.9.2013 18:41
Random metodu asi nevytvoříš rychleji a v unsafe kódu toho moc
nevytvoříš s generikou
David Čápka Hartinger:17.9.2013 18:44
Pokud je generika takový problém, tak ji můžeme dát pryč
Jan Vargovský:17.9.2013 18:46
No omezil bych to na nějaký daný typ, protože já fakt googloval snad 4
hodiny různé způsoby jak se dá dostat nějak níže a optimalizovat takhle,
ale nic jsem nenašel - a v IL to psát opravdu nebudu
Lukáš Hruda:17.9.2013 18:47
Příběh už mám Teď
vymýšlím atributy kouzlům a nepřátelům.
Michael Olšavský:17.9.2013 18:50
Jenže ona je vážně hrozně blbá taková odvozená, ale
zároveň náhodná. Generuje to nicméně docela čisté mapy (beztvaré), tak
to snad nebude problém. O unsafe kódu jsem také přemýšlel, ale C# ho
spíše "nedoporučuje" a v některých případech jeho použití i zpomaluje
kód.
Lukáš Hruda:17.9.2013 18:53
Začali jsme brzo, ale měli jsme moc dlouhou pauzu
Jan Vargovský:17.9.2013 21:03
Toto je právě příklad, kde to reálně zkusíš já v C# nikdy s unsafe nepracoval,
tak jsem se "těšil" že si to zkusím a vylepším své znalosti a místo toho
jsem se akorát nasral, že u generiky to nejde
Jan Vargovský:19.9.2013 20:27
Zadání se změnilo na pole intů (jde to ofc i na to tvoje, ale bude to krapet pomalejší)
Jan Vargovský:22.9.2013 19:01
To moje nepočítej, našel jsem lepší způsob, ale nějak jsem nebyl doma
Předběžné výsledky jsou následující (viz screenshot) a velmi různé
pro různá pole. Pracuji ještě na testu pro míchaná pole. Také chci zkusit
jestli to opravdu shuffluje. Nevím, jestli to dnes stihnu vyhlásit
Jan Vargovský:22.9.2013 19:41
private static void PakoShuffle(int[] input)
{
Random r = new Random();
int n, t;
for (int i = input.Length - 1; i > 0; i--)
{
n = r.Next(5);
t = input[n];
input[n] = input[i];
input[i] = t;
}
}Můžeš zkusit toto ? byl tam improve skoro 350% oproti tomu předtím.
Kdyby se ti nechtělo, hodil bys mi zdroják a já bych si to pustil u sebe ?
Proměřil jsem i náhodná pole. Vypadá to na bitvu mezi Brisingrem a Davidomilem. Snad jsem tam někde neudělal chybu, jsem docela unavený. Zdroják prozatimního testu je zde: http://www.itnetwork.cz/dev-lighter/208
Jdu se kouknout jak vám to kluci prohazuje.
Vypadá to tedy, že z testu vyšel nejlépe Lukáš Hruda, získává tedy
Machra na C# 
Druhý je
Silvinios. Metody Brisingra a Davidomila mi nějak nedělaly to, co měly. Pro
případ přikládám celý zdroják testů: http://www.itnetwork.cz/dev-lighter/209 .
Luckinovu adresu prosím x do PM.
Michael Olšavský:22.9.2013 20:49
Sakra. To je dost trapný a to sem tomu algoritmu tak veril... Stacilo pritom pridat jednu
nahodnou navic... A ten cas by se skoro nezvedl. A vubec. mel jsem to nechat na
svem prvnim pokusu. Vypada to, ze by to s tim casem nebylo tak spatne, kdyz to
davidomilovi take nefunguje. Mam na tyhle machry teda stesti... doufam, ze priste to vyjde.
Omlouvam se, za klamavy aloritmus. Nahodnost pentia nebyla schvalne.
Michael Olšavský:22.9.2013 20:51
Tomu už ani nevěřím... :/ Chce to víc kontrolovat. Přitom sem to opravil za pár
minut........................ 
Michael Olšavský:22.9.2013 20:56
Také tomu odpovídá čas. Vidíš čeho jsou někteří soutěžící
schopni dopustit
Doplnil jsem do testu ještě novou metodu od Jan Vargovský a metodu
Theodor Johnsona, na kterého jsem zapomněl 
Zobrazeno 110 zpráv z 110.