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]

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]

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]

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]

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

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.

[clockover]

Già hai avuto diverse spiegazioni. Tu però non sei stato preciso. Qual'è il numero massimo? L'array finale deve essere ordinato? Possono esserci numeri negativi? Float? Ecc...

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

[arsenico2009]

non ho mai detto che l'array deve essere ordinato ( quindi non mi serve l'ordinamento ).

faccio l'esempio per capirci.

l'utente digita 7.

il pc elabora così: ( 5 - 3 - 6 - 1 - 7 - 2 - 4 )

chiaramente dovrà generare tutti i numeri da 1 a 7 in maniera casuale-disordinata.

[clockover]

Guarda allora hai fatto un casino.
1 il titolo della discussione è completamente sbagliato
2 ci hai fatto intendere che bisognava generare questi numeri casualmente

Soluzione (che già ti aveva dato un altro utente) : ti crei un array e lo mescoli.

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

[arsenico2009]

come faccio a mescolarlo.

scusatemi tanto:(

[clockover]

Ci sono tanti modi. Uno potrebbe essere quello di scandire l'array e a ogni iterazione ti generi un numero causale fino a N che chiamiamo M. Basta quindi scambiare il valore in posizione attuale con il valore in posizione M.

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

[arsenico2009]

caro clockover con l'ultimo metodo che hai detto mi ritrovo la lista sempre con doppioni. NON FUNZIONA :muro: :muro: :mc: :mc: :confused: :confused: :rolleyes:

[clockover]

Vuol dire che lo implementi male. Non possono esserci doppioni se in una lista senza doppioni effettui degli scambi

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

[arsenico2009]

ECCO IL PEZZO DI CODICE:

N=100000;

int numeri[N];

//CARICA NUMERI IN ORDINE
for (int i=0; i<N; i++){
numeri[i]=i+1;
}

//MESCOLA

srand(time(NULL));
for (int i=0; i<N; i++){
numeri[i]=numeri[generaNumeri()];
}

//GENERA NUMERO
int generaNumeri(){
int numero=rand() % N;
return numero;
}

[wingman87]

L'istruzione
numeri[i]=numeri[generaNumeri()];
non scambia due elementi ma copia il secondo nel posto del primo

[arsenico2009]

scusa mi ero dimenticato un pezzo.

for (int i=0; i<N; i++){
int casuale=generaNumeri();
numeri[casuale]=numeri[i];
numeri[i]=numeri[casuale];
}

lo stesso non funziona !!!

[wingman87]

Anche in quel modo non stai effettuando uno scambio, pensaci bene.

[arsenico2009]

Ci sono tanti modi. Uno potrebbe essere quello di scandire l'array e a ogni iterazione ti generi un numero causale fino a N che chiamiamo M. Basta quindi scambiare il valore in posizione attuale con il valore in posizione M.


come interpretarlo ??

[clockover]

Ci sono tanti modi. Uno potrebbe essere quello di scandire l'array e a ogni iterazione ti generi un numero causale fino a N che chiamiamo M. Basta quindi scambiare il valore in posizione attuale con il valore in posizione M.


come interpretarlo ??

Non devi interpretare più nulla. Sembra che hai capito il senso ma non lo implementi bene. Sai scambiare di posto due elementi in un array dati due indici?

void swap(int * array, int i, int j){
.......
.......
.......
}

sapresti completarmi questa funzione?

ps
il prossimo codice che posti indentalo per piacere altrimenti non ti rispondo più

[arsenico2009]

mostrami il codice. guarda che non mi trovo.

[clockover]

mostrami il codice. guarda che non mi trovo.

Che furbacchione :D

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

[Daniels118]

:mbe: Cavolo, ti ha messo proprio il numero di righe delle istruzioni che servono, ci mancava solo che li metteva pure contati per i singoli caratteri, potremmo farci le parole crociate, un po' di impegno, su!

[!fazz]

arsenico ti ricordo che come da regolamento di sezione non si fanno i compiti per gli studenti

[arsenico2009]

non è il fatto di fare i compiti.

il problema è che click over come anche alcuni hanno torto. pensano che funzioni ma non funziona.

[Daniels118]

non è il fatto di fare i compiti.

il problema è che click over come anche alcuni hanno torto. pensano che funzioni ma non funziona.

UAHAHUAHAH STO PIANGENDO DALLE RISATE :ahahah:

[arsenico2009]

scusate tanto :p
mancava una riga di codice per funzionare.

ecco la soluzione:

for (int i=0; i< N; i++){
numeroArray = numeri[i];
pos = generaPos();
numeri[i] = numeri[pos];
numeri[pos] = numeroArray;
}

così funziona perfettamente.

[arsenico2009]

salve ho un'altro problema:

riesco a generare max 100000 numeri.

se prova a cambiare la costante N ( che indica la grandezza dell'array), il compilatore non dà errori ma quando apro l'eseguibile windows mi dice il programma ha smesso di funzionare. Come mai ?

la costante N lo dichiarata così.

const long int N= 1000000;

è possibile che il limite max di una costante è centomila numeri ?

[Daniels118]

No, non è possibile. Posta tutto il codice, ricordati di utilizzare i tag code.

[arsenico2009]

link codice sorgente programma

https://www.dropbox.com/s/bngk221yte0geqd/numeri_casuali.cpp

[!fazz]

link codice sorgente programma

https://www.dropbox.com/s/bngk221yte0geqd/numeri_casuali.cpp

prima cosa al volo

nei parametri di una funzione non si mette la dimensione del vettore
esempio
void caricaNumeri(int numeri[N])

deve diventare
void caricaNumeri(int numeri[])

e lo stesso pure nei prototipi (dove si omette anche il nome )
void caricaNumeri(int[]);

[arsenico2009]

perchè questa cosa ??

tanto funziona lo stesso.

comunque io chiedevo un'altra cosa.

[Daniels118]

Mi sembra strano che riesca a compilare scritto in quel modo... che compilatore usi?
Ho il dubbio che il tipo int nel tuo compilatore sia a 16 bit. In questo caso dovrebbe andare male anche con 100000, ma chissà... prova a trasformare tutti gli int in long int.

[arsenico2009]

scrivo il codice su notepad++ e poi lo compilo dal dos con il programma minigw.

il comando dal dos è: g++ nomeprogramma.cpp -o nomeprogramma.exe

[arsenico2009]

stessa cosa windows mi blocca il programma.

mi dice che il programma ha smesso di funzionare.

è come se vede che lo spazio del'array è grande e quindi me lo blocca.

come cavolo è ?

[Daniels118]

Ah ecco... hai riempito lo stack. Alloca il vettore con malloc.

[arsenico2009]

quindi che dovrei fare ?

[!fazz]

stessa cosa windows mi blocca il programma.

mi dice che il programma ha smesso di funzionare.

è come se vede che lo spazio del'array è grande e quindi me lo blocca.

come cavolo è ?

al 99% esaurisci lo spazio di ram dedicato allo stack

http://stackoverflow.com/questions/156510/increase-stack-size-on-windows-gcc

lo stack non è pensato per contenere grosse quantità di dati per quello devi usare l'heap ma è oggettivamente un pò troppo avanzato per le tue competenze

[Daniels118]

Ah ecco... hai riempito lo stack. Alloca il vettore con malloc.
Allocare il vettore con malloc :D

[!fazz]

Allocare il vettore con malloc :D

miii lasciamo l'heap all'estate (almeno)

se soluzioni attualmente sono due

1) riduci la dimensione del vettore
2) aumenti la dimensione dello stack con un parametro in complilazione,

[arsenico2009]

come impostare l'heap al posto dello stack ?

[!fazz]

come impostare l'heap al posto dello stack ?

lascia perdere, entri in un altro ramo del c++ l'allocazione dinamica della memoria che è di molto al di sopra delle tue competenze attuali

[Daniels118]

@!fazz
Stavo per chiederti se sei il suo professore, poi dopo aver visto la sua risposta ecco cosa mi è successo: :doh:
:D

[clockover]

Scusami se te lo chiedo, ma a cosa ti serve un array di quelle dimensioni? La motivazione di questa cosa qual'è? Nel senso...cosa devi farci con questi numeri mescolati?

[arsenico2009]

in pratica devo fare un esperimento.

un professore ha pensato un algoritmo per generare N numeri casuali diversi.

io voglio dimostrargli che questo metodo è più veloce e quindi impiega meno tempo.

tuttavia per mettere a confronto i due algoritmi bisogna confrontarli con grosse mole di numeri. ecco perchè volevo aumentare la grandezza dell'array.

[ESEMPIO]

[TEST SULLO STESSO COMPUTER:]

1) metodo del professore: x generare 1 miliardo di numeri e salvarli impiega 12 secondi)

2) questo metodo x generare 1 miliardo di numeri ne impiega 6-7 secondi.

ecco il tutto. per giocare un pò con il C++

[!fazz]

in pratica devo fare un esperimento.

un professore ha pensato un algoritmo per generare N numeri casuali diversi.

io voglio dimostrargli che questo metodo è più veloce e quindi impiega meno tempo.

tuttavia per mettere a confronto i due algoritmi bisogna confrontarli con grosse mole di numeri. ecco perchè volevo aumentare la grandezza dell'array.

[ESEMPIO]

[TEST SULLO STESSO COMPUTER:]

1) metodo del professore: x generare 1 miliardo di numeri e salvarli impiega 12 secondi)

2) questo metodo x generare 1 miliardo di numeri ne impiega 6-7 secondi.

ecco il tutto. per giocare un pò con il C++

cioè, tu non conosci neanche la base della programmazione strutturata ma vuoi comunque dire di saperne di più rispetto al professore?

devi capire una cosa non esiste un algoritmo migliore di un altro senza un contesto nel quale collocarlo ergo un algoritmo può andare bene per un determinata dimensione, un altro per un'altra un algoritmo può andare bene su un architettura, ma può avere pessime prestazioni su un altra

[Daniels118]

Poi ci sono anche gli algoritmi che dove li metti li metti vanno sempre male, tipo lo stupid sort :D

[clockover]

Mi piacerebbe ora vedere l'algoritmo del tuo professore e capire (questo non voglio vederlo) che cosa avevo pensato tu. Una semplice spiegazione

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