[java] divisione in modulo

[nuovoUtente86]

andando ad accedere ad un array con questa operazione

array[Random.nextInt()%array.length] non si rischia di ottenere con grandissima frequenza l' elemento in posizione 0 o quello in posizione 1 dato che si considera il resto della divisione intera.

[^TiGeRShArK^]

...ovvero?
l'operatore % ti dice qual'è il resto della divisione intera...
La divisione in floating point in teoria non dovrebbe darti alcun resto, anche se nella pratica gli errori di arrotondamento sono sempre scontati.
Cmq c'era un bel thread proprio sulle tecniche per ottenere numeri pseudo-casuali + decenti rispetto al classico '%'.
..solo ke non mi ricordo come si chiama questo thread

[k0nt3]

Originariamente inviato da nuovoUtente86

andando ad accedere ad un array con questa operazione

array[Random.nextInt()%array.length] non si rischia di ottenere con grandissima frequenza l' elemento in posizione 0 o quello in posizione 1 dato che si considera il resto della divisione intera.

quello che fai è dividere un numero intero per un'altro numero intero e ne prendi il resto, che è un numero compreso tra 0 e array.length-1 con probabilità uniforme (se supponiamo che Random.nextInt sia realmente casuale). quindi no

[nuovoUtente86]

be se però ipotizziamo che la lunghezza dell' array sia 2 per tutti i numeri casuali parti avremmo resto 0,accedendo di fatto sempre a quell' elemento.

[^TiGeRShArK^]

Originariamente inviato da nuovoUtente86

be se però ipotizziamo che la lunghezza dell' array sia 2 per tutti i numeri casuali parti avremmo resto 0,accedendo di fatto sempre a quell' elemento.

....e x quelli dispari avremo resto 1 accedendo quindi con *quasi* uguale probabilità ad entrambi gli elementi dell'array.
Ancora mi sfugge dove vuoi arrivare

[nuovoUtente86]

Originariamente inviato da ^TiGeRShArK^

....e x quelli dispari avremo resto 1 accedendo quindi con *quasi* uguale probabilità ad entrambi gli elementi dell'array.
Ancora mi sfugge dove vuoi arrivare

si in un array a dimensione 2 si ma con dimensioni maggiori dovrebbe esserci cmq questo maggiore accesso alla cella 0.

[k0nt3]

Originariamente inviato da nuovoUtente86

si in un array a dimensione 2 si ma con dimensioni maggiori dovrebbe esserci cmq questo maggiore accesso alla cella 0.

assolutamente no! prendi una dimensione di 5, i casi sono:
Random.nextInt = multiplo di 5 -> resto 0
Random.nextInt = (multiplo di 5) + 1 -> resto 1
Random.nextInt = (multiplo di 5) + 2 -> resto 2
Random.nextInt = (multiplo di 5) + 3 -> resto 3
Random.nextInt = (multiplo di 5) + 4 -> resto 4

tutti i casi hanno pari frequenza

[nuovoUtente86]

per quanto quello che dici teoricamente è corretto,so che molti programmatori evitano l' utilizzo del modulo propriamente perchè nella pratica poi potrebbe generarsi carico eccessivo verso alcuni numeri.quello che penso io e che il carico è distribuito equamente estraendo a random tutti i numeri del range,ma andando ad analizzare un numero limitato di estrazioni non si avrebbe certo una distribuzione uniforme.

[k0nt3]

Originariamente inviato da nuovoUtente86

per quanto quello che dici teoricamente è corretto,so che molti programmatori evitano l' utilizzo del modulo propriamente perchè nella pratica poi potrebbe generarsi carico eccessivo verso alcuni numeri.quello che penso io e che il carico è distribuito equamente estraendo a random tutti i numeri del range,ma andando ad analizzare un numero limitato di estrazioni non si avrebbe certo una distribuzione uniforme.

no si avrebbe qualcosa di casuale, cioè una volta tanti 5, la prossima volta tanti 3 e quella dopo tanti 8. se lo fai tante volte vedi che ogni numero compare con la stessa frequenza in media.
non c'è motivo per credere che qualche numero appaia più spesso (in realtà tutto è legato all'assunzione che Random.nextInt estragga numeri veramente casuali, ma questo dipende da come generi il seme.. di norma si usa il timestamp).

[nuovoUtente86]

be ovviamente su un numero grande di estrazione avremmo una certa omogeneita..probabilmente su poche operazioni no.Riporto una mia idea e quella di altri programmatori..sopraattutto di c++

[k0nt3]

Originariamente inviato da nuovoUtente86

be ovviamente su un numero grande di estrazione avremmo una certa omogeneita..probabilmente su poche operazioni no.Riporto una mia idea e quella di altri programmatori..sopraattutto di c++

comunque sia in java sarebbe meglio usare Random.nextInt(length) che come scritto nella javadoc assicura l'uniformità.
magari faccio qualche esperimento

[nuovoUtente86]

ti posto la sequenza generata con 10 estrazioni random (Random.nextInt()%4):
-3 0 1 2 0 -3 1 -1 2 0 -3.

Mi chiedo da dove spuntino quei numeri negativi però.

[nuovoUtente86]

Originariamente inviato da k0nt3

comunque sia in java sarebbe meglio usare Random.nextInt(length) che come scritto nella javadoc assicura l'uniformità.
magari faccio qualche esperimento

si infatti utilizzo quello o meglio Math.random().

[k0nt3]

import java.util.Random;


public class Main {
	private static int[] freqs;
	private static int length;
	private static Random rnd;

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		length = 10;
		freqs = new int[length];
		
		for (int i = 0; i < freqs.length; i++) {
			freqs[i] = 0;
		}
		
		rnd = new Random();
		for (int i = 0; i < 10; i++) {
			++freqs[Math.abs(rnd.nextInt()%length)];
		}
		
		for (int i = 0; i < freqs.length; i++) {
			System.out.println("Frequenza del valore " + i + " è " + freqs[i]);
		}
	}

}

risultato:

Frequenza del valore 0 è 0
Frequenza del valore 1 è 1
Frequenza del valore 2 è 3
Frequenza del valore 3 è 1
Frequenza del valore 4 è 0
Frequenza del valore 5 è 1
Frequenza del valore 6 è 1
Frequenza del valore 7 è 1
Frequenza del valore 8 è 1
Frequenza del valore 9 è 1

poi ho messo:

for (int i = 0; i < 100; i++) {
			++freqs[Math.abs(rnd.nextInt()%length)];
		}

al posto di:

for (int i = 0; i < 10; i++) {
			++freqs[Math.abs(rnd.nextInt()%length)];
		}

risultato:

Frequenza del valore 0 è 8
Frequenza del valore 1 è 8
Frequenza del valore 2 è 9
Frequenza del valore 3 è 8
Frequenza del valore 4 è 16
Frequenza del valore 5 è 6
Frequenza del valore 6 è 10
Frequenza del valore 7 è 7
Frequenza del valore 8 è 17
Frequenza del valore 9 è 11

poi ho messo 1000 al posto di 100

risultato:

Frequenza del valore 0 è 106
Frequenza del valore 1 è 107
Frequenza del valore 2 è 112
Frequenza del valore 3 è 97
Frequenza del valore 4 è 102
Frequenza del valore 5 è 83
Frequenza del valore 6 è 105
Frequenza del valore 7 è 95
Frequenza del valore 8 è 88
Frequenza del valore 9 è 105

poi con 10000 al posto di 1000

risultato:

Frequenza del valore 0 è 1028
Frequenza del valore 1 è 980
Frequenza del valore 2 è 976
Frequenza del valore 3 è 1027
Frequenza del valore 4 è 1038
Frequenza del valore 5 è 1003
Frequenza del valore 6 è 1036
Frequenza del valore 7 è 939
Frequenza del valore 8 è 1009
Frequenza del valore 9 è 964

con 100000:

Frequenza del valore 0 è 9996
Frequenza del valore 1 è 10067
Frequenza del valore 2 è 9998
Frequenza del valore 3 è 9905
Frequenza del valore 4 è 10030
Frequenza del valore 5 è 9844
Frequenza del valore 6 è 10009
Frequenza del valore 7 è 10045
Frequenza del valore 8 è 9965
Frequenza del valore 9 è 10141

come si può vedere il risultato è già accettabile con 1000 iterazioni

[k0nt3]

Originariamente inviato da nuovoUtente86

ti posto la sequenza generata con 10 estrazioni random (Random.nextInt()%4):
-3 0 1 2 0 -3 1 -1 2 0 -3.

Mi chiedo da dove spuntino quei numeri negativi però.

Random.nextInt() genera un Int, non un Int positivo, quindi ci sono anche i numeri negativi. per questo io ho usato Math.abs()

[k0nt3]

con 1000000000 iterazioni

Frequenza del valore 0 è 100007141
Frequenza del valore 1 è 99986788
Frequenza del valore 2 è 100004692
Frequenza del valore 3 è 100000778
Frequenza del valore 4 è 99997784
Frequenza del valore 5 è 99999491
Frequenza del valore 6 è 99996712
Frequenza del valore 7 è 100006047
Frequenza del valore 8 è 99993754
Frequenza del valore 9 è 100006813

[nuovoUtente86]

converrai con me che per l' utilizzo in un array ridotto ad esempio la cadenza non sarebbe cmq accettabilissima.

Il mio errore dipendeva dal fatto che su documentazione non ufficiale avevo letto che nextInt restituiva un numero positivo.

Perdonami un' ultima cosa: la divisione in modulo dovrebbe però essere trasparente al segno,essendo essenzilamente il resto della divisione?

[k0nt3]

Originariamente inviato da nuovoUtente86

converrai con me che per l' utilizzo in un array ridotto ad esempio la cadenza non sarebbe cmq accettabilissima.

Il mio errore dipendeva dal fatto che su documentazione non ufficiale avevo letto che nextInt restituiva un numero positivo.

Perdonami un' ultima cosa: la divisione in modulo dovrebbe però essere trasparente al segno,essendo essenzilamente il resto della divisione?

in java è definito così quindi mi fido http://java.sun.com/docs/books/jls/t...ns.html#239829 un pò più sotto "Remainder Operator %"

per il fatto che non è uniforme sui piccoli numeri non ci si può fare niente.. se vuoi numeri che assomigliano veramente a numeri casuali l'uniformità sui piccoli numeri viene a mancare per definizione

[k0nt3]

quello che conta più che altro è che eseguendo numerosi run dell'applicazione ho sempre distribuzioni diverse e quindi compensandosi vanno a creare l'uniformità di cui sopra.
es:
1° run

Frequenza del valore 0 è 0
Frequenza del valore 1 è 2
Frequenza del valore 2 è 0
Frequenza del valore 3 è 0
Frequenza del valore 4 è 1
Frequenza del valore 5 è 4
Frequenza del valore 6 è 2
Frequenza del valore 7 è 1
Frequenza del valore 8 è 0
Frequenza del valore 9 è 0

2° run

Frequenza del valore 0 è 1
Frequenza del valore 1 è 2
Frequenza del valore 2 è 1
Frequenza del valore 3 è 1
Frequenza del valore 4 è 0
Frequenza del valore 5 è 0
Frequenza del valore 6 è 1
Frequenza del valore 7 è 2
Frequenza del valore 8 è 2
Frequenza del valore 9 è 0

3° run

Frequenza del valore 0 è 0
Frequenza del valore 1 è 2
Frequenza del valore 2 è 2
Frequenza del valore 3 è 1
Frequenza del valore 4 è 0
Frequenza del valore 5 è 0
Frequenza del valore 6 è 4
Frequenza del valore 7 è 0
Frequenza del valore 8 è 0
Frequenza del valore 9 è 1

ecc... a lungo andare le frequenze si uniformano

[nuovoUtente86]

nn sapevo che java nell' operazione di modulo ntenesse conto del segno,personalmente non la trovo una soluzione corretta.

Ti riporto un' estratto della documentazione di cui parlavo,di cui nn faccio il nome:
int i = r.nextInt(int n) da’ un random int tra 0 e n
int i = r.nextInt() da’ un random int tra 0 e 2**32
evidentemente la seconda definizione è scorretta.