NOVINKA: Získej 40 hodin praktických dovedností s AI – ZDARMA ke každému akreditovanému kurzu!
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í.
Avatar
David Hartinger
Vlastník
Avatar
David Hartinger: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
16.9.2013 16:40
New kid back on the block with a R.I.P
Avatar
Theodor Johnson
Tvůrce
Avatar
Odpovídá na David Hartinger
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
Avatar
Silvinios
Tvůrce
Avatar
Odpovídá na David Hartinger
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 Hartinger
Vlastník
Avatar
Odpovídá na Theodor Johnson
David Hartinger: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
New kid back on the block with a R.I.P
Avatar
David Hartinger
Vlastník
Avatar
Odpovídá na Silvinios
David Hartinger: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
New kid back on the block with a R.I.P
Avatar
David Hartinger
Vlastník
Avatar
Odpovídá na Theodor Johnson
David Hartinger: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
New kid back on the block with a R.I.P
Avatar
Theodor Johnson
Tvůrce
Avatar
Odpovídá na David Hartinger
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
Avatar
Silvinios
Tvůrce
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
Luboš Běhounek Satik
Tvůrce
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
16.9.2013 18:31
https://www.facebook.com/peasantsandcastles/
Avatar
Jakub Lásko[Saarix]
Tvůrce
Avatar
Odpovídá na David Hartinger
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
Tvůrce
Avatar
Odpovídá na David Hartinger
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
Avatar
Luboš Běhounek Satik
Tvůrce
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
https://www.facebook.com/peasantsandcastles/
Avatar
Jan Vargovský
Tvůrce
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
Michal Žůrek - misaz
Tvůrce
Avatar
Odpovídá na David Hartinger
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
16.9.2013 18:57
Avatar
Theodor Johnson
Tvůrce
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
Avatar
Silvinios
Tvůrce
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 Hartinger
Vlastník
Avatar
Odpovídá na Luboš Běhounek Satik
David 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 :)

Nahoru Odpovědět
16.9.2013 19:33
New kid back on the block with a R.I.P
Avatar
David Hartinger
Vlastník
Avatar
Odpovídá na Theodor Johnson
David Hartinger: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
New kid back on the block with a R.I.P
Avatar
Silvinios
Tvůrce
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
16.9.2013 19:54
Avatar
Jan Vargovský
Tvůrce
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
Tvůrce
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
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
16.9.2013 20:04
Avatar
Jan Vargovský
Tvůrce
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 Hartinger
Vlastník
Avatar
Odpovídá na Silvinios
David Hartinger: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
New kid back on the block with a R.I.P
Avatar
Jakub Lásko[Saarix]
Tvůrce
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
Tvůrce
Avatar
Odpovídá na David Hartinger
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
Tvůrce
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
Avatar
Kit
Tvůrce
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 Hartinger, 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
Michal Žůrek - misaz
Tvůrce
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
Avatar
Jakub Lásko[Saarix]
Tvůrce
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
Tvůrce
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
Avatar
Jakub Lásko[Saarix]
Tvůrce
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
Tvůrce
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
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
Tvůrce
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
Avatar
Michael Olšavský
Tvůrce
Avatar
Odpovídá na Jakub Lásko[Saarix]
Michael Olšavský:16.9.2013 20:35

Tohle asi neprojde :-D

 
Nahoru Odpovědět
16.9.2013 20:35
Avatar
Kit
Tvůrce
Avatar
Odpovídá na Jakub Lásko[Saarix]
Kit:16.9.2013 20:37

Já tam tu chybu vidím a David Hartinger 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
Michael Olšavský
Tvůrce
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
Jakub Lásko[Saarix]
Tvůrce
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 Hartinger
Vlastník
Avatar
Odpovídá na Kit
David 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.

Nahoru Odpovědět
16.9.2013 20:43
New kid back on the block with a R.I.P
Avatar
Michael Olšavský
Tvůrce
Avatar
Odpovídá na David Hartinger
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
Tvůrce
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
16.9.2013 22:43
Vlastnosti objektů by neměly být veřejné. A to ani prostřednictvím getterů/setterů.
Avatar
Michael Olšavský
Tvůrce
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
Jakub Lásko[Saarix]
Tvůrce
Avatar
Odpovídá na Michael Olšavský
Jakub Lásko[Saarix]:17.9.2013 12:33

Dost dobrý výkon :-)

Nahoru Odpovědět
17.9.2013 12:33
Časem je vše možné.
Avatar
Jan Vargovský
Tvůrce
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
Michael Olšavský
Tvůrce
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
Tvůrce
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
adas
Tvůrce
Avatar
adas: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 Hartinger
Vlastník
Avatar
Odpovídá na adas
David Hartinger:17.9.2013 16:38

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

Nahoru Odpovědět
17.9.2013 16:38
New kid back on the block with a R.I.P
Avatar
adas
Tvůrce
Avatar
Odpovídá na David Hartinger
adas: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
Michael Olšavský
Tvůrce
Avatar
Odpovídá na David Hartinger
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
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 50 zpráv z 110.