[C#]generování náhodných čísel bez opakování

C++, C#, Visual Basic, Delphi, Perl a ostatní

Moderátor: Moderátoři Živě.cz

Odeslat příspěvekod themrmaros 23. 5. 2013 10:36

Zdravím, mám takový problém. Lámu si hlavu nad tím jak mám napsat jeden program. Přesně zadání je takové:

Načti délku pole, vytvoř jej a naplň náhodnými čísly rozsahu 1-velikostpole tak, aby se žádné z čísel neopakovalo dvakrát.

Vymyslel jsem kód přidaný níže a program funguje, ale s tím problém že to přesto generuje dvě a více stejných čísel, prosím o radu už jsem vyzkoušel snad všechno co mě napadlo:

Obrázek Obrázek
themrmaros
Kolemjdoucí

Odeslat příspěvekod Wikan 23. 5. 2013 10:52

Vygeneruješ číslo - zkontroluješ jestli už ho nemáš - pokud ano, vygeneruješ další - vložíš ho tam.
A tam je ten problém, co když už tam je i to druhé vygenerované číslo?
A porovnávat čísla tím, že je převedeš na string, je docela prasárna.
Wikan
Moderátor
Uživatelský avatar

Odeslat příspěvekod JirkaVejrazka 23. 5. 2013 11:10

Pri takovemto zadani zadna nahodna cisla generovat nemusis. Zkus ti to rucne (treba na papire nebo v Excelu) pro pole delky pet nebo deset a pak se poradne podivej na vysledek.
JirkaVejrazka
Mírně pokročilý

Odeslat příspěvekod PeterKE 23. 5. 2013 11:45

Napln to bole cislami zaradom (=> nebudeš mať žiadne duplicity) a potom cez neho chod položku po položke a pri každej položke si nechaj vygenerovať náhodné číslo v rozsahu dlžky pola a obsah sucasnej pozície a obsah na vygenerovanej pozícii zamen.

Snad je to zrozumitelne a snad sa to da povazovať za náhodné.

A navyše môžeš to pole takto "premiešať" ľubovoľne veľa krát..
PeterKE
Junior

Odeslat příspěvekod Mike.M 23. 5. 2013 12:04

Co ta naplnit pole postupně 1,2,3,4-x a pak jen to jen promichat.
Mike.M
Mírně pokročilý
Uživatelský avatar

Odeslat příspěvekod Nargon 23. 5. 2013 12:10

Generování náhodných čísel tak aby se neopakovali lze jedině tak, že v cyklu stále dokola generuješ náhodné číslo dokud se netrefíš do toho čísla co tam není.
Tobě tam chybí ten cyklus. Ty vygeneruješ jedno náhodné číslo, zkontroluješ zda tam už není. Pokud tam je vygeneruješ druhé náhodné číslo a to tam zapíšeš (ale už nezkontroluješ zda i tohle to druhé číslo tam náhodou není)

Ovšem tohle zmíněné řešení je vhodné jen když je velice malá pravděpodobnost kolize dvou náhodně generovaných čísel (tj máš vygenerovat třeba 10 čísel z intervalu 0..100, ale čím více čísel z toho intervalu musíš vyplnit tím je toto řešení horší. Může se dostat až do "téměř nekonečné smyčky". Představ si že máš vygenerovat 1 milion takto náhodných čísel do 1 milionu. A máš už skoro všechny, jen ti chybí posledních 5 čísel. A než ten generátor náhodně vyplodí to jedno číslo co tam můžeš zadat, tak můžeš čekat třeba hodinu, nebo i pár dní.

Pro tyhle situace, kdy máš vygenerovat 10 čísel bez opakování z intervalu 0..9, je nejlepší řešení je nacpat do pole od začátku tj: 0,1,2,3,4,5,6,7,8,9 a následně toto pole náhodně zamíchat. Vygeneruješ dvojici indexů a prohodíš dva prvky na těch indexech. Napr vygeneruješ 3 a 5 a tyhle prvky prohodíš. Dostaneš: 0,1,2,5,4,3,6,7,8,9. A tohle opakuješ tolikrát jak hodně to chceš promíchat. Třeba 5x délka pole. Tj pro tenhle příklad vygeneruješ 50 dvojic náhodných indexů a ty prvky prohodíš.
Desktop: Ryzen 7 1800X (3.95GHz, 1.35V), Asus Crosshair VI Hero, 16GB DDR4 Ram (3200MHz), 128GB SSD + 3TB HDD, Nvidia GTX 1080
Notebook: Asus UL50VT 15.6" (SU7300@1.7GHz, 4GB ram, 500GB HDD, Intel GMA 4500MHD + nVidia G210M, dlouha vydrz cca 7+ hod)
Nargon
Moderátor

Odeslat příspěvekod themrmaros 23. 5. 2013 19:06

Promícháváním ten program udělat nemohu. Musí tam být to ta metoda Random, aby mi to uznali. Napadlo mě napsat for cyklus naplnit to pole náhodnými čísly a v něm další for cyklus, který by to pole projízděl a v případě že už tam to číslo je tak bude generovat nové tak dlouho dokud nevygeneruje takové které tam není, ale nevím jak na to.
themrmaros
Kolemjdoucí

Odeslat příspěvekod Wikan 23. 5. 2013 19:10

Promíchávání je přece náhodné, takže tam Random mít budeš.
Co konkrétně nevíš?
Wikan
Moderátor
Uživatelský avatar

Odeslat příspěvekod themrmaros 23. 5. 2013 19:17

Byl tady nápad naplnit to pole od 1-velikostpole a pak to promíchat. A já tam právě potřebuji ty čísla generovat náhodně a poté bych tam dal další for cyklus který by to projížděl, ale nevím jak ho mám napsat aby pokračoval furt do té doby než vygeneruje to číslo které v tom poli ještě není a poté se přesunul k dalšímu i-tému prvku v poli. Nevím jak na ten druhý for cyklus. Jinak už mě vážně nic nenapadá jak by se to dalo napsat.
themrmaros
Kolemjdoucí

Odeslat příspěvekod gandor 23. 5. 2013 19:20

Dalsie trocha lepsie riesenie je vytvorit si dane pole kam vkladas (zatial nic neplnis) vysledok. Toto pole je dobre inicializovat nejakou hodnotou, ktora sa tam nemoze vyskytnut (-1, NULL ak ide o pointre, pripadne dlzka pola+1)
Potom for-cyklom generovat vzdy nahodne cislo v uzavretom intervale <0, (velkost pola - iteracia generovaneho prvku)> - toto cislo ti hovori o pozicii noveho prvku.
Ale miesto toho, aby si dane cislo priamo umiestnil na pole, tak odpocitavas od nultej pozicie, daneho pola.
Pokial, uz v danom policku bol nejaky prvok umiestneny, tak od vygenerovaneho cisla odpocitas 1. V opacnom pripade sa posunies o dalsi prvok. Ked vygenerovane cislo dosiahne 0, tak do daneho pola umiestnis cislo iteracie (vonkajsiej iteracie - to znamena, na zaciatku bude pole obsahovat "niekde" cislo 0, potom 0,1 atd)....

Vyhoda tohto algoritmu je, ze ma zlozitost O(N^2) (takze ani 1 000 000 prvkov nebude riesit niekolko hodin) a vytvorena postupnost je tak nahodna, ako mas nahodny generator nahodnych cisiel.
Ten priklad s naplnenim pola a miesanim prvkov v nom je bud pomalsi, alebo nezanechava vskutku nahodne cisla (je vyssia pravdepodobnost, ze na napriklad 3. pozicii v poly ostane cislo 2 (indexacia od nuly), lebo mozno generator nevygeneroval zamenenie tohto prvku)...

Existuju ale aj lepsie riesenia...

-- 23. 5. 2013 20:26 --

K zamiesaniu pola - najskvor si BEZ NAHODNOSTI napln pole od 0 po dlzka pola-1. Ma vzniknut postupnost - ziadna nahodnost... Toto je prva oddelena cast.
Nasledne v druhej casti X krat vygenerujes 2 nahodne cisla. Tieto cisla ti urcia indexy pola - napriklad ak sa ti vygeneruje 3 a 7, vies ze musis zamenit obsah pola v prvku 3 s obsahom pola v prvku 7. Takze po prvej zamene by si mohol mat vysledok 0127456389...
No a to dane X by malo byt "dost velke". Minimalne o velkosti pola - ale to je nedostatocne minimum...
Ked sa zamyslis, da sa dany algoritmus potom aj vylepsit. Ale ak nechces, tak kludne pouzi aj len "dostatocne velke X". Napriklad 100-nasobok velkosti pola alebo este viac a pozry na vysledok. Predpokladam, ze od profaka by si nedostal nejak vyrazne menej bodov...
gandor
Mírně pokročilý

Odeslat příspěvekod PeterKE 23. 5. 2013 20:26

re gandor: "Nasledne v druhej casti X krat vygenerujes 2 nahodne cisla." - ja som vyššie navrhoval, aby to prvé číslo na výmenu nebolo náhodne ale aby sa prešlo postupne po všetkých pozíciach a až druhe by sa generovalo náhodne. Takto máš istotu že už pri jednom prechode každé jedno bolo ovplyvnené náhodou, aj ked to negarantuje že nebudú čísla ktoré neostanú na svojom mieste (napr číslo 6 na 6-tej pozícii)
PeterKE
Junior

Odeslat příspěvekod Nargon 23. 5. 2013 20:30

Pokud to mermomocí chceš takhle řešit a generovat to náhodné pole, tak ti to teda napíšu:
Kód: Vybrat vše
Random r = new Random();
for (int i = 0; i < pole.Length; i++)
{
    int tmp = r.Next(1, pole.Length + 1);
    while (pole.Contains(tmp)) tmp = r.Next(1, pole.Length + 1);
    pole[i] = tmp;
}

Ale tohle je ŠPATNÝ přístup, pro nějakých cca 100 000 prvků (a více) toho pole, to může počítat několik dní a stejně to ten výsledek nemusí dopočítat. Pokud ti tohle učitel uzná, tak by měl jít učit něco jiného než programování.

Opravdu jediný správný postup pro zadání typu: "chci výsledek s X náhodnýmí čísly z intervalu <Y,Y+X>, kde se čísla nebudou opakovat", je ten že ty čísla "vyrobíš" tak jak jdou po sobě. A pak je náhodně promícháš. Při tomto postupu máš jistotu že opravdu ten výsledek vygeneruješ. Ten kód co jsem ti napsal výše ti ten výsledek nemusí vypočítat ani do doby, kdy zanikne vesmír.
Desktop: Ryzen 7 1800X (3.95GHz, 1.35V), Asus Crosshair VI Hero, 16GB DDR4 Ram (3200MHz), 128GB SSD + 3TB HDD, Nvidia GTX 1080
Notebook: Asus UL50VT 15.6" (SU7300@1.7GHz, 4GB ram, 500GB HDD, Intel GMA 4500MHD + nVidia G210M, dlouha vydrz cca 7+ hod)
Nargon
Moderátor

Odeslat příspěvekod pucmeloudek 23. 5. 2013 21:17

ja bych to teda videl takhle:
trida:
Kód: Vybrat vše
    class RandomWithoutRepeat
    {
        private int index;
        private int maxValue;
        private int [] gen;
        private Random r = new Random();

        public RandomWithoutRepeat(int maxValue) {
            this.maxValue = maxValue;
            gen = new int[maxValue];
        }

        public int Next() {
            int res;
            if (gen[index] == 0)
            {
                int cislo = r.Next(maxValue - index);
                if (gen[cislo + index] == 0)
                    res = cislo + index;
                else
                    res = gen[cislo + index] - 1;
                gen[cislo + index] = index + 1;
            }
            else
            {
                res = gen[index] - 1;
            }
            index++;
            return res;
        }
    }


a priklad pouzit

Kód: Vybrat vše
            RandomWithoutRepeat r = new RandomWithoutRepeat(10);
            for (int i = 0; i < 10; i++)
               Console.Out.WriteLine(r.Next());


vyhody: rovnomerna rychlost generovani od zacatku do konce (coz neplati pro metodu s testoovanim, jestli jsem uz generoval) a rychle dodani prvniho vysledku (coz neplati pro metodu s pocatecnim michanim), zapouzdreny algoritmus.

Nevyhodne je to pouze za predpokladu, kdyz potrebny rozsah je prilis velky (treba vic nez 10 milionu) - prilis roste pametova narocnost. pak viz vyse Nargon.
pucmeloudek
Junior

Odeslat příspěvekod PeterKE 23. 5. 2013 22:21

myslím že riešiť toto "objektovo" je overkill, len to nafukuje kod a robi ho neprehľadným.
Ja by som to napísal takto - začnem od bodu že máme pole o dlžke c, najprv ho prvotne obsadíme číslami:
Kód: Vybrat vše
for (x=0;x<c;x+=1) pole[x]=x+1;

a potom ich zamiešame (jedným "prechodom"):
Kód: Vybrat vše
for (x=0;x<c;x+=1) {
   y=rand()%c;
   tmp=pole[x];
   pole[x]=pole[y];
   pole[y]=tmp;
}

Nie je to C# ale ten zápis je taký triviálny že by nemal byť problém ho previesť aj do toho C#
PeterKE
Junior

Odeslat příspěvekod kohutisko 23. 5. 2013 23:31

a este to urob bez pomocnej premennej tmp a budes uplny frajer ;)
kohutisko
Junior
Uživatelský avatar

Odeslat příspěvekod pucmeloudek 24. 5. 2013 06:54

Nu, on ten objektovy pristup sam o sobe overkill neni. Tomu pristupu, co jsem predved, se daj vytknout hlavne 2 veci.
1. pro zadani (napln pole vsemi cisly) neni idealne efektivni, potrebuje ty pole 2 (ale zas se hodi pro jiny ucely, kdy cloveku staci nekolik nahodnych cisel, jako treba sportka)
2. ta generova posloupnost cisel ma jednu nepeknou vlastnost. Schvalne, kdo odhali, jakou :)
pucmeloudek
Junior

Odeslat příspěvekod zivan 24. 5. 2013 08:09

To je skolni uloha? Pokud se probiraly nejake dynamicke struktury, tak by to tam treba ucitel chtel videt :)

Me napada reseni s jednim polem. Vytvori se pole o x prvcich, kde pole[x] = x. A pak se nahodne generuje index (tj. 0 az velikost -1). A cislo z toho nahodneho indexu se vymeni s cislem na konci pole. Pak se nahodne generuje index z intervalu 0 az velikost - 2 a prvek z toho indexu se vymeni s predposlednim...atd.
Naposledy upravil zivan dne 24. 5. 2013 08:35, celkově upraveno 1
Lenovo Moto G5 Plus, Lenovo Thinkpad X220 (12,5" IPS, i5-2410M, 16GB RAM, 500GB mSata Samsung 850 EVO + 1TB Samsung HDD) + 29" LG 29UM65 + 22" Eizo S2202W
zivan
Junior

Odeslat příspěvekod PeterKE 24. 5. 2013 08:26

re zivan: ten algoritmus je veľmi podobný môjmu, tu akurát ideš zozadu, nie spredu, a prvok na výmenu vyberaš nie zo všetkých ale iba zo zostávajúcich prkov

re: kohutisko: "a este to urob bez pomocnej premennej tmp a budes uplny frajer" - no navrhni niečo...
PeterKE
Junior

Odeslat příspěvekod kohutisko 24. 5. 2013 08:37

vymenit 2 ciselne premenne bez pomoci tretej sa samozrejme da. nie je to sice efektivne, je to len taka pikoska. kto si rad potrapi hlavu, nech porozmysla :)
kohutisko
Junior
Uživatelský avatar

Odeslat příspěvekod Bespi_ 24. 5. 2013 08:48

Muzes zkusit pouzit i toto:

Kód: Vybrat vše
               Dim lRandomList As New List(Of Int32)
      Const cMaxNumbers as Int32 = 10
      Dim lRandom As New System.Random()
      Do
         Dim lNewNumber As Int32 = lRandom.Next(0,1000)
         if Not lRandomList.Contains(lNewNumber) Then lRandomList.Add(lNewNumber)
      Loop While lRandomList.Count<cMaxNumbers
      
      ' -----------------
      For Each lNumber As Int32 In lRandomList
         Console.WriteLine(lNumber)
      Next


Konvertor do C# http://www.developerfusion.com/tools/convert/vb-to-csharp/

Pisu ve VB.NET protoze je to prehlednejsi nez C# a moznosti jsou defakto stejne.
Bespi_
Junior

Odeslat příspěvekod pucmeloudek 24. 5. 2013 09:16

[OT]
VB.NET definitivne NENI prehlednejsi nez c#. prave naopak, jedna z nejprisernejsich syntaxi, co existuje, bordel na ntou.
[/OT]
pucmeloudek
Junior

Odeslat příspěvekod Bespi_ 24. 5. 2013 10:09

[OT
]Je prehlednejsi. Neni potreba vkladat zbytecne komentare ktere supluji "zjednodusenou" syntaxi. Dokonce ani pri te jednodusi syntaxi neni C# uspornejsi. Staci si porovnat delku totoznych zdrojaku v obou jazycich. V C# me neuveritelne stve }}}}}} ... bez dodatecnych komentaru se v tom neda vyznat.
[/OT]
Bespi_
Junior

Odeslat příspěvekod piErcE 24. 5. 2013 10:24

kohutisko píše:vymenit 2 ciselne premenne bez pomoci tretej sa samozrejme da. nie je to sice efektivne, je to len taka pikoska. kto si rad potrapi hlavu, nech porozmysla :)


ze to není efektivní? :) je to efektivnější, než přes pomocnou proměnnou :)

-- 24. 5. 2013 11:25 --

:-D tohle vlákno je typická ukázka toho, proč většina opensource komunitních programů je většinou v praktickém životě nepoužitelná ... místo řešení cílového problemu lidi půl den stráví tím, že řeší, jak udělat triviální úlohu a jak je to nejlepší :)
Garmin DriveLuxe 50 - iPhone SE - Octavia III 1.4 110 kW DSG
piErcE
Junior

Odeslat příspěvekod Wikan 24. 5. 2013 10:37

Efektivnější je to jenom, když máš jistotu, že to tahle můžeš provést. Ono to totiž nejde vždy.
Wikan
Moderátor
Uživatelský avatar

Odeslat příspěvekod pucmeloudek 24. 5. 2013 10:42

Bespi_ píše:[OT]
V C# me neuveritelne stve }}}}}} ... bez dodatecnych komentaru se v tom neda vyznat.
[/OT]


ale da, staci dodrzovat odsazovani a neprogramovat jak prase (=neprehanet to s hloubkou vnorovani)

-- 24. 5. 2013 11:43 --

piErcE píše:ze to není efektivní? :) je to efektivnější, než přes pomocnou proměnnou :)


ale kusuj. efektivni leda z hlediska pametovych naroku, z hlediska casu, ktery v tom cpu stravi, urcite ne.
pucmeloudek
Junior

Odeslat příspěvekod PeterKE 24. 5. 2013 10:49

No už niekto napíšte ako vymeniť dve premenne bez pomocnej premennej! :)

C# alebo VB.NET - všetko vyzerá ako bordel, niet nad python! :)
PeterKE
Junior

Odeslat příspěvekod Bespi_ 24. 5. 2013 10:52

pucmeloudek píše:
Bespi_ píše:[OT]
V C# me neuveritelne stve }}}}}} ... bez dodatecnych komentaru se v tom neda vyznat.
[/OT]


ale da, staci dodrzovat odsazovani a neprogramovat jak prase (=neprehanet to s hloubkou vnorovani)


Staci aby kod byl delsi a nepomuze ti to. A ne vzdy je vhodne jednu funkci rozlozit na tisice kousku (funkce/procedury).
Bespi_
Junior

Odeslat příspěvekod pucmeloudek 24. 5. 2013 11:05

treba tak:
int a = 42, b = 73;
b = a ^ b;
a = b ^ a;
b = a ^ b

nebo se to da i scitanim/odcitanim
pucmeloudek
Junior

Odeslat příspěvekod PeterKE 24. 5. 2013 11:09

"^" je mocnina?
PeterKE
Junior

Odeslat příspěvekod pucmeloudek 24. 5. 2013 11:13

xor
pucmeloudek
Junior

Odeslat příspěvekod piErcE 24. 5. 2013 11:23

Proc tak složité proboha?

x -= y;
y += x;
x = (y - x);

-- 24. 5. 2013 12:25 --

pucmeloudek píše:
Bespi_ píše:[OT]
V C# me neuveritelne stve }}}}}} ... bez dodatecnych komentaru se v tom neda vyznat.
[/OT]


Samozrejme ze i z hlediska cpu.

ale da, staci dodrzovat odsazovani a neprogramovat jak prase (=neprehanet to s hloubkou vnorovani)

-- 24. 5. 2013 11:43 --

piErcE píše:ze to není efektivní? :) je to efektivnější, než přes pomocnou proměnnou :)


ale kusuj. efektivni leda z hlediska pametovych naroku, z hlediska casu, ktery v tom cpu stravi, urcite ne.


kušuj sám. Samozrejme i z pohledu cpu. Dve odečítání a jedno pricteni je řádově rychlejší, než veškerá režie s alokaci paměti apod.
piErcE
Junior

Odeslat příspěvekod xixo 24. 5. 2013 11:50

kušuj sám. Samozrejme i z pohledu cpu. Dve odečítání a jedno pricteni je řádově rychlejší, než veškerá režie s alokaci paměti apod.

Jakýkoliv ne úplně debilní kompilátor/JIT udělá z tmp registrovou proměnnou a nic se alokovat nebude. Prohazování přes xor nebo sčítání a odčítání (které se navíc může chovat zajímavě, zejména pokud ho provádíte u floatů) je tady dobré akorát tak pro matení n00bů.
xixo
Junior

Odeslat příspěvekod piErcE 24. 5. 2013 12:06

Coz ovsem ne vždy jde (registru není nekonečný počet), může to vest k tomu, ze se diky tomu do registru nevejde jiná proměnná, u které bude dopad na výkon keste vyšší. Ne vždy je vše tak jednoduché a orimocare, jak si myslíte... Noobe
piErcE
Junior

Odeslat příspěvekod pucmeloudek 24. 5. 2013 12:25

piErcE píše:Proc tak složité proboha?

x -= y;
y += x;
x = (y - x);


huh? ten tvuj kod neni o nic jednodussi, nez ten, co jsem postnul sam. nebo povazujes x += y za nejak vyrazne lepsi nez x = x + y? navic to xorovani prepises snadno na

b ^= a;
a ^= b;
b ^= a;

a jses na tom jeste lip z hlediska poctu bajtu zdrojovyho kodu nez ten bordel se scitanim.
pucmeloudek
Junior

Odeslat příspěvekod Nargon 24. 5. 2013 12:29

Co se týče toho prohození tak procesory obsahují instrukci XCHG, která právě slouží přímo k prohození dat. Dost se divím, že ty programovací jazyky nemají speciální funkci na prohození, která by právě využívala tuhle instrukci. A místo toho všichi píšem něco s tou "tmp" proměnou, kam si ten jeden prvek uschováme.
Desktop: Ryzen 7 1800X (3.95GHz, 1.35V), Asus Crosshair VI Hero, 16GB DDR4 Ram (3200MHz), 128GB SSD + 3TB HDD, Nvidia GTX 1080
Notebook: Asus UL50VT 15.6" (SU7300@1.7GHz, 4GB ram, 500GB HDD, Intel GMA 4500MHD + nVidia G210M, dlouha vydrz cca 7+ hod)
Nargon
Moderátor

Odeslat příspěvekod pucmeloudek 24. 5. 2013 12:33

piErcE píše:Coz ovsem ne vždy jde (registru není nekonečný počet), může to vest k tomu, ze se diky tomu do registru nevejde jiná proměnná, u které bude dopad na výkon keste vyšší. Ne vždy je vše tak jednoduché a orimocare, jak si myslíte... Noobe


blabol dne, prinejmensim pro x86
a) na prohozeni obsahu dvou registru zadnou dalsi promennou nepotrebuju (anzto mam na x86 xchg, na spouste ostatnich bude taky neco takoveho)
b) na prohozeni obsahu dvou pametovych bunek stejne obvykle zadna prima instrukce neni, takze pomocny registr potrebujes stejne.
pucmeloudek
Junior

Odeslat příspěvekod piErcE 24. 5. 2013 12:43

Takze si rovnou zaplacnes dva registry místo jednoho? :D
piErcE
Junior

Odeslat příspěvekod pucmeloudek 24. 5. 2013 12:51

me uz to nebavi.

mov eax, [pametove misto 1]
xchg [pametove misto 2], eax
mov [pametove misto 1], eax

kolik vidis registru?
pucmeloudek
Junior

Odeslat příspěvekod Nargon 24. 5. 2013 12:51

proč dva?
MOV regA, mem1
XCHG regA, mem2
MOV mem1, regA
A mám prohozené dvě paměťové buňky a stačil jeden registr.

Edit: byl jsi rychlejší :)
Desktop: Ryzen 7 1800X (3.95GHz, 1.35V), Asus Crosshair VI Hero, 16GB DDR4 Ram (3200MHz), 128GB SSD + 3TB HDD, Nvidia GTX 1080
Notebook: Asus UL50VT 15.6" (SU7300@1.7GHz, 4GB ram, 500GB HDD, Intel GMA 4500MHD + nVidia G210M, dlouha vydrz cca 7+ hod)
Nargon
Moderátor

Odeslat příspěvekod PiranhaGreg 24. 5. 2013 12:53

Prohazovat čísla (a další věci) umí třída Interlocked

Kód: Vybrat vše
int[] cisla = { 1, 2, 3 };

cisla[2] = Interlocked.Exchange(ref cisla[0], cisla[2]);

foreach (var cislo in cisla) // 3, 2, 1
    Console.WriteLine(cislo);


jen to asi nebude zas tak rychlý...
PiranhaGreg
Mírně pokročilý
Uživatelský avatar

Odeslat příspěvekod Fuller009 24. 5. 2013 13:10

Interlocked to sice umí. ale provádí to jako threadSafe atomickou operaci, což si vezme trošku výkonu navíc.

Jinak k použití tmp nebo xoru(plus a mínus). Stejně záleží na překladači jaký bastl vám z toho udělá ;-)
Fuller009
Junior

Odeslat příspěvekod PiranhaGreg 24. 5. 2013 13:45

Menší benchmark :mrgreen: .

Kód: Vybrat vše
Stopwatch sw = new Stopwatch();
int a = 5, b = 10;
int pom = 0;

// Metoda 1 -> 778 ms
sw.Start();

for (int i = 0; i < 100000000; i++)
    b = Interlocked.Exchange(ref a, b);

sw.Stop();
Console.WriteLine(sw.ElapsedMilliseconds + " ms");
sw.Reset();

// Metoda 2 -> 405 ms
sw.Start();

for (int i = 0; i < 100000000; i++)
{
    b ^= a;
    a ^= b;
    b ^= a;
}

sw.Stop();
Console.WriteLine(sw.ElapsedMilliseconds + " ms");
sw.Reset();

// Metoda 3 -> 614 ms
sw.Start();

for (int i = 0; i < 100000000; i++)
{
    a -= b;
    b += a;
    a = (b - a);
}

sw.Stop();
Console.WriteLine(sw.ElapsedMilliseconds + " ms");
sw.Reset();

// Metoda 4 -> 85 ms
sw.Start();

for (int i = 0; i < 100000000; i++)
{
    pom = a;
    a = b;
    b = pom;
}

sw.Stop();
Console.WriteLine(sw.ElapsedMilliseconds + " ms");
Naposledy upravil PiranhaGreg dne 24. 5. 2013 14:10, celkově upraveno 1
PiranhaGreg
Mírně pokročilý
Uživatelský avatar

Odeslat příspěvekod pucmeloudek 24. 5. 2013 14:06

mas tam ale chybicku v tom interlocked...
pucmeloudek
Junior

Odeslat příspěvekod PiranhaGreg 24. 5. 2013 14:10

Nojo, díky ;-) . Opraveno.
PiranhaGreg
Mírně pokročilý
Uživatelský avatar

Odeslat příspěvekod pucmeloudek 24. 5. 2013 15:00

pro zajimavost metoda 5 a 6
Kód: Vybrat vše
// ConsoleApplication1.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include <windows.h>
#include <iostream>

using namespace std;

typedef struct {
    LARGE_INTEGER start;
    LARGE_INTEGER stop; } stopWatch;
  void startTimer( stopWatch *timer) ;
  void stopTimer( stopWatch *timer) ;
  double LIToSecs( LARGE_INTEGER * L) ;
  double getElapsedTime( stopWatch *timer) ;

void startTimer( stopWatch *timer) {
    QueryPerformanceCounter(&timer->start) ;
}
void stopTimer( stopWatch *timer) {
    QueryPerformanceCounter(&timer->stop) ; }
double LIToSecs( LARGE_INTEGER * L) {
    LARGE_INTEGER frequency;
    QueryPerformanceFrequency( &frequency ) ;
    return ((double)L->QuadPart /(double)frequency.QuadPart) ; }
double getElapsedTime( stopWatch *timer) {
    LARGE_INTEGER time;
    time.QuadPart = timer->stop.QuadPart - timer->start.QuadPart;
    return LIToSecs( &time) ;
}

int _tmain(int argc, _TCHAR* argv[])
{
   stopWatch sw;
   startTimer(&sw);

   // metoda 5
   int a = 1, b = 2;
            for (int i = 0; i < 100000000; i++)
            {
                int pom = a;
                a = b;
                b = pom;
            }

   stopTimer(&sw);
   cout << getElapsedTime(&sw) * 1000 << '\n';

   // metoda 6
   startTimer(&sw);
            for (int i = 0; i < 100000000; i++)
            {
            __asm {
               mov eax, a;
               xchg b, eax;
               mov a, eax;
            }
            }
   stopTimer(&sw);
   cout << getElapsedTime(&sw) * 1000  << '\n';

   cin >> a;
   return 0;
}



s casy

39 ms
873 ms

nutno asi dodat, ze casy z predchozich mam

1121
665
659
258
pucmeloudek
Junior

Odeslat příspěvekod Bespi_ 24. 5. 2013 20:53

Mam pocit ze to tu uz prehanite.

Presne jak napsal piErcE:
:-D tohle vlákno je typická ukázka toho, proč většina opensource komunitních programů je většinou v praktickém životě nepoužitelná ... místo řešení cílového problemu lidi půl den stráví tím, že řeší, jak udělat triviální úlohu a jak je to nejlepší :)


Nikdo asi nepochybuje, ze to jde v assembleru napsat efektivneji nez v C# atd. Ale v praxi to ve vice jak 90% nikdo resit nebude a napise to normalne i bez tech optimalizaci :-) , protoze to neni potreba a ten usetreny procesorovy cas nic neprinese.
Bespi_
Junior

Odeslat příspěvekod PeterKE 24. 5. 2013 22:02

"napise to normalne i bez tech optimalizaci" - práveže tu boli prezentované 2 alebo 3 normálne riešenia ale ich náročnosť na CPU sa rádovo líšila (čím dlhší by bol zoznam prvkov, tým bol rozdiel výraznejší), takže programátor tak či tak musí byť schopný zvážiť viacej algoritmov a nie len že "skompilovalo to, tak to je hotové"
PeterKE
Junior

Odeslat příspěvekod Bespi_ 24. 5. 2013 23:32

Kdyz budu chtit vygenerovat 10 nahodnych cisel tak asi nebudu delat totozny kod jako kdyz jich budu generovat milion, to je snad jasne ne. Zalezi hlavne na pouziti, tedy ve vetsine pripadech se optimalizace tohoto typu resit nemusi.
Bespi_
Junior

Odeslat příspěvekod PiranhaGreg 25. 5. 2013 10:17

pucmeloudek píše:pro zajímavost metoda 5 a 6...
Jsem ani nečekal že bude výměna proměnných přes pomocnou proměnnou v C++ 6,5x rychlejší než v C# O:-) .
PiranhaGreg
Mírně pokročilý
Uživatelský avatar

Odeslat příspěvekod pucmeloudek 25. 5. 2013 14:08

Nojo, asi protoze to bezi uplbe cely jenom v registrech. Prakticky vyznam to nema zadny, menit 2 promenne furt tam a zpatky :-)
pucmeloudek
Junior


Kdo je online

Uživatelé procházející toto fórum: Žádní registrovaní uživatelé a 0 návštevníků