migliore algoritmo C++ per verificare se in una sequenza di numeri tutti sono diversi

[arsenico2009]

qual'è il migliore algoritmo per C++ per verificare se in una sequenza di numeri tutti sono diversi ??

qual'è il vostro modo di procedere tenendo conto che io ho un array di N numeri.

[arsenico2009]

posta il codice

[arsenico2009]

io ho pensato questo:

poniamo che il prog deve generare N numeri casuali diversi.

for (int i=0; i<N; i++){
ripeti:
numeri[i]=generaNumeri();
for (int j=i-1; j>=0; j--){
if (numeri[i] == numeri[j]){
goto ripeti;
}
}
}

[arsenico2009]

il problema è che con questo algoritmo per un numero elevato di numeri ci mette troppo tempo.

io invece volevo un algoritmo più efficiente.

in pratica devo generare N numeri diversi, con N anche 1 milione.

[wingman87]

Li ordini e poi li scorri uno ad uno, se non ne trovi due vicini uguali è perché non ce ne sono. Questo algoritmo è O(nlog(n))

[arsenico2009]

mi fai vedere come applicarlo. non ho ben capito.

scrivi un pezzo di codice.

[wingman87]

Però questo risolve il problema iniziale. Se invece vuoi generare N numeri tutti diversi, se possibile, puoi creare una sequenza che va da 1 a N e poi "disordinarla".
Se invece devono essere N numeri completamente random l'affare si complica, probabilmente ti conviene inserire uno ad uno gli elementi random in una struttura ordinata, avendo cura di controllare ogni volta che l'elemento non sia già presente (oppure, meglio, la struttura può non fare nulla se l'elemento da inserire è già presente).
In casi come questo non so come si calcola la complessità perché a livello teorico potrebbe anche non terminare mai se ad un certo step non viene più generato nessun numero non ancora presente nella struttura...
Se possibile adotta il primo metodo, tieni conto del fatto che non devi necessariamente usare i numeri da 1 a N ma puoi anche generarli secondo una qualche distribuzione, basta che siano tutti diversi, e poi disordinarli.

[clockover]

Diciamo che comunque il titolo del post non è pienamente attinente a quello che stai cercando di fare. Tu vuoi creare una sequenza di numeri tutti diversi

Soluzione 1
Ti crei un array da 0 a N (dove N è il numero più grande che vorresti avere nel tuo vettore casuale). Generi un numero random da 0 a N che chiameremo M. Rimuovi dal tuo array l'elemento con indice M (lo rimuovi completamente) e lo inserisci nel tuo vettore che stai generando. L'array iniziale adesso è più piccolo di 1 quindi qualunque altro numero M casuale punterà ad un altro elemento e così via.
Es.
Array[0-N]
Casuale (per ora ha dimensione 0)
genero M (random da 0 a N)
Casuale[0] = Array[M]
rimuovo Array[M]
genero M (random da 0 a N-1)
Casuale[1] = Array[M]
rimuovo Array[M]
.....

Soluzione 2
Ogni numero casuale generato verrà inserito in un Set. Non è un buon metodo comunque.

[wingman87]

Originariamente inviato da arsenico2009

mi fai vedere come applicarlo. non ho ben capito.

scrivi un pezzo di codice.

Te lo scrivo in pseudo codice:

checkAllUnique (array, nElem) {
   sortedArray = sort(array)
   previousElem = sortedArray[0];
   for(i=1; i<nElem; i++){
      if(sortedArray[i] == previousElem)
         return false;
      previousElem = sortedArray[i];
   }
   return true;
}

[arsenico2009]

in metodo di CLOCK_OVER è più efficiente.

il problema è che come si elimina un elemento da un'array ?

[clockover]

Originariamente inviato da arsenico2009

in metodo di CLOCK_OVER è più efficiente.

il problema è che come si elimina un elemento da un'array ?

Si ma l'efficienza di un metodo "in pratica" dipende dall'utilizzo che se ne deve fare. Cosa devi farci con questi numeri casuali?
Per quanto riguarda rimuovere un elemento da un array in C++ non posso aiutarti

Inviato da una supercazzola ed un Nexus 5 scappellato a sinistra.. con senso unico

[Daniels118]

Puoi usare un generatore di numeri casuali con un periodo maggiore del numero di elementi nell'array.

Oppure ogni volta che inserisci un elemento gli assegni il valore usato in precedenza incrementato di una quantità casuale (*non troppo grande*), alla fine fai degli scambi casuali sugli elementi per disordinarli.
Volendo l'algoritmo si può anche migliorare per evitare di dover fare gli scambi casuali.

[clockover]

Originariamente inviato da coffe_killer

Comunque per il discorso efficienza, onestamente per un algoritmo del genere non starei troppo a guardare una cosa del genere...la generazione di un numero per una CPU è poca roba, anche se ben fossero 1000000, chissenefrega...cioè è giusto calcolare complessità e complessità, ma di solito sono cose irrilevanti per frammenti di codice così piccoli...si comincia a ragionare in quei termini solo se cominci ad avere un programma con migliaia di righe di codice annidate e ricorsioni a manetta...

mi è capitato spesso di sviluppare, sia in uni, sia sul lavoro, programmi corposi, sia in C sia in Java, ma non ho mai davvero apprezzato cambiamenti significativi tra un algoritmo e l'altro...è un discorso che vale di più per la creazione di SO, sistemi distribuiti, algoritmi di calcolo scientifico ecc....

Non mi ci trovo tanto nel tuo ragionamento. Quindi mi stai dicendo che se io volessi generare 50 numeri, tutti totalmente diversi e su una base di 70 numeri, chissenefrega....vai di forza bruta? Tanto che ci mette a generare un numero?

[Daniels118]

Un milione di numeri non sono pochi, per verificare se ci sono duplicati con l'algoritmo semplice (due cicli annidati che confrontano ogni elemento con tutti gli altri), la complessità o(n^2) implica 1000000^2 = mille miliardi di operazioni!
E se capita un doppione bisogna sostituirlo con un altro numero casuale fino a quando non diventa unico!

La soluzione che ho proposto prima consente di generare direttamente numeri unici, casuali e distribuiti in modo uniforme.

[clockover]

Originariamente inviato da Daniels118

Un milione di numeri non sono pochi, per verificare se ci sono duplicati con l'algoritmo semplice (due cicli annidati che confrontano ogni elemento con tutti gli altri), la complessità o(n^2) implica 1000000^2 = mille miliardi di operazioni!
E se capita un doppione bisogna sostituirlo con un altro numero casuale fino a quando non diventa unico!

La soluzione che ho proposto prima consente di generare direttamente numeri unici, casuali e distribuiti in modo uniforme.

Ma se hai un numero limitato di numeri? Supponiamo che il massimo numero che puoi inserire è 90 e devi sceglierne casualmente 10, e a prima botta ti esce 89...

[!fazz]

l'algoritmo semplice di ricerca iterativa (quello con due cicli ) va benissimo se il numero di elementi è limitato, se diventano parecchi (milioni o più) forse è meglio pensare ad alcuni trucchetti per ridurre il tempo di esecuzione come ad esempio, il primo che mi viene in mente usare una hash table e verificare se ci sono doppioni solamente nelle collisioni

[Daniels118]

Mi autoquoto:

(*non troppo grande*)

Cerco di non dilungarmi troppo nelle risposte per evitare di dire cose scontate, comunque, visto che sembra che non lo siano così tanto, ecco gli accorgimenti da adottare:
1) anche il primo numero generato deve essere *non troppo grande*;
2) per *non troppo grande* si intende compreso tra zero (EDIT: strettamente maggiore di zero) e MAX/N, dove MAX è il valore massimo accettabile nell'intero vettore ed N è il numero di elementi da inserire.

Nel peggiore dei casi (tutti gli incrementi casuali uguali a MAX/N: e che sfiga!),
avremo che il kappesimo numero sarà uguale a:
SOMMATORIA per i da 1 a K DI (MAX/N) = k*(MAX/N)
l'ennesimo numero sarà quindi N*(MAX/N), che è la stessa cosa di MAX*(N/N),
poiché N/N = 1, il massimo sarà uguale a MAX.

In molti linguaggi la funzione random accetta direttamente il valore massimo da generare, altrimenti è possibile ovviare utilizzando l'operatore modulo (la percentuale in C).

[-MiStO-]

Originariamente inviato da !fazz

l'algoritmo semplice di ricerca iterativa (quello con due cicli ) va benissimo se il numero di elementi è limitato, se diventano parecchi (milioni o più) forse è meglio pensare ad alcuni trucchetti per ridurre il tempo di esecuzione come ad esempio, il primo che mi viene in mente usare una hash table e verificare se ci sono doppioni solamente nelle collisioni

esattamente:hastable e via per controllare se il numero e gia stato generato / trovato

[Daniels118]

L'hashtable è una buona soluzione, però così si spreca parecchia memoria per conservare dei cloni dei numeri generati.
Però questo problema non è rilevante se la memoria a disposizione è abbondante, il vero problema è che se la quantità di valori si avvicina al valore massimo, c'è un'altissima probabilità di generare duplicati e le prestazioni dell'algoritmo degradano vertiginosamente. Generare direttamente numeri unici garantisce delle performance superiori.

[arsenico2009]

in pratica devo creare un programma che genera N (scelto dall'utente) numeri casuali diversi.

l'algoritmo deve essere efficiente perchè se l'utente gli dice generami 2.000.000 di numeri diversi il prog non deve stare due minuti ad elaborare.

deve immediatamente generarli e salvarli in un file.

qual'è il metodo che usereste.

spiegate in modo semplice e con parole non troppo eloquenti.