27 votos

Java Colecciones.shuffle está haciendo qué?

Recientemente me encontré con la necesidad de estar seguro de que mi lista no estaba en orden. Hibernate era lo suficientemente bueno para devolver en perfecto orden. Tonto de hibernación, por no leer mi mente.

Miré a mi API de Java y me dice que su shuffle método:

Al azar permutes la lista especificada mediante un defecto de la fuente de aleatoriedad.

Siendo el jorge el curioso que soy, quiero saber qué significa esto exactamente. Hay un curso de matemáticas que puedo tomar para aprender de esto? Puedo ver el código? Java, ¿qué estás haciendo para mi ArrayList?!?!?

Para ser más específicos, que los conceptos matemáticos se utilizan aquí?

36voto

Chris Jester-Young Puntos 102876

Sí, usted puede mirar en el código; que básicamente hace una aleatorización de Fisher-Yates. Aquí es (gracias OpenJDK, y ¡guay de código abierto :-P):

public static void shuffle(List<?> list, Random rnd) {
    int size = list.size();
    if (size < SHUFFLE_THRESHOLD || list instanceof RandomAccess) {
        for (int i=size; i>1; i--)
            swap(list, i-1, rnd.nextInt(i));
    } else {
        Object arr[] = list.toArray();

        // Shuffle array
        for (int i=size; i>1; i--)
            swap(arr, i-1, rnd.nextInt(i));

        // Dump array back into list
        ListIterator it = list.listIterator();
        for (int i=0; i<arr.length; i++) {
            it.next();
            it.set(arr[i]);
        }
    }
}

El método de intercambio:

 private static void swap(Object[] x, int a, int b) {
    Object t = x[a];
    x[a] = x[b];
    x[b] = t;
}

6voto

Bill the Lizard Puntos 147311

Las Colecciones de JavaDoc da algo de información sobre la selección del método utilizado.

Esta aplicación se recorre la lista hacia atrás, desde el último elemento hasta el segundo, en repetidas ocasiones de intercambio al azar elemento seleccionado en la "posición actual". Los elementos son seleccionados al azar de la parte de la lista que va desde el primer elemento hasta la posición actual, inclusive.

Así que empieza por el final y paseos de la lista hacia atrás. En cada elemento se detiene y se intercambia el elemento actual con un elemento anterior de la lista. El "default fuente de aleatoriedad" en este caso es probablemente una al Azar objeto creado con una semilla por defecto.

Iteramos.com

Iteramos es una comunidad de desarrolladores que busca expandir el conocimiento de la programación mas allá del inglés.
Tenemos una gran cantidad de contenido, y también puedes hacer tus propias preguntas o resolver las de los demás.

Powered by:

X