[Java] Random

[Strat]

Qualcuno sa dirmi se la funzione che spara numeri random in java e lenta, cioè nextInt?

Spiegandomi meglio: ho realizzato un ordinamento QuickSort in due modi, uno deterministico con pivot il primo elemento e uno randomizzato con una scelta casuale del pivot fra gli elementi inseriti nell'array.
Però, diversamente dalle previsioni, è più veloce la versione deterministica.
Essendo le due realizzate in modo identico apparte per la scelta del pivot, viene spontaneo pensare, almeno e me, che il problema stia nella randomizzaione.
Può essere?

Un'altra ipotesi è quella che io abbia scritto una formula di "restringimento" al range che mi interessa che fa schifo.
eccola:

int choise = from + (generator.nextInt((to-from)));

mi da un valore tra from e to.

Grazie tante, è importante!!!

Ciao!

[PGI]

Non ho mai cronometrato la faccenda, ma potresti provare con un'interfaccia JNI a interrogare un generatore di interi Random scritto in codice nativo.

A dire il vero il "ponte" JNI non è che sia il pezzo più efficiente di Java, però se il codice nativo è sensibilmente più rapido di quello della classe Math potresti averne dei benefici.

[Angus]

...ma i test di confronto tra le due realizzazioni li fai con un ampia scelta di input iniziali, magari di dimensioni piuttosto generose? Il quicksort randomizzato dovrebbe essere statisticamente più veloce, non sempre più veloce.

[Angus]

... il costo dell'istruzione nextInt() è costante, e moltiplica il costo complessivo dell'algoritmo, che nel caso medio , per la versione randomizzata e per quella non randomizzata, è comunque O(n * log(n)), per una costante K. Quindi per input sufficientemente grandi dovresti osservare, statisticamente, che la versione randomizzata è più veloce.

[Angus]

... prova a confrontarne le prestazioni col metodo public static void sort(int[] a) della classe java.util.Arrays di cui cito testualmente la definizione:

"Sorts the specified array of ints into ascending numerical order. The sorting algorithm is a tuned quicksort, adapted from Jon L. Bentley and M. Douglas McIlroy's "Engineering a Sort Function", Software-Practice and Experience, Vol. 23(11) P. 1249-1265 (November 1993). This algorithm offers n*log(n) performance on many data sets that cause other quicksorts to degrade to quadratic performance."

[Strat]

Grazie comunque avevo risolto.

Naturalmete inserisco molti elementi nella sequenza da ordinare, fino a 3000000, con un range di elementi da 0 a 10000000.

E' una sequenza talmente disordinata che i casi cosiddetti cattivi sono rari per tutte le versioni, deterministiche e non.

Comunque la funzione nextInt anche se di un valore trascurabile un po' rallenta, e pur sempre un qualcosa in più in confronto alla versine di Quick Sort che non c'e l'ha.

Ciao e grazie!

[cn73]

Ti ricordi di inizializzare ogni volta il generatore di numeri casuali vero? E' un errore frequente...