Avatar
David Čápka
Tým ITnetwork
Avatar
David Čápka:16.9.2013 16:40

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:16.9.2013 17:49

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:16.9.2013 17:55

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:16.9.2013 18:13

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:16.9.2013 18:14

Ž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:16.9.2013 18:16

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:16.9.2013 18:24

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:16.9.2013 18:26

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):16.9.2013 18:31

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]:16.9.2013 18:34

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:16.9.2013 18:35

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):16.9.2013 18:46

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ý:16.9.2013 18:54

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):16.9.2013 18:57

š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:16.9.2013 19:07

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:16.9.2013 19:23

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

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:16.9.2013 19:35

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:16.9.2013 19:54

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ý:16.9.2013 19:55

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:16.9.2013 20:03

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:16.9.2013 20:04

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ý:16.9.2013 20:06

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:16.9.2013 20:09

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]: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... :(

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:16.9.2013 20:23

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:16.9.2013 20:24

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:16.9.2013 20:24

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):16.9.2013 20:24

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]:16.9.2013 20:28

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:16.9.2013 20:30

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]:16.9.2013 20:33

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:16.9.2013 20:34

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:16.9.2013 20:34

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

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ý:16.9.2013 20:41

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]:16.9.2013 20:42

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

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ý:16.9.2013 22:09

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:16.9.2013 22:43

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ý:17.9.2013 8:51

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ý:17.9.2013 15:04

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ý:17.9.2013 15:36

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:17.9.2013 15:47

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:17.9.2013 16:10
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:17.9.2013 16:38

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:17.9.2013 17:47

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

 
Nahoru Odpovědět 17.9.2013 18:00
Avatar
Libor Šimo (libcosenior):17.9.2013 18:03
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ý: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 :-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ý:17.9.2013 18:10

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ý:17.9.2013 18:16

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):17.9.2013 18:24

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:17.9.2013 18:24

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

 
Nahoru Odpovědět 17.9.2013 18:25
Avatar
Silvinios
Redaktor
Avatar
Silvinios:17.9.2013 18:29
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ý: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 :-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ý:17.9.2013 18:37

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:17.9.2013 18:39

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):17.9.2013 18:41

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ý:17.9.2013 18:41

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:17.9.2013 18:44

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

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

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):17.9.2013 18:47

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ý:17.9.2013 18:50

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 Lukáš Hruda (Luckin)
Michael Olšavský:17.9.2013 18:52

To začínáte tedy brzy :D

 
Nahoru Odpovědět 17.9.2013 18:52
Avatar
Odpovídá na David Čápka
Lukáš Hruda (Luckin):17.9.2013 18:53

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):17.9.2013 18:53

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

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

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:18.9.2013 13:57

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:18.9.2013 14:19

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

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

(Y) jaky máš HW?

 
Nahoru Odpovědět 18.9.2013 15:44
Avatar
davidomil
Člen
Avatar
Odpovídá na Michael Olšavský
davidomil:18.9.2013 15:58

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:19.9.2013 11:57

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ý:19.9.2013 11:58

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:19.9.2013 11:58

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):19.9.2013 20:07

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ý: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ší)

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):19.9.2013 20:39
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):21.9.2013 17:57

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:22.9.2013 13:14

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:22.9.2013 18:28

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ý:22.9.2013 19:01

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:22.9.2013 19:26

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):22.9.2013 19:35

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

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

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:22.9.2013 19:51

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:22.9.2013 20:09

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:22.9.2013 20:15

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:22.9.2013 20:16

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:22.9.2013 20:17

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ý:22.9.2013 20:49

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ý:22.9.2013 20:51

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:22.9.2013 20:55

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ý:22.9.2013 20:56

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:22.9.2013 21:39

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:23.9.2013 9:08

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:23.9.2013 10:03

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:23.9.2013 10:18

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:23.9.2013 10:32

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:23.9.2013 19:48

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
Odpovídá na Ondřej Hanák
David Čápka:23.9.2013 20:08

Placku získal Luckin.

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:24.9.2013 12:11

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.