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í.
Přejít k původní otázce
Avatar
Jan Vargovský
Tvůrce
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

 
Odpovědět
17.9.2013 18:00
Avatar
Libor Šimo (libcosenior)
Tvůrce
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
Michael Olšavský
Tvůrce
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ý
Tvůrce
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
Michael Olšavský
Tvůrce
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
Libor Šimo (libcosenior)
Tvůrce
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 Hartinger
Vlastník
Avatar
Odpovídá na adas
David Hartinger:17.9.2013 18:24

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

Nahoru Odpovědět
17.9.2013 18:24
New kid back on the block with a R.I.P
Avatar
Jan Vargovský
Tvůrce
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
Tvůrce
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
Michael Olšavský
Tvůrce
Avatar
Odpovídá na David Hartinger
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
Michael Olšavský
Tvůrce
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
Tvůrce
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
Luboš Běhounek Satik
Tvůrce
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 hru do magickeho leta, Luckin uz pise pribeh... :D

Nahoru Odpovědět
17.9.2013 18:41
https://www.facebook.com/peasantsandcastles/
Avatar
Jan Vargovský
Tvůrce
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 Hartinger
Vlastník
Avatar
Odpovídá na Jan Vargovský
David Hartinger: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
New kid back on the block with a R.I.P
Avatar
Jan Vargovský
Tvůrce
Avatar
Odpovídá na David Hartinger
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 Hartinger
Vlastník
Avatar
Odpovídá na Jan Vargovský
David Hartinger:17.9.2013 18:46

Dobře, dejme to na pole intů.

Nahoru Odpovědět
17.9.2013 18:46
New kid back on the block with a R.I.P
Avatar
Lukáš Hruda
Tvůrce
Avatar
Odpovídá na Luboš Běhounek Satik
Lukáš Hruda: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
Michael Olšavský
Tvůrce
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
Michael Olšavský
Tvůrce
Avatar
Odpovídá na Lukáš Hruda
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
Lukáš Hruda
Tvůrce
Avatar
Odpovídá na David Hartinger
Lukáš Hruda: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
17.9.2013 18:53
Avatar
Lukáš Hruda
Tvůrce
Avatar
Odpovídá na Michael Olšavský
Lukáš Hruda: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ý
Tvůrce
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
Michael Olšavský
Tvůrce
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
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
Michael Olšavský
Tvůrce
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
18.9.2013 15:58
Live long and prosper.
Avatar
davidomil
Člen
Avatar
Odpovídá na David Hartinger
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ý
Tvůrce
Avatar
Odpovídá na davidomil
Jan Vargovský:19.9.2013 11:58

Buď tady a nebo sdracovi do zpráv.

 
Nahoru Odpovědět
19.9.2013 11:58
Avatar
David Hartinger
Vlastník
Avatar
Odpovídá na davidomil
David Hartinger:19.9.2013 11:58

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

Nahoru Odpovědět
19.9.2013 11:58
New kid back on the block with a R.I.P
Avatar
Libor Šimo (libcosenior)
Tvůrce
Avatar
Odpovídá na David Hartinger
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ý
Tvůrce
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
Libor Šimo (libcosenior)
Tvůrce
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
19.9.2013 20:39
Aj tisícmíľová cesta musí začať jednoduchým krokom.
Avatar
Lukáš Hruda
Tvůrce
Avatar
Lukáš Hruda: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
adas
Tvůrce
Avatar
Odpovídá na David Hartinger
adas: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 Hartinger
Vlastník
Avatar
David Hartinger:22.9.2013 18:28

Makám na tom.

Nahoru Odpovědět
22.9.2013 18:28
New kid back on the block with a R.I.P
Avatar
Jan Vargovský
Tvůrce
Avatar
Odpovídá na David Hartinger
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 Hartinger
Vlastník
Avatar
David Hartinger: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
New kid back on the block with a R.I.P
Avatar
Michal Žůrek - misaz
Tvůrce
Avatar
Odpovídá na David Hartinger
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
Avatar
Jan Vargovský
Tvůrce
Avatar
Odpovídá na David Hartinger
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 Hartinger
Vlastník
Avatar
David Hartinger: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
New kid back on the block with a R.I.P
Avatar
Kit
Tvůrce
Avatar
Odpovídá na David Hartinger
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 Hartinger
Vlastník
Avatar
David Hartinger:22.9.2013 20:09

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

Nahoru Odpovědět
22.9.2013 20:09
New kid back on the block with a R.I.P
Avatar
Kit
Tvůrce
Avatar
Odpovídá na David Hartinger
Kit:22.9.2013 20:15

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

Nahoru Odpovědět
22.9.2013 20:15
Vlastnosti objektů by neměly být veřejné. A to ani prostřednictvím getterů/setterů.
Avatar
David Hartinger
Vlastník
Avatar
David Hartinger:22.9.2013 20:16

Vypadá to tedy, že z testu vyšel nejlépe Lukáš Hruda, 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
22.9.2013 20:16
New kid back on the block with a R.I.P
Avatar
David Hartinger
Vlastník
Avatar
Odpovídá na Kit
David Hartinger:22.9.2013 20:17

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

Nahoru Odpovědět
22.9.2013 20:17
New kid back on the block with a R.I.P
Avatar
Lukáš Hruda
Tvůrce
Avatar
Odpovídá na David Hartinger
Lukáš Hruda:22.9.2013 20:25

Děkuji :)

 
Nahoru Odpovědět
22.9.2013 20:25
Avatar
Michael Olšavský
Tvůrce
Avatar
Odpovídá na David Hartinger
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
Michael Olšavský
Tvůrce
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
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.