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

Předchozí stránkaDalší stránka

Kdo je online

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