Avatar
David Čápka
Tým ITnetwork
Avatar
David Čápka:

Ahoj, v pravidelné minisoutěži Machr na C# .NET o placku a samolepky si tento týden zkusíme naprogramovat shuffle. Shuffle je metoda, které přijde na vstupu pole a ona ho pozmění tak, aby v něm byly původní prvky zcela náhodně přeházené. Půjde o soutěž v rychlosti. Odevzdává se jen kód metody, kterou si pojmenujte podle vaší přezdívky. Níže je uvedená moje metoda s poněkud naivním algoritmem:

UPDATE zadání: můžete místo generického pole brát pole intů.

public void SdracoShuffle<T>(T[] input)
{
        Random r = new Random();
        for (int i = 0; i < input.Length / 2; i++)
        {
                int a = r.Next(input.Length);
                int b = r.Next(input.Length);
                var c = input[a];
                input[a] = input[b];
                input[b] = c;
        }
}

Vaše metody vyzkouším na různě velkých polích a změřím jak jsou rychlé. Můžete používat vlákna. Z výsledků sestavím tabulku. Autor nejrychlejšího algoritmu získává ocenění v podobě placky a také do svého profilu. Soutěž je omezena samozřejmě jen na C# .NET. Budu to překládat asi pod .NET 3.5.

Čas si dejme do 22.9. do 18:00.

Editováno 17.9.2013 18:47
Odpovědět  +1 16.9.2013 16:40
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
Theodor Johnson
Redaktor
Avatar
Odpovídá na David Čápka
Theodor Johnson:

Zkusil jsem si to jen tak nahrubo kolik by asi při normálním zpřeházení vyšel výsledek, ale na 20 intů to vrací počet tiků v rozmezí 100k - 200k, jak to chceš hodnotit když využití procesoru různě stoupá a kolísá?

Nahoru Odpovědět 16.9.2013 17:49
Přecházím na "Cross-Platform Development"
Avatar
Silvinios
Redaktor
Avatar
Odpovídá na David Čápka
Silvinios:

Co přesně znamená, že původní prvky jsou zcela náhodně přeházené?

 
Nahoru Odpovědět 16.9.2013 17:55
Avatar
David Čápka
Tým ITnetwork
Avatar
Odpovídá na Theodor Johnson
David Čápka:

Výkonové testy se dělají na velkém množství náhodně generovaných dat. Když změříš seřazení milionu polí a ještě uděláš průměr z několika měření, je to přesné. Samozřejmě si musíš vypnout spuštěné aplikace a měřit to na stejném stroji.

Nahoru Odpovědět 16.9.2013 18:13
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
David Čápka
Tým ITnetwork
Avatar
Odpovídá na Silvinios
David Čápka:

Že to pole vypadá vždy jinak a je proházené po celé své délce. Můžeme tu filosofovat o tom, co to znamená náhodně a dojdeme k tomu, že náhodné není nikdy nic.

Nahoru Odpovědět 16.9.2013 18:14
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
David Čápka
Tým ITnetwork
Avatar
Odpovídá na Theodor Johnson
David Čápka:

Ještě dodám že je nutné to pole uchovávat, tedy předgenerovat si je třeba do listu. Jinak VM udělá optimalizaci a tu metodu třeba ani nespustí, protože se její výsledek nepoužije.

Nahoru Odpovědět 16.9.2013 18:16
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
Theodor Johnson
Redaktor
Avatar
Odpovídá na David Čápka
Theodor Johnson:

Aha, tak to asi na mém stroji ne, to bych se těch milionů nedočkal :D radši budu trochu realista a maximálně tak 10k

Nahoru Odpovědět 16.9.2013 18:24
Přecházím na "Cross-Platform Development"
Avatar
Silvinios
Redaktor
Avatar
Silvinios:

Omlouvám se, ale stále příliš nerozumím zadání.

Řekněme, že vstupem je pole a1, a2, ..., an.
Můj program vrátí pole b1, b2, ... bn.

Aby můj program vyhověl zadání "pole vypadá vždy jinak", musí platit a[i]!=b[i] pro nějaký index i. Je to tak?

 
Nahoru Odpovědět 16.9.2013 18:26
Avatar
Odpovídá na Silvinios
Luboš Běhounek (Satik):

Myslím, že pokud třeba v poli o 100 prvcích bude náhodou jeden prvek na stejném místě, tak se vůbec nic neděje, tohle bych nehlídal, jde asi hlavně o to, aby pořadí bylo po promíchání opravdu (pseudo)náhodné.

Nahoru Odpovědět  +2 16.9.2013 18:31
:)
Avatar
Odpovídá na David Čápka
Jakub Lásko[Saarix]:

Tak nad tím teď přemýšlím a něco jsem vyplodil, nevím zda se pletu, ale to může být tak variabilní a dosáhnout různých výsledků?

Nahoru Odpovědět 16.9.2013 18:34
Časem je vše možné.
Avatar
Theodor Johnson
Redaktor
Avatar
Odpovídá na David Čápka
Theodor Johnson:

Jetšě se chci zeptat, je nějáké minimum kolik ta metoda musí zvládnout? Protože jsem zkoušel 100M a vyhodilo mi to chybu "Out of memory"

Nahoru Odpovědět 16.9.2013 18:35
Přecházím na "Cross-Platform Development"
Avatar
Luboš Běhounek (Satik):

Dal bych třeba nějaké pravidlo, třeba že o nové pozici každého prvku musí nějak rozhodnout metoda Next() třídy Random apod., aby byla u všech řešení ta náhodnost stejná.

Nahoru Odpovědět 16.9.2013 18:46
:)
Avatar
Jan Vargovský
Redaktor
Avatar
Odpovídá na Theodor Johnson
Jan Vargovský:

100M mi prošlo vpohodě a doba kolem 5s :D

Editováno 16.9.2013 18:54
 
Nahoru Odpovědět 16.9.2013 18:54
Avatar
Odpovídá na David Čápka
Michal Žůrek (misaz):

škoda že nemůžeme dělat v ASM, to bych se ho i naučil.

Nahoru Odpovědět  -2 16.9.2013 18:57
Nesnáším {}, proto se jim vyhýbám.
Avatar
Theodor Johnson
Redaktor
Avatar
Odpovídá na Jan Vargovský
Theodor Johnson:

Asi mám málo operační paměti, nebo jsem zvolil špatný způsob, jinak mám 10M asi za 4 vteřiny

Nahoru Odpovědět 16.9.2013 19:07
Přecházím na "Cross-Platform Development"
Avatar
Silvinios
Redaktor
Avatar
Odpovídá na Luboš Běhounek (Satik)
Silvinios:

To by bylo fajn, nicméně ani příklad ze zadání toto nesplňuje.

 
Nahoru Odpovědět 16.9.2013 19:23
Avatar
David Čápka
Tým ITnetwork
Avatar
Odpovídá na Luboš Běhounek (Satik)
David Čápka:

Já bych to asi nechal, když si někdo udělá svůj random a bude fungovat, tak je to jeho plus :)

Nahoru Odpovědět 16.9.2013 19:33
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
David Čápka
Tým ITnetwork
Avatar
Odpovídá na Theodor Johnson
David Čápka:

To metoda přece neovlivňuje, do pole se vejde tolik, kolik máš paměti. Určitě budu dělat pole s tisíci, možná desetitisíci prvky. Delší ale asi ne.

Nahoru Odpovědět 16.9.2013 19:35
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
Silvinios
Redaktor
Avatar
Odpovídá na Jakub Lásko[Saarix]
Silvinios:

Také nerozumím, o co vlastně jde...
Navrhnout vlastní náhodný generátor, který bude rychlejší než Random?
Napsat algoritmus, který prohází pouze část pole (viz příklad v zadání pro pole liché délky) a doufat, že bude o něco rychlejší než řešení ostatních?
Procvičit se v psaní vícevláknových aplikací?

 
Nahoru Odpovědět  -1 16.9.2013 19:54
Avatar
Jan Vargovský
Redaktor
Avatar
Odpovídá na Silvinios
Jan Vargovský:

To je na Tobě jak to implementuješ. Rozhodující je čas.

 
Nahoru Odpovědět 16.9.2013 19:55
Avatar
Silvinios
Redaktor
Avatar
Odpovídá na Jan Vargovský
Silvinios:

Rozhodující by mělo být, aby program dělal přesně to, co má dělat. Pokud se neřekne, co to má dělat, není možné napsat program.

Pokud bych upravil podmínku v příkladu takto:

for (int i = 0; i < input.Length / 3; i++)

splnil bych zadání nebo ne?

 
Nahoru Odpovědět  ±0 16.9.2013 20:03
Avatar
vitamin
Člen
Avatar
vitamin:

Najvecsi problem vidim v tom ze zadanie neriesi kvalitu nahodneho generatora a ani kvalitu prehadzania.

 
Nahoru Odpovědět  +1 16.9.2013 20:04
Avatar
Jan Vargovský
Redaktor
Avatar
Odpovídá na Silvinios
Jan Vargovský:

Klidně nepoužívej žádný cyklus. Prostě máš náhodně uspořádat pole, aby v tom nebyla logika. ( = aby jsi logicky nemohl rozshufflovat to pole zpátky)

 
Nahoru Odpovědět 16.9.2013 20:06
Avatar
David Čápka
Tým ITnetwork
Avatar
Odpovídá na Silvinios
David Čápka:

Zadání je aby to pole vypadalo náhodně přeházené. Představ si to třeba jako že mícháš karty. S mým algoritmem se teoreticky může stát že pole bude vypadat úplně stejně a je korektní. Jde o to, aby to ve většině případů fungovalo. Občas něco může zůstat kde to je, nemělo by se ale stát, že ti to bude ve většině případů shufflovat jen polovinu pole a druhá bude stejná. Nebo že tam bude nějaký hodně viditelný pattern.

Editováno 16.9.2013 20:10
Nahoru Odpovědět 16.9.2013 20:09
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
Odpovídá na Theodor Johnson
Jakub Lásko[Saarix]:

Zajimavé, 5M mám skoro ihned (ani ne 1s), ale jakmile navrším data na 50M, tak to už je jiná písnička... :(

Nahoru Odpovědět 16.9.2013 20:22
Časem je vše možné.
Avatar
Silvinios
Redaktor
Avatar
Odpovídá na David Čápka
Silvinios:

Jasně, ale kde je ta hranice mezi tím, co vypadá náhodně a co už ne? Co už je hodně viditelný pattern a co ne?

 
Nahoru Odpovědět 16.9.2013 20:23
Avatar
Theodor Johnson
Redaktor
Avatar
Odpovídá na Jakub Lásko[Saarix]
Theodor Johnson:

Může to být i mým výkonem pc

Nahoru Odpovědět 16.9.2013 20:24
Přecházím na "Cross-Platform Development"
Avatar
Kit
Redaktor
Avatar
Odpovídá na Silvinios
Kit:

Statisticky by průměrně jeden prvek pole měl zůstat na svém původním místě. Někdy žádný, jindy třeba pět. Není to tak těžké udělat. Algoritmus, který použil David Čápka, je úmyslně chybný.

Nahoru Odpovědět 16.9.2013 20:24
Vlastnosti objektů by neměly být veřejné. A to ani prostřednictvím getterů/setterů.
Avatar
Odpovídá na Silvinios
Michal Žůrek (misaz):

prostě projeď všechno nebo vynechej jen vyjmečné, ne že vynecháš každý čtvrtý. Nijak se z toho nevymotávej.

Nahoru Odpovědět 16.9.2013 20:24
Nesnáším {}, proto se jim vyhýbám.
Avatar
Odpovídá na Kit
Jakub Lásko[Saarix]:

V sdracově příkladu nevidím chybu, protože šplňuje to že se položky náhodně přehází.

Editováno 16.9.2013 20:28
Nahoru Odpovědět 16.9.2013 20:28
Časem je vše možné.
Avatar
Theodor Johnson
Redaktor
Avatar
Odpovídá na Jakub Lásko[Saarix]
Theodor Johnson:

To jo, ale 2× použít random není nejlepší, random.next je dost pomalá metoda

Nahoru Odpovědět 16.9.2013 20:30
Přecházím na "Cross-Platform Development"
Avatar
Odpovídá na Theodor Johnson
Jakub Lásko[Saarix]:

To jsem nevěděl, ale tak potom trochu pokulhávám v tom jak vygenerovat náhodný shuffle, protože bez Random to bude asi těžší

Editováno 16.9.2013 20:33
Nahoru Odpovědět 16.9.2013 20:33
Časem je vše možné.
Avatar
Kit
Redaktor
Avatar
Odpovídá na Silvinios
Kit:

Zkus si jako výstup udělat obrázek třeba 1000×1000 bodů. Pokud budu považovat a[0], a[1], a[2], ... jako hodnoty na indexech 0, 1, 2, ..., tak si jako dvojice [x, y] nakresli bod na souřadnice

[a[0], a[1]]
[a[1], a[2]]
[a[2], a[3]]
atd.

Testuji na tom generátory náhodných čísel. Měla by vzniknout "hvězdná obloha". Pokud na ní budeš nacházet mohutné galaxie, je to špatně.

Nahoru Odpovědět  +1 16.9.2013 20:34
Vlastnosti objektů by neměly být veřejné. A to ani prostřednictvím getterů/setterů.
Avatar
Theodor Johnson
Redaktor
Avatar
Odpovídá na Jakub Lásko[Saarix]
Theodor Johnson:

Random není zakázaný, ale jde to udělat i s jedním použitím random.next

Nahoru Odpovědět 16.9.2013 20:34
Přecházím na "Cross-Platform Development"
Avatar
Kit
Redaktor
Avatar
Odpovídá na Jakub Lásko[Saarix]
Kit:

Já tam tu chybu vidím a David Čápka o ní zcela jistě ví a dal ji tam záměrně. Máme za úkol vymyslet algoritmus, který bude správný.

Nahoru Odpovědět 16.9.2013 20:37
Vlastnosti objektů by neměly být veřejné. A to ani prostřednictvím getterů/setterů.
Avatar
Odpovídá na Kit
Michael Olšavský:

Je to opravdu chyba? Spíše to algoritmus omezuje v rychlosti. Alespoň podle toho co vidím já.

 
Nahoru Odpovědět 16.9.2013 20:41
Avatar
Odpovídá na Theodor Johnson
Jakub Lásko[Saarix]:

Teď jsem docílil 1,2s na 100M záznamech, ale problém je že se tam objevil vzorec :(

Nahoru Odpovědět 16.9.2013 20:42
Časem je vše možné.
Avatar
David Čápka
Tým ITnetwork
Avatar
Odpovídá na Kit
David Čápka:

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.

Nahoru Odpovědět 16.9.2013 20:43
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
Odpovídá na David Čápka
Michael Olšavský:

Není zde zadáno to, kolik se z pole musí projet. Určil bych to alespoň na polovinu. Jinak je výsledek malo promychany. Zároveň si myslím, ze to bude spis soutěž o nejrychlejší random metodě, ale kdo ví. Třeba někdo vymyslí něco revolučního.

 
Nahoru Odpovědět 16.9.2013 22:09
Avatar
Kit
Redaktor
Avatar
Odpovídá na Michael Olšavský
Kit:

Pole projíždím vždy 1×. Mám tak jistotu, že pole je správně promícháno.

Nahoru Odpovědět  +3 16.9.2013 22:43
Vlastnosti objektů by neměly být veřejné. A to ani prostřednictvím getterů/setterů.
Avatar
Odpovídá na Jakub Lásko[Saarix]
Michael Olšavský:

Jsem na 600ms(400 - 800) pro 100M, bez vzorce! 8-) :-D

 
Nahoru Odpovědět 17.9.2013 8:51
Avatar
Nahoru Odpovědět 17.9.2013 12:33
Časem je vše možné.
Avatar
Jan Vargovský
Redaktor
Avatar
Odpovídá na Michael Olšavský
Jan Vargovský:

Jak můžeš mít odchylku 1/3 času ?

 
Nahoru Odpovědět 17.9.2013 15:04
Avatar
Odpovídá na Jan Vargovský
Michael Olšavský:

Jsou to milisekundy. Navíc závisí dost na tom, co mám spuštěné za procesy. Když zrovna oteviram photoshop, asi to bude vice + release mode oproti normálnímu spuštění bez VS

 
Nahoru Odpovědět 17.9.2013 15:36
Avatar
Kit
Redaktor
Avatar
Odpovídá na Michael Olšavský
Kit:

Při měření se snažím udržovat stálé podmínky, aby měření bylo co nejpřesnější. Nejhorší a nejlepší měření škrtám, zbytek průměruji nebo vyberu nejlepší.

Nahoru Odpovědět 17.9.2013 15:47
Vlastnosti objektů by neměly být veřejné. A to ani prostřednictvím getterů/setterů.
Avatar
Ondřej Hanák
Redaktor
Avatar
Ondřej Hanák:
public static void Sidecek123Shuffle<T>(this IList<T> list)
{
    Random rng = new Random();
    int n = list.Count;
    while (n > 1) {
        n--;
        int k = rng.Next(n + 1);
        T value = list[k];
        list[k] = list[n];
        list[n] = value;
    }
}
 
Nahoru Odpovědět 17.9.2013 16:10
Avatar
David Čápka
Tým ITnetwork
Avatar
Odpovídá na Ondřej Hanák
David Čápka:

Tu metodu jsem dal do zadání proto, abyste použili její hlavičku ;-)

Nahoru Odpovědět  -1 17.9.2013 16:38
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
Ondřej Hanák
Redaktor
Avatar
Odpovídá na David Čápka
Ondřej Hanák:

Aha ty to mas bodobne, tak pocky, vymyslim neco jineho.
Jsem si nevsiml :(

 
Nahoru Odpovědět 17.9.2013 17:47
Avatar
Odpovídá na David Čápka
Michael Olšavský:

Ono jde něco jiného? Já to mám taky podobné, jen jsem si udělal svůj Random. :D Je to profláklý algoritmus (Fisher-Yates shuffle), už od roku 1964 se nevymyslelo nic lepšího :-D Má to časovou náročnost O(n). Co jiného by jsi chtěl? :-D 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ý.

 
Nahoru Odpovědět 17.9.2013 17:53
Avatar
Jan Vargovský
Redaktor
Avatar
Odpovídá na Michael Olšavský
Jan Vargovský:

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

 
Nahoru Odpovědět 17.9.2013 18:00
Avatar
Libor Šimo (libcosenior):
public void LibcoShuffle<T>(T[] input)
{
       Random r = new Random();
       for (int i = 0; i < input.Length; i++)
       {
               int a = r.Next(input.Length);
               if (i != a)
               {
                    var b = input[i];
                    input[i] = input[a];
                    input[a] = b;
               }
       }
}
Editováno 17.9.2013 18:03
Nahoru Odpovědět 17.9.2013 18:03
Aj tisícmíľová cesta musí začať jednoduchým krokom.
Avatar
Odpovídá na Jan Vargovský
Michael Olšavský:

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 :-D při kopírování zpět z IEnumerable do pole.

 
Nahoru Odpovědět 17.9.2013 18:07
Avatar
Jan Vargovský
Redaktor
Avatar
Odpovídá na Michael Olšavský
Jan Vargovský:

No LINQ určitě rychlejší nebude. Každopádně testovat se to bude na číslech 103 - 104 (říkalo se tady v diskuzi)

 
Nahoru Odpovědět 17.9.2013 18:10
Avatar
Odpovídá na Jan Vargovský
Michael Olšavský:

Myslíš? Možná máš pravdu. Pouze 103? To bude na tiky procesoru nebo co? To už bude dost nepřesné měření, řekl bych.

 
Nahoru Odpovědět 17.9.2013 18:16
Avatar
Odpovídá na Libor Šimo (libcosenior)
Libor Šimo (libcosenior):

Neviem či to takto pôjde na c#, možno ano.

public void LibcoShuffle<T>(T[] input)
{
       Random r = new Random();
       for (int i = 0; i < input.Length; i += 2)
       {
               int a = r.Next(input.Length);
               i != a ? var b = input[i], input[i] = input[a], input[a] = b : 0;
       }
}
Nahoru Odpovědět 17.9.2013 18:24
Aj tisícmíľová cesta musí začať jednoduchým krokom.
Avatar
David Čápka
Tým ITnetwork
Avatar
Odpovídá na Ondřej Hanák
David Čápka:

Ne, myslel jsem, že máš jinou hlavičku než je v zadání.

Nahoru Odpovědět  +3 17.9.2013 18:24
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
Jan Vargovský
Redaktor
Avatar
Odpovídá na Michael Olšavský
Jan Vargovský:

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

 
Nahoru Odpovědět 17.9.2013 18:25
Avatar
Silvinios
Redaktor
Avatar
Silvinios:
public void SilviniosShuffle<T>(T[] input)
{
        // Fisher–Yates shuffle
        // Linear congruential generator: r = (a * r + c) % m, m = 2^31, a=1103515245, c=12345
        int r = (int) DateTime.Now.Ticks;
        for (int i = input.Length - 1; i > 0; i--) {
                r = (1103515245 * r + 12345) & 0x7FFFFFFF;
                int j = r % (i + 1);
                T c = input[j];
                input[j] = input[i];
                input[i] = c;
        }
}
 
Nahoru Odpovědět 17.9.2013 18:29
Avatar
Odpovídá na David Čápka
Michael Olšavský:

Nevadí, že mám naprosto "blbou" metodu random? Jakože není vůbec vymakaná, ale náhodná čísla to jsou :-D 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ší.

 
Nahoru Odpovědět 17.9.2013 18:33
Avatar
Odpovídá na Silvinios
Michael Olšavský:

Jsem si říkal, kde jsi sakra vytáhl ta čísla a on je to standart Céčka pro rand() :-D 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.

 
Nahoru Odpovědět 17.9.2013 18:37
Avatar
Silvinios
Redaktor
Avatar
Odpovídá na Michael Olšavský
Silvinios:

Určitě se dá vymyslet něco horšího. Třeba, že některá uspořádání jsou více pravděpodobná, než jiná...

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

Ja se asi nezucastnim, o vikendu nejsem u PC a do patecni pulnoci musime dodelat s Lukáš Hruda (Luckin) hru do magickeho leta, Luckin uz pise pribeh... :D

Nahoru Odpovědět 17.9.2013 18:41
:)
Avatar
Jan Vargovský
Redaktor
Avatar
Odpovídá na Michael Olšavský
Jan Vargovský:

Random metodu asi nevytvoříš rychleji a v unsafe kódu toho moc nevytvoříš s generikou :)

 
Nahoru Odpovědět 17.9.2013 18:41
Avatar
David Čápka
Tým ITnetwork
Avatar
Odpovídá na Jan Vargovský
David Čápka:

Pokud je generika takový problém, tak ji můžeme dát pryč :)

Nahoru Odpovědět 17.9.2013 18:44
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
Jan Vargovský
Redaktor
Avatar
Odpovídá na David Čápka
Jan Vargovský:

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

 
Nahoru Odpovědět 17.9.2013 18:46
Avatar
David Čápka
Tým ITnetwork
Avatar
Odpovídá na Jan Vargovský
David Čápka:

Dobře, dejme to na pole intů.

Nahoru Odpovědět 17.9.2013 18:46
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
Odpovídá na Luboš Běhounek (Satik)
Lukáš Hruda (Luckin):

Příběh už mám :D Teď vymýšlím atributy kouzlům a nepřátelům.

 
Nahoru Odpovědět 17.9.2013 18:47
Avatar
Odpovídá na Jan Vargovský
Michael Olšavský:

Jenže ona je vážně hrozně blbá :-D 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.

Editováno 17.9.2013 18:51
 
Nahoru Odpovědět 17.9.2013 18:50
Avatar
Odpovídá na David Čápka
Lukáš Hruda (Luckin):

Myslím, že pro úkol jako je tento by bylo vhodnější C++ nebo C. Tam by ta generika nebyla takový problém, C++ má šablony, v C se to dá nasimulovat pomocí typedef nebo maker.

 
Nahoru Odpovědět  +1 17.9.2013 18:53
Avatar
Odpovídá na Michael Olšavský
Lukáš Hruda (Luckin):

Začali jsme brzo, ale měli jsme moc dlouhou pauzu :D

 
Nahoru Odpovědět 17.9.2013 18:53
Avatar
Jan Vargovský
Redaktor
Avatar
Odpovídá na Michael Olšavský
Jan Vargovský:

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

 
Nahoru Odpovědět 17.9.2013 21:03
Avatar
Odpovídá na Jan Vargovský
Michael Olšavský:

Já už to zkoušel několikrát. Vždy jsem byl sklamán rozdíly mezi Céčkem a C#. DOvolí toho několikanásobně méně.

 
Nahoru Odpovědět 17.9.2013 21:21
Avatar
davidomil
Člen
Avatar
davidomil:

Tak jsem to vytáhl na 350ms na 100M položek :D

Nahoru Odpovědět  +1 18.9.2013 13:57
Live long and prosper.
Avatar
davidomil
Člen
Avatar
Odpovídá na davidomil
davidomil:

Ještě jsem to stáhnul o 50ms :D

Nahoru Odpovědět 18.9.2013 14:19
Live long and prosper.
Avatar
davidomil
Člen
Avatar
Odpovídá na Michael Olšavský
davidomil:

Běží to na 1.7GHz i5-3317U. Ale vlákna stejně nepoužívám, rozsekat to na části zabere spoustu času.

Nahoru Odpovědět  +1 18.9.2013 15:58
Live long and prosper.
Avatar
davidomil
Člen
Avatar
Odpovídá na David Čápka
davidomil:

Možná to je stupidní otázka, ale kam mám odevzdat tu metodu? Díky

Nahoru Odpovědět 19.9.2013 11:57
Live long and prosper.
Avatar
Jan Vargovský
Redaktor
Avatar
Odpovídá na davidomil
Jan Vargovský:

Buď tady a nebo sdracovi do zpráv.

 
Nahoru Odpovědět  +3 19.9.2013 11:58
Avatar
David Čápka
Tým ITnetwork
Avatar
Odpovídá na davidomil
David Čápka:

Buď jí pošli sem nebo mně do zpráv. :)

Nahoru Odpovědět 19.9.2013 11:58
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
Odpovídá na David Čápka
Libor Šimo (libcosenior):

Môj posledný pokus. Podmienka je pole väčšie ako 255 prvkov.

public void LibcoShuffle<T>(T[] input)
{
    Random r = new Random((int)DateTime.Now.Ticks);
    Byte[] b = new Byte[input.Length];
    r.NextBytes(b);
    for (int i = 0; i < input.Length; i += 2)
    {
        var c = input[i];
        input[i] = input[b[i]];
        input[b[i]] = c;
    }
}
Nahoru Odpovědět 19.9.2013 20:07
Aj tisícmíľová cesta musí začať jednoduchým krokom.
Avatar
Jan Vargovský
Redaktor
Avatar
Odpovídá na Libor Šimo (libcosenior)
Jan Vargovský:

Zadání se změnilo na pole intů :) (jde to ofc i na to tvoje, ale bude to krapet pomalejší)

Editováno 19.9.2013 20:28
 
Nahoru Odpovědět 19.9.2013 20:27
Avatar
Odpovídá na Jan Vargovský
Libor Šimo (libcosenior):
public void LibcoShuffle(int[] input)
{
    Random r = new Random((int)DateTime.Now.Ticks);
    Byte[] b = new Byte[input.Length];
    r.NextBytes(b);
    for (int i = 0; i < input.Length; i += 2)
    {
        int c = input[i];
        input[i] = input[b[i]];
        input[b[i]] = c;
    }
}
Nahoru Odpovědět  +1 19.9.2013 20:39
Aj tisícmíľová cesta musí začať jednoduchým krokom.
Avatar
Lukáš Hruda (Luckin):

Zde je můj pokus. Nefunguje pro pole obsahující záporná čísla a není ideální pro míchání malých polí a polí obsahujících pouze jedničky a nuly.

static void Shuffle(int[] arr)
{
    Random rnd = new Random();
    int size = arr.Length;
    int num = rnd.Next() % (size / 2 - 1) + 1;
    for (int i = 0; i < size; i++)
    {
        int pos = (arr[i] + num + i * 2) % size;
        int temp = arr[i];
        arr[i] = arr[pos];
        arr[pos] = temp;
    }
}
 
Nahoru Odpovědět 21.9.2013 17:57
Avatar
Ondřej Hanák
Redaktor
Avatar
Odpovídá na David Čápka
Ondřej Hanák:

To minulé nepočítej.
Jsem to předělal na toto:

static void Sidecek123Shuffle(int[] array)
{
Random r = new Random();
for (int i = array.Length - 1; i > 0; i--)
{
int index = r.Next(i);
int tmp = array[index];
array[index] = array[i];
array[i] = tmp;
   }
}
Editováno 22.9.2013 13:15
 
Nahoru Odpovědět 22.9.2013 13:14
Avatar
David Čápka
Tým ITnetwork
Avatar
David Čápka:

Makám na tom.

Nahoru Odpovědět  +2 22.9.2013 18:28
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
Jan Vargovský
Redaktor
Avatar
Odpovídá na David Čápka
Jan Vargovský:

To moje nepočítej, našel jsem lepší způsob, ale nějak jsem nebyl doma :D

 
Nahoru Odpovědět 22.9.2013 19:01
Avatar
David Čápka
Tým ITnetwork
Avatar
David Čápka:

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

Nahoru Odpovědět 22.9.2013 19:26
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
Odpovídá na David Čápka
Michal Žůrek (misaz):

radši se jdi naladit na podzimní atmosféru.

Nahoru Odpovědět 22.9.2013 19:35
Nesnáším {}, proto se jim vyhýbám.
Avatar
Jan Vargovský
Redaktor
Avatar
Odpovídá na David Čápka
Jan Vargovský:
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 ? :)

 
Nahoru Odpovědět 22.9.2013 19:41
Avatar
David Čápka
Tým ITnetwork
Avatar
David Čápka:

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.

Nahoru Odpovědět 22.9.2013 19:42
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
Kit
Redaktor
Avatar
Odpovídá na David Čápka
Kit:

Podle výsledků bych to jednoznačně viděl na to, že vede Michael Olšavský

Nahoru Odpovědět 22.9.2013 19:51
Vlastnosti objektů by neměly být veřejné. A to ani prostřednictvím getterů/setterů.
Avatar
David Čápka
Tým ITnetwork
Avatar
David Čápka:

Test náhodnosti ukázal, že většina řešení moc náhodná není :)

Nahoru Odpovědět  +1 22.9.2013 20:09
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
Kit
Redaktor
Avatar
Odpovídá na David Čápka
Kit:

No co? je to jak u Pentia. Blbě, ale rychle :)

Nahoru Odpovědět  ±0 22.9.2013 20:15
Vlastnosti objektů by neměly být veřejné. A to ani prostřednictvím getterů/setterů.
Avatar
David Čápka
Tým ITnetwork
Avatar
David Čápka:

Vypadá to tedy, že z testu vyšel nejlépe Lukáš Hruda (Luckin), získává tedy Machra na C# :P 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.

Nahoru Odpovědět  ±0 22.9.2013 20:16
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
David Čápka
Tým ITnetwork
Avatar
Odpovídá na Kit
David Čápka:

Starý, ale pořád dobrý :D

Nahoru Odpovědět 22.9.2013 20:17
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
Odpovídá na David Čápka
Michael Olšavský:

Sakra. To je dost trapný :D 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... :D doufam, ze priste to vyjde. Omlouvam se, za klamavy aloritmus. Nahodnost pentia nebyla schvalne.

 
Nahoru Odpovědět 22.9.2013 20:49
Avatar
Odpovídá na Michael Olšavský
Michael Olšavský:

Tomu už ani nevěřím... :/ :-D Chce to víc kontrolovat. Přitom sem to opravil za pár minut........­.............­... :@ :@

 
Nahoru Odpovědět 22.9.2013 20:51
Avatar
Kit
Redaktor
Avatar
Odpovídá na David Čápka
Kit:

Přitom jediný, kdo to má opravdu správně, je Ondřej Hanák

Nahoru Odpovědět  +1 22.9.2013 20:55
Vlastnosti objektů by neměly být veřejné. A to ani prostřednictvím getterů/setterů.
Avatar
Odpovídá na Kit
Michael Olšavský:

Také tomu odpovídá čas. Vidíš čeho jsou někteří soutěžící schopni dopustit :-D

 
Nahoru Odpovědět 22.9.2013 20:56
Avatar
davidomil
Člen
Avatar
Odpovídá na Michael Olšavský
davidomil:

Byly tam blbe chyby. Já jsem posílal dnes ráno ještě opravenou poslední verzi, která byla už dostatečně náhodná, jen jsem nějak přehlédl, že to padá při poli menším než 10 prvků. Proto ji tam David Čápka asi nedal. Škoda.

Nahoru Odpovědět 22.9.2013 21:39
Live long and prosper.
Avatar
David Čápka
Tým ITnetwork
Avatar
Odpovídá na davidomil
David Čápka:

Dával jsem tam tu poslední co mi přišla, byly 3.

Nahoru Odpovědět 23.9.2013 9:08
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
davidomil
Člen
Avatar
Odpovídá na David Čápka
davidomil:

Tak to je zajímavé. Protože sice byly 3, ale ta poslední tam jasně nebyla. Už proto, že ta při poli menším jak 11 položkách spadla.

Nahoru Odpovědět 23.9.2013 10:03
Live long and prosper.
Avatar
David Čápka
Tým ITnetwork
Avatar
Odpovídá na davidomil
David Čápka:

Aha, já totiž aktualizoval jen tu metodu (která je stejná) a ne kód, co jí volá. Jestli však padá, tak bych to stejně nebyl schopen porovnat.

Nahoru Odpovědět 23.9.2013 10:18
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
davidomil
Člen
Avatar
Odpovídá na David Čápka
davidomil:

V pohodě. Zkusím to příště :D

Nahoru Odpovědět 23.9.2013 10:32
Live long and prosper.
Avatar
Ondřej Hanák
Redaktor
Avatar
Odpovídá na David Čápka
Ondřej Hanák:

A kdo teda získal placku ?

Editováno 23.9.2013 19:49
 
Nahoru Odpovědět 23.9.2013 19:48
Avatar
David Čápka
Tým ITnetwork
Avatar
Nahoru Odpovědět 23.9.2013 20:08
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
David Čápka
Tým ITnetwork
Avatar
David Čápka:

Doplnil jsem do testu ještě novou metodu od Jan Vargovský a metodu Theodor Johnsona, na kterého jsem zapomněl :`

Nahoru Odpovědět 24.9.2013 12:11
Miluji svou práci a zdejší komunitu, baví mě se rozvíjet, děkuji každému členovi za to, že zde působí.
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 110 zpráv z 110.