[JAVA] Array con Elementi Ripetuti

[fede0693]

Ciao a tutti, sono nuovo nel forum.
Avrei bisogno gentilmente di alcuni consigli per risolvere il seguente problema.
Sto creando una classe main per testare gli algoritmi di ordinamento su array di interi (generati casualmente tramite la classe Random) ordinati, non ordinati, non ordinati con pochi elementi ripetuti e non ordinati con molti elementi ripetuti. Il mio problema sta nel generare gli ultimi due array con pochi e molti elementi ripetuti.

L'idea che mi è venuta in mente è quella di modificare il range. Un esempio potrebbe essere di questo tipo, vi riporto il codice che ho scritto :

int[] aNonOrdPochiRip = new int[n];
fill(aNonOrdPochiRip, n/2);

int[] aNonOrdMoltiRip = new int[n];
fill(aNonOrdMoltiRip, n/4);

con il metodo fill che riempe l'array di interi casuali con probabilità uniforme da 0 fino a range incluso.

private static void fill(int[] a, int range) {
Random generatore = new Random();
for(int i = 0; i < a.length; i++)
a[i] = generatore.nextInt(range+1);
}

Ho fatto inizialmente una piccola prova su array di lunghezza n = 10 ed effettuando la stampa, gli output sono i seguenti :
POCHI ELEMENTI RIPETUTI : 0, 2, 1, 5, 0, 2, 3, 4, 2, 5
MOLTI ELEMENTI RIPETUTI : 1, 1, 0, 1, 1, 1, 2, 0, 0, 1

Grazie anticipatamente per i consigli!

[andbin]

non ordinati con pochi elementi ripetuti e non ordinati con molti elementi ripetuti. Il mio problema sta nel generare gli ultimi due array con pochi e molti elementi ripetuti.

Ho fatto inizialmente una piccola prova su array di lunghezza n = 10 ed effettuando la stampa, gli output sono i seguenti :
POCHI ELEMENTI RIPETUTI : 0, 2, 1, 5, 0, 2, 3, 4, 2, 5
MOLTI ELEMENTI RIPETUTI : 1, 1, 0, 1, 1, 1, 2, 0, 0, 1

Grazie anticipatamente per i consigli!

Ok ma ... quale è il dubbio o domanda specifica in particolare? Perché il mio dubbio è il modo in cui hai descritto le caratteristiche degli array. Un conto è avere pochi "simboli" poco ripetuti sequenzialmente (quindi molto mescolati) e un altro conto è avere lo stesso pochi "simboli" ma molto ripetuti sequenzialmente.

[fede0693]

Scusa se mi sono espresso male, cerco di spiegarmi meglio.
Intendo avere nel complesso pochi-molti elementi ripetuti...

Ti faccio qualche esempio di come dovrebbe essere l'output

Pochi : 1 2 3 7 1 9
Molti : 1 1 1 1 3 7 9 5 oppure 1 1 2 2 2 6 6 8 9

[andbin]

Intendo avere nel complesso pochi-molti elementi ripetuti...

Ti faccio qualche esempio di come dovrebbe essere l'output

Pochi : 1 2 3 7 1 9
Molti : 1 1 1 1 3 7 9 5 oppure 1 1 2 2 2 6 6 8 9

Sì, ok, grosso modo è come intendevo io.
Dati 4 "simboli" es. A, B, C e D, un conto infatti è avere:

Sequenza 1)
A B A D B C D A C C D B A D A A B C D A C D B A D C C A B

e un altro conto è avere

Sequenza 2)
A A A A B B C B D D D D C C A A B B B B B A A D D D D

La differenza è che la Sequenza 1 è molto casuale ed è data da un "buon" generatore di numeri casuali. Mentre la Sequenza 2 è poco casuale e molto ripetiva, data da un "cattivo" generatore.

Se vuoi ottenere il secondo tipo di sequenza, la cosa più semplice è realizzare un "cattivo" generatore. È molto più facile fare un algoritmo per un "cattivo" generatore piuttosto che per uno "buono".

Quindi a questo punto, ripeto, i tuoi dubbi quali sono ancora? Come fare un "cattivo" generatore?

[fede0693]

ehm...sono un po' confuso a dire il vero...
comunque credo che al prof vada bene qualsiasi delle due. non ha specificato questa sottile "differenza" nell'implementazione. il mio dubbio sta per lo più su quale metodo scegliere tra i due...
ti va di illustrarmi come si implementato in linea di massima tutti e due i metodi? e quale mi consigli?
Sicuramente il "buon" generatore richiederà più tempo ma quando andrò a confrontare i tempi, questi saranno certamente ottimali...
Tieni anche conto che nel main dovrò generare moltissimi array fino a dimensioni molto grandi, ad es. 2 milioni di elementi.

[andbin]

il mio dubbio sta per lo più su quale metodo scegliere tra i due...
ti va di illustrarmi come si implementato in linea di massima tutti e due i metodi?

Il "buon" generatore di numeri casuali l'hai già usato ... è java.util.Random. Stop, non c'è da inventarsi nulla o chissà quale algoritmo (a meno che si debba/voglia farne apposta uno nuovo per motivi "didattici" o simile). Esiste nel framework anche java.security.SecureRandom (estende Random) che però è usato tipicamente in campo crittografico. Dubito che tu abbia bisogno di quel livello di security/casualità ma comunque c'è, se necessario.

Il "cattivo" generatore di numeri casuali nel framework standard di Java non c'è. Quindi o implementi da zero un "cattivo" algoritmo con calcoli/logica varia oppure cerchi di manipolare in qualche modo i valori ottenuti da Random per ottenere un qualcosa di meno casuale.

e quale mi consigli?

Dipende cosa ti è stato chiesto di fare e per cosa.

Tieni anche conto che nel main dovrò generare moltissimi array fino a dimensioni molto grandi, ad es. 2 milioni di elementi.

Ok, nessun problema di per sé, considera poi solo le questioni di occupazione di memoria sul heap-space e aumenta la dimensione massima del heap-space, se necessario.

[fede0693]

ah ok perfetto! grazie mille! continuerò ad usare il java.util.Random senza problemi...
riguardo invece la differenza tra pochi e molti elementi ripetuti?
come faccio a capire il range che gli devo mettere per distinguere i due casi?

[andbin]

riguardo invece la differenza tra pochi e molti elementi ripetuti?
come faccio a capire il range che gli devo mettere per distinguere i due casi?

Per avere sequenze es. 1 1 1 2 2 4 4 4 4 4 3 3 5 5 5 5 5, quindi con molte ripetizioni dello stesso numero, non centra il range dei valori. Centra solo la più o meno "cattiva" casualità. E qui è questione di algoritmo, appunto, non di range.

[fede0693]

scusami ma non riesco proprio a capire
come mai non è una questione di scelta del range? se il range è più piccolo rispetto alla dimensione dell'array il Random sceglie valori che si ripetono...
potresti perfavore mettere giù un esempio di codice?

[andbin]

come mai non è una questione di scelta del range? se il range è più piccolo rispetto alla dimensione dell'array il Random sceglie valori che si ripetono...

java.util.Random ha una casualità molto "buona". Indipendentemente da quanti valori vuoi estrarre e dal range di tali valori, è altamente improbabile che Random, di suo, tiri fuori una sequenza con es. 4 volte lo stesso valore X, poi 3 volte lo stesso valore Y, poi 6 volte lo stesso valore Z.

Se il range è molto piccolo, sì, probabilmente è più facile che ci siano ripetizioni dello stesso numero. Ma in generale la ripetitività di uno stesso numero non è certo il "forte" di Random .... altrimenti non sarebbe un buon generatore di valori casuali!