Panel użytkownika
Nazwa użytkownika:
Hasło:
Nie masz jeszcze konta?

Dłuuugie oczekiwanie na Rand

Ostatnio zmodyfikowano 2011-03-17 17:32
Autor Wiadomość
Dragonit
Temat założony przez niniejszego użytkownika
Dłuuugie oczekiwanie na Rand
» 2011-03-17 16:53:08
Witam. Korzystam z dostępnego na stronie kodu źródłowego losowania liczb bez powtórzeń, trochę go przerobiłem do własnych potrzeb. Kod jest dobry, ale strasznie powolny. Przy wpisaniu dla losowania, losuj 100tys liczb z zakresu 100tys trzeba bardzooo długo czekać na wyniki. Dodam, że mam 4rdzeniowego Phenoma, który kręci po 4.0Ghz na rdzeń, więc to raczej nie wina zbyt słabego kompa. Czego mam użyć, aby kod był szybszy? Wielowątkowości? Czy po prostu przerobienie kodu np. zamiast na końcu wyrzucić wszystkie wyniki od razu, niech po kolei sprawdza wynik i wyrzuca na ekran. Nie wiem czy to szybsze będzie.

Oto kod:
C/C++
#include <iostream>
#include <cstdlib>
#include <ctime>

using namespace std;

bool czyBylaWylosowana( int iLiczba, int tab[], int ile )
{
    if( ile <= 0 )
         return false;
   
    int i = 0;
    do
    {
        if( tab[ i ] == iLiczba )
             return true;
       
        i++;
    } while( i < ile );
   
    return false;
}

int wylosuj( int max )
{
    return( rand() % max ) + 1;
}

int main()
{
    int IleLiczb, maxLiczby;
   
    cout << "ILE LICZB WYLOSOWAC: "; cin >> IleLiczb;
    cout << "MAKSYMALNY ZAKRES LICZB: "; cin >> maxLiczby;
   
    int * wylosowane = new int[ IleLiczb ];
    int wylosowanych = 0;
   
    srand( time( 0 ) );
    do
    {
        int liczba = wylosuj( maxLiczby );
        if( czyBylaWylosowana( liczba, wylosowane, wylosowanych ) == false )
        {
            wylosowane[ wylosowanych ] = liczba;
            wylosowanych++;
        } //if
    } while( wylosowanych < IleLiczb );
   
    wylosowanych = 0;
    do
    {
        std::cout << wylosowane[ wylosowanych ] << std::endl;
        wylosowanych++;
    } while( wylosowanych < IleLiczb );
   
    delete[] wylosowane;
   
    system( "PAUSE" );
    return EXIT_SUCCESS;
}
P-29284
ison
» 2011-03-17 16:56:06
program tak wolno działa bo jego złożoność jest zbyt duża, da się to zrobić w wydajniejszy sposób

//edit
C/C++
#include <cstdio>
#include <ctime>
#include <algorithm>
#include <vector>

const size_t ILOSC_LICZB = 1000000;

int main()
{
    srand( time( NULL ) );
    std::vector < int > vec;
    for( size_t i = 0; i < ILOSC_LICZB; ++i ) vec.push_back( i );
   
    random_shuffle( vec.begin(), vec.end() );
    //for(size_t i=0; i<vec.size(); ++i) printf("%d\n", vec[i]); wypisywanie do konsoli jest dosyć wolne (Windows), lepszym rozwiązaniem jest zapisywanie wyniku do pliku, jeśli chcesz zobaczyć wynik w konsoli to odkomentuj tę linijkę
}
bez wypisywania dla 1.000.000 liczb: 141 ms
zapisywanie wyniku do pliku dla 1.000.000 liczb: 1172 ms
wypisywanie wyniku na ekran dla 1.000.000 liczb: 40844 ms

//powyższy kod losuje bez powtórzeń liczby od 0 do N
żeby wylosować N losowych liczb z danego zakresu bez powtórzeń (tak aby w wylosowanym ciągu niekoniecznie znalazły się wszystkie liczby od 1 do N) to zwyczajnie wrzuć do vectora wszystkie liczby od 1 do zakresu do którego mają być losowane liczby i po random_shuffle bierz z niego pierwsze N liczb
C/C++
#include <cstdio>
#include <ctime>
#include <algorithm>
#include <vector>

const size_t ILOSC_LICZB = 10;
const size_t ZAKRES = 50; //zakres musi byc wiekszy lub rowny ilosci liczb

int main()
{
    srand( time( NULL ) );
    std::vector < int > vec;
    for( size_t i = 0; i < ZAKRES; ++i ) vec.push_back( i );
   
    random_shuffle( vec.begin(), vec.end() );
    for( size_t i = 0; i < ILOSC_LICZB; ++i ) printf( "%d\n", vec[ i ] );
    //na ekran nie zostaje wypisana cala zawartosc vectora vec tylko pierwsze ILOSC_LICZB liczb
}
P-29285
Dragonit
Temat założony przez niniejszego użytkownika
» 2011-03-17 17:32:54
Panie ison rewelacja. Wszystko oczywiście już działa jak należy. A i dzięki za dogłębne wytłumaczenie :) Jeśli ktoś ma coś do dodania niech się podzieli, w innym wypadku temat można zamknąć.
P-29286
« 1 »
  Strona 1 z 1