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

[piErcE]

Proc tak složité proboha?

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

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

[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 --

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.

[xixo]

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

[piErcE]

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

[pucmeloudek]

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.

[Nargon]

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.

[pucmeloudek]

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.

[piErcE]

Takze si rovnou zaplacnes dva registry místo jednoho?

[pucmeloudek]

me uz to nebavi.

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

kolik vidis registru?

[Nargon]

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ší

[PiranhaGreg]

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

[Fuller009]

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á

[PiranhaGreg]

Menší benchmark .

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");

[pucmeloudek]

mas tam ale chybicku v tom interlocked...

[PiranhaGreg]

Nojo, díky . Opraveno.

[pucmeloudek]

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