[c++] Generare milioni di numeri casuali univoci [Risolto subito Vict85+APa]
#include <fstream>
#include <stdlib.h>
#include <time.h>
#include <vector>
using namespace std;
int
main ()
{
vector < int > v (1000000);
int r;
bool ripeti = false;
srand (time (NULL));
for (int i = 0; i < 1000000; i++)
{
r = rand () % 2000000 + 1;
for (int c = 0; c < i; c++)
{
if (v[c] == r)
{
ripeti = true;
c = i;
}
}
if (ripeti == true)
i = i - 1;
else
v[i] = r;
ripeti = false;
}
ofstream out ("prova.txt");
for (int i = 0; i <1000000; i++)
out << v[i] << " ";
out << endl;
return 0;
}
Volevo migliorare questo codice senza copiare, in rete, algoritmi noti (Knuth/Ruskey..) ma difficili.
Il codice riportato è "comprensibile" agli ignorantoni come me; ci mette mezz'ora (anche di più
) per generare un file con un milione di numeri che NON si ripetino.
Risposte
Se usi il C++ è meglio se usi la libreria random, è migliore di rand sotto vari aspetti. Non cambia in modo considerevole il codice. Un esempio del suo uso lo vedi qui http://en.cppreference.com/w/cpp/numeri ... stribution (questo esempio usa il Mersenne Twister per generare i numeri casuali).
Potresti eliminare la ricerca dell'elemento usando un vector. Seppur immagino che il più grande problema di questo algoritmo sia che la probabilità di ritrovare un numero precedentemente estratto è molto grande.
Potresti eliminare la ricerca dell'elemento usando un vector
Mitico Vic! Il link è ottimo! Devo cambiare sì.
Per non ripeterli il modo usato è primitivo, lo so.
Dici di togliere il ciclo e mettere un vettore di booleani?
Mi fai vedere come faresti tu?
Per non ripeterli il modo usato è primitivo, lo so.
Dici di togliere il ciclo e mettere un vettore di booleani?
Mi fai vedere come faresti tu?
Ne ho parlato con Antonio (APatriarca) e ha detto che quando i due valori si avvicinano si tende ad usare uno shuffle. Ho fatto una prova e per valori come questi sembra che la predominanza di uno o dell'altro dipenda dalle ottimizzazioni del compilatore (tra l'altro potrebbero esserci bug in giro)[nota]È una impressione, comunque in release sembra che convenga la versione con il vector di bool.[/nota]. In entrambi i casi la scrittura del file è l'operazione più lenta di tutte comunque.
#include <fstream>
#include <iostream>
#include <vector>
#include <random>
#include <chrono>
typedef unsigned int uint;
std::vector<uint> generate(uint const N, uint const M);
std::vector<uint> generate_std(uint const N, uint const M);
std::vector<uint> generate_shuffle(uint const N, uint const M);
std::vector<uint> generate_slow(uint const N, uint const M);
int main()
{
std::chrono::time_point<std::chrono::system_clock> start, end;
start = std::chrono::system_clock::now();
uint const N = 1000000;
uint const M = 2000000;
//std::vector<uint> vec{ generate(N, M) };
//std::vector<uint> vec{ generate_shuffle(N, M) };
std::vector<uint> vec{ generate_std(N, M) };
//std::vector<uint> vec{ generate_slow(N, M) };
end = std::chrono::system_clock::now();
std::chrono::duration<double> diff = end - start;
std::cout << "Ci ha messo " << diff.count() << " s " << std::endl;
//start = std::chrono::system_clock::now();
std::ofstream out("prova.txt");
for (int i = 0; i < N; i++)
out << vec[i] << " ";
out << std::endl;
//end = std::chrono::system_clock::now();
//diff = end - start;
//std::cout << "Ci ha messo " << diff.count() << " s " << std::endl;
return 0;
}
//decide quale lanciare tra i due algoritmi, il valore 3/8 è scelto piuttosto casualmente
std::vector<uint> generate(uint const N, uint const M)
{
std::vector<uint> vec{};
if (N < M)
{
vec = ((M + 0.) / N > 3 / 8) ? generate_shuffle(N, M) : generate_std(N, M);
}
else if (N == M)
{
vec.reserve(M);
for (uint i = 0; i != M;) {
vec.push_back(++i);
}
}
return vec;
}
std::vector<uint> generate_std(uint const N, uint const M)
{
std::vector<uint> vec{};
vec.reserve(N);
std::vector<bool> Chk_vec(M, true);
{
std::random_device rd;
std::default_random_engine gen(rd());
std::uniform_int_distribution<uint> dist(1, M);
for (int i = 0; i != N; ++i)
{
uint t = dist(gen);
if (Chk_vec[t - 1])
{
vec.push_back(t);
Chk_vec[t - 1] = true;
}
else
{
--i;
}
}
}
return vec;
}
std::vector<uint> generate_shuffle(uint const N, uint const M)
{
std::vector<uint> vec{};
vec.reserve(M);
for (uint i = 0; i != M;) {
vec.push_back(++i);
}
{
std::random_device rd;
std::default_random_engine gen(rd());
for (uint i = 0; i != N; ++i)
{
std::uniform_int_distribution<uint> dist(i, M - 1);
uint j = dist(gen);
uint const t = vec[i];
vec[i] = vec[j];
vec[j] = t;
}
}
vec.resize(N);
return vec;
}
std::vector<uint> generate_slow(uint const N, uint const M)
{
std::vector<uint> vec{};
vec.reserve(N);
std::random_device rd;
std::default_random_engine gen(rd());
std::uniform_int_distribution<uint> dist(1, M);
for (int i = 0; i < N; ++i)
{
bool ripeti = false;
uint r = dist(gen);
for (int j = 0; j < i; ++j)
{
if (vec[j] == r)
{
ripeti = true;
j = i;
}
}
if (ripeti)
--i;
else
vec.push_back(r);
}
return vec;
}
Senza di 
Voi non saprei davvero che fare!!!!!!!
Voi non saprei davvero che fare!!!!!!!
.. e se volessimo generare N numeri reali (diciamo double) all'interno di un qualche intervallo [a, b] in modo che ogni numero abbia una distanza di almeno \(\epsilon\) da tutti gli altri? Qualche idea su come affrontare questo problema?
Capisco la faccina iniziale[size=150] = )[/size]
Nell'intervallo ci sono infinite possibilità di scelta, questo ok; ma non saprei davvero, forse c'é qualche nuova funzione magica nello standard '14?
(Io sono ancora al '98 quando giocavo alla play I a WorldCup'98 )
Nell'intervallo ci sono infinite possibilità di scelta, questo ok; ma non saprei davvero, forse c'é qualche nuova funzione magica nello standard '14?
(Io sono ancora al '98 quando giocavo alla play I a WorldCup'98
)
Si tratta essenzialmente dello stesso problema. L'unica differenza è che le soluzioni adottate per riconoscere i duplicati non sono adottabili. Ovviamente puoi usare il tuo algoritmo di base, ma si può fare di meglio ovviamente.
Ragazzi, Maestri miei 
Non vi prendete gioco di me
Ho provato a modificare il codice di Vic e ho dovuto premere ctrl+c...
Sapete a che livelli sono o vi scrivo in privato?!?!??!
Il problema non è così banale. Cioé in questo caso bisogna conoscere bene il c++ per non mandare a spasso il compilatore..
Mi accontento del "codice magico" che lavora con gli interi che, non so come, va alla velocità della luce!!!!
E' incredibile davvero quel codice! [size=50]Ed ecco come eludere il discorso...[/size]
[size=50]Anche se vederlo/impararlo mi stuzzica non poco... Petrebbe essere molto utile quando si lavora con esercizi in stile "zaino reale greedy" e problemi simili...[/size]
Non vi prendete gioco di me
Ho provato a modificare il codice di Vic e ho dovuto premere ctrl+c...
Sapete a che livelli sono o vi scrivo in privato?!?!??!
Il problema non è così banale. Cioé in questo caso bisogna conoscere bene il c++ per non mandare a spasso il compilatore..
Mi accontento del "codice magico" che lavora con gli interi che, non so come, va alla velocità della luce!!!!
E' incredibile davvero quel codice! [size=50]Ed ecco come eludere il discorso...[/size]
[size=50]Anche se vederlo/impararlo mi stuzzica non poco... Petrebbe essere molto utile quando si lavora con esercizi in stile "zaino reale greedy" e problemi simili...[/size]
Non è una questione di sapere il C++. Ti do un piccolo hint su come si potrebbe fare: puoi generarli in ordine e poi mischiarli.
Per un po' di ore, in ambiente lavorativo, non ho tempo ( e manco un compilatore in mano per poter far disastri... )
L'hint è grandioso! Cavolo, non ci avevo pensato proprio! Alla fine è un ciclo che si "blocca e sblocca" e che spara numeri andando sempre verso un verso di conteggio. Poi, una volta finito, si applica una qualche funzione di shuffle che sparge double a casaccio (e qui sì che serve sapere qualcosina Vic )
Grazie per gli stimoli, ragazzi siete straordinari!!!!!
)L'hint è grandioso! Cavolo, non ci avevo pensato proprio! Alla fine è un ciclo che si "blocca e sblocca" e che spara numeri andando sempre verso un verso di conteggio. Poi, una volta finito, si applica una qualche funzione di shuffle che sparge double a casaccio (e qui sì che serve sapere qualcosina Vic
) Grazie per gli stimoli, ragazzi siete straordinari!!!!!
Ci sono principalmente tre idee di base:
1. Supponi di suddividere il tuo intervallo in diversi sottointervalli. Per ogni sottointervallo memorizzi i valori in esso contenuti. Se ora devi vedere se un qualche nuovo valore è troppo vicino ad un altro, quello che puoi fare è vedere in quale sottointervallo si trova e confrontarlo solo con i valori di questo sottointervallo. In questo modo hai ovviamente ridotto il numero di confronti da fare ad ogni iterazione. Ci sono a questo punto diversi modi di dividere il nostro intervallo in sottointervalli: si può usare una suddivisione gerarchica creando una specie di albero o si può suddividere in un numero fisso di intervalli o si può scegliere il numero di suddivisioni in base ad \(\epsilon,\) l'ampiezza dell'intervallo o altri valori.
2. Si può creare una struttura dati per memorizzare le parti dell'intervallo ancora libere. Partiamo quindi da \((a, b)\) e quando scegliamo un numero \(x\) suddividiamo l'intervallo in due: \( (a, x-\epsilon), (x+\epsilon, b). \) A questo punto ripetiamo il processo ma scegliendo questa volta il numero solo all'interno di uno di quegli intervalli. Nota che perché sia uniforme la probabilità hai bisogno di scegliere un intervallo in base alla sua ampiezza. Un modo può essere quello di mantenere la somma delle ampiezze dei sottointervalli e quindi usare questa somma per scegliere il numero casuale.
3. Usare l'idea di Vittorio sull'array con valori casuali ordinati e quindi mischiarli (anche se credo che in questo caso sia più difficile ottenere una distribuzione uniforme dei valori).
1. Supponi di suddividere il tuo intervallo in diversi sottointervalli. Per ogni sottointervallo memorizzi i valori in esso contenuti. Se ora devi vedere se un qualche nuovo valore è troppo vicino ad un altro, quello che puoi fare è vedere in quale sottointervallo si trova e confrontarlo solo con i valori di questo sottointervallo. In questo modo hai ovviamente ridotto il numero di confronti da fare ad ogni iterazione. Ci sono a questo punto diversi modi di dividere il nostro intervallo in sottointervalli: si può usare una suddivisione gerarchica creando una specie di albero o si può suddividere in un numero fisso di intervalli o si può scegliere il numero di suddivisioni in base ad \(\epsilon,\) l'ampiezza dell'intervallo o altri valori.
2. Si può creare una struttura dati per memorizzare le parti dell'intervallo ancora libere. Partiamo quindi da \((a, b)\) e quando scegliamo un numero \(x\) suddividiamo l'intervallo in due: \( (a, x-\epsilon), (x+\epsilon, b). \) A questo punto ripetiamo il processo ma scegliendo questa volta il numero solo all'interno di uno di quegli intervalli. Nota che perché sia uniforme la probabilità hai bisogno di scegliere un intervallo in base alla sua ampiezza. Un modo può essere quello di mantenere la somma delle ampiezze dei sottointervalli e quindi usare questa somma per scegliere il numero casuale.
3. Usare l'idea di Vittorio sull'array con valori casuali ordinati e quindi mischiarli (anche se credo che in questo caso sia più difficile ottenere una distribuzione uniforme dei valori).
Ho il compilatore ora ma, pur avendolo, no.. non riuscirei a farlo sicuro.
Riuscivo, ma a fatica, con gli interi.. A parole, leggendo, credo di capire le varie possibili idee...
Implementarle meno, molto meno. Lavorare con questi valori penso sia molto complicato e, se Apa, ha proposto un approfondimento vuol dire che banale non è. La soluzione di Vic mi pareva molto valida, in effetti la distribuzione è vero che potrebbe essere troppo "calcolata" e quindi ci sarebbero scelte "prevedibili". A parte che, avevo pensato di poterla fare "addormentando" il ciclo che sceglie i valori... Che non saprei manco fare su due piedi... Devo cambiare facoltà
Riuscivo, ma a fatica, con gli interi.. A parole, leggendo, credo di capire le varie possibili idee...
Implementarle meno, molto meno. Lavorare con questi valori penso sia molto complicato e, se Apa, ha proposto un approfondimento vuol dire che banale non è. La soluzione di Vic mi pareva molto valida, in effetti la distribuzione è vero che potrebbe essere troppo "calcolata" e quindi ci sarebbero scelte "prevedibili". A parte che, avevo pensato di poterla fare "addormentando" il ciclo che sceglie i valori... Che non saprei manco fare su due piedi... Devo cambiare facoltà
Però, mentre cenavo, pensavo.. E se si usasse un set di double che vuole un elemento diverso dall'altro?! Ci pensa il set a garantire il valore unico? O sbaglio? Quindi basta prendere il codice consigliato da Vic e buttare tutto in un set e non in un vector? Però non ho provato la sto buttando un po' così... ( :Apa sai che devi avere molta pazienza con me : )
Con i double si dovrebbe evitare di usare l'operazione $=$ perché potrebbe dare risultati inaspettati.
Se la richiesta fosse di ottenere valori univoci.. potresti fare come dici mettendo tutto in un set.. ma la richiesta non è quella. Io voglio valori che siano casuali (distribuzione uniforme) ma tali che ci sia una distanza minima fissata tra di loro.. Si tratta di una versione semplificata di Poisson Disk Sampling. La differenza è ovviamente la dimensione.
P.S. Si tratta di una distribuzione abbastanza utile. Serve ad esempio quando si vogliono disporre degli oggetti, senza che questi oggetti siano troppo vicini tra di loro. E' anche comune in natura (se non sbaglio sono disposti secondo questa distribuzione i fotorecettori nella nostra retina).
P.S. Si tratta di una distribuzione abbastanza utile. Serve ad esempio quando si vogliono disporre degli oggetti, senza che questi oggetti siano troppo vicini tra di loro. E' anche comune in natura (se non sbaglio sono disposti secondo questa distribuzione i fotorecettori nella nostra retina).
AH 
allora avevo capito male leggendo in fretta!!!! Sì pensavo a numeri double che non si ripetessero... Ora avevo pensato ad un set che fa tutto da se e, ciclando con un while sulla sua dimensione, quando era pieno il set voleva dire che era finito il lavoro garantendo univocità... Però se Vic dice che le operazioni sballano vuol dire che l'idea è bocciata poiché il set fallirà nel suo scopo. La distribuzione avevo capito che era una sorta di "optional" da pagare per avere qualcosa in più. Tu invece proponevi una versione eccellente FULL OPTIONAL = ) Apa e Vic volete farmi volare alto ma io manco un aliante vi guido.. 
allora avevo capito male leggendo in fretta!!!! Sì pensavo a numeri double che non si ripetessero... Ora avevo pensato ad un set che fa tutto da se e, ciclando con un while sulla sua dimensione, quando era pieno il set voleva dire che era finito il lavoro garantendo univocità... Però se Vic dice che le operazioni sballano vuol dire che l'idea è bocciata poiché il set fallirà nel suo scopo. La distribuzione avevo capito che era una sorta di "optional" da pagare per avere qualcosa in più. Tu invece proponevi una versione eccellente FULL OPTIONAL = ) Apa e Vic volete farmi volare alto ma io manco un aliante vi guido.. 
Potresti provare a leggere l'articolo di Bridson ed implementarlo nel caso n=1.
Quindi bisogna produrre numeri in una sorta di intorno: ogni volta si aggiunge un numero che ha una distanza r minima da quello scelto. Ci serve una matrice o qualcosa del genere... Poi due array che ci aiutano a tenere traccia dei numeri scelti casualmente e restituire i numeri finali scelti e "promossi". Nella matrice si mette in una (ed una sola) casella uno (ed uno solo) dei numeri.
Mi dimenticavo del k (il numero 30 pare che basti) che è un limite sulle ripetizioni di scelta quando i numeri casuali non ci vanno bene... Quindi questa costante ci garantisce un ciclo (di tempo costante) dentro ad un "ciclo serio", cioé che dipende da n.
Tornando alla matrice, ogni casella dovrebbe avere una dimensione fissa: r/sqrt(n)
giusto per avere univocità (credo). All'inizio tutta inizializzata a -1 e quando non è negativa ci fornisce l'indice del numero.
Il primo numero si sceglie random e viene messo sicuro nel vettore finale da tornare. Si prende nota in un vettore ausiliare "active list" e nella matrice (non ho capito bene cosa inserirci però). Fino a quando (entro in un while) questa lista ausiliaria non è vuota scelgo un num casuale che non dev'essere vicino a nessuno altro (controllando la matrice?); se non si trova "vicino" allora è accettato e messo nel vettore finale (e si prende nota sia in quello ausiliare ed altresì nella matrice)
Immagino un for (limitato) dentro ad un while ma il verificare se un numero sta in una sorta di intorno di un altro non mi è chiaro.. Forse basta una funzione che ritorna false se la "distanza da rispettare", ossia r, è >= della distanza dal numero random scelto...
Mi dimenticavo del k (il numero 30 pare che basti) che è un limite sulle ripetizioni di scelta quando i numeri casuali non ci vanno bene... Quindi questa costante ci garantisce un ciclo (di tempo costante) dentro ad un "ciclo serio", cioé che dipende da n.
Tornando alla matrice, ogni casella dovrebbe avere una dimensione fissa: r/sqrt(n)
giusto per avere univocità (credo). All'inizio tutta inizializzata a -1 e quando non è negativa ci fornisce l'indice del numero.
Il primo numero si sceglie random e viene messo sicuro nel vettore finale da tornare. Si prende nota in un vettore ausiliare "active list" e nella matrice (non ho capito bene cosa inserirci però). Fino a quando (entro in un while) questa lista ausiliaria non è vuota scelgo un num casuale che non dev'essere vicino a nessuno altro (controllando la matrice?); se non si trova "vicino" allora è accettato e messo nel vettore finale (e si prende nota sia in quello ausiliare ed altresì nella matrice)
Immagino un for (limitato) dentro ad un while ma il verificare se un numero sta in una sorta di intorno di un altro non mi è chiaro.. Forse basta una funzione che ritorna false se la "distanza da rispettare", ossia r, è >= della distanza dal numero random scelto...
TE SEI TORNATO DA ROMA POI?!?!??!?!
// non so che metterci
vector<int> aus(size, -1);
// first sample
Vec<n1,n2> matr;
for(int i=0; i<n1; i++)
matr[i]=rand(seme) //il primo numero poi da questo si parte con Poisson
//non so
aclist.pushback(0); //indice del primo numero scelto
int pippo = // dovrebbe prendere dati dalla matr ma non so cosa :(
arrayfinale[pippo] = 0;
while(!aclist.empty())
//non so
for(int j=0; j<k; j++)
// AIUTOOOOOOO
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo