[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 :stordita:

[k0nt3]

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

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 :mbe:

[nuovoUtente86]

....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 :mbe:

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

[k0nt3]

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]

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]

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 :D

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

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

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]

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

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 :fagiano: http://java.sun.com/docs/books/jls/third_edition/html/expressions.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.

[k0nt3]

Il mio errore dipendeva dal fatto che su documentazione non ufficiale avevo letto che nextInt restituiva un numero positivo.
nel caso in cui usi Random.nextInt(numero) allora si che non hai bisogno del Math.abs perchè generi un numero compreso tra 0 compreso e "numero" escluso. quindi se "numero" è positivo generi numeri positivi, altrimenti negativi

[k0nt3]

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.
si anche perchè il massimo valore positivo che può assumere un int è 2^31 quindi 2^32 assolutamente non ha senso

non avrai altro dio all'infuori della javadoc :read:
http://java.sun.com/javase/6/docs/api/java/util/Random.html#nextInt()

EDIT: ops avevo sbagliato! il massimo è 2^31 :fagiano: e il minimo -2^31 (in tutto fanno 2^32 numeri)

[nuovoUtente86]

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

prendo spunto da qui,sperando di non stancarti per farti notare una cosa.
iotizando di fare %numero pari abbastanza piccolo....nel nostro range di numeri estratti a caso avremmo la metà di possibilità di prendere un numero pari grande abbastanza da dare modulo 0.

[nuovoUtente86]

si anche perchè il massimo valore positivo che può assumere un int è 2^31 quindi 2^32 assolutamente non ha senso

non avrai altro dio all'infuori della javadoc :read:
http://java.sun.com/javase/6/docs/api/java/util/Random.html#nextInt()

EDIT: ops avevo sbagliato! il massimo è 2^31 :fagiano: e il minimo -2^31 (in tutto fanno 2^32 numeri)
perona la mia grezza ignoranza: da - 2 31 a 2 31 come arrivi a 2 32 numeri totali...sarà facile ma ora n mi sovviene.

[k0nt3]

prendo spunto da qui,sperando di non stancarti per farti notare una cosa.
iotizando di fare %numero pari abbastanza piccolo....nel nostro range di numeri estratti a caso avremmo la metà di possibilità di prendere un numero pari grande abbastanza da dare modulo 0.
no hai la metà delle possibilità solo nel caso che il numero è 2. se è 3 avrai un terzo delle possibilità ecc...
perona la mia grezza ignoranza: da - 2 31 a 2 31 come arrivi a 2 32 numeri totali...sarà facile ma ora n mi sovviene.
2^31 + 2^31 = 2^31 * 2 = 2^32

[nuovoUtente86]

no hai la metà delle possibilità solo nel caso che il numero è 2. se è 3 avrai un terzo delle possibilità ecc...

2^31 + 2^31 = 2^31 * 2 = 2^32

u che stupido..gia 2 31 * 2 1=2 32