Коллекции Java.shuffle делает что? - PullRequest
Новая
       27

Коллекции Java.shuffle делает что?

39 голосов
/ 12 февраля 2010

Недавно я обнаружил, что мне нужно убедиться, что мой список не в порядке. Hibernate был достаточно хорош, чтобы вернуть его в идеальном порядке. Глупая спящая, не читающая мои мысли.

Я посмотрел на свой Java API, и он говорит мне, что его метод случайного выбора делает это:

Произвольно переставляет указанный список, используя источник случайности по умолчанию.

Будучи любопытным джорджем, я хочу знать, что именно это значит. Есть ли математический курс, который я могу пройти, чтобы выучить это? Могу ли я увидеть код? Ява, что ты делаешь с моим ArrayList?!?!?

Чтобы быть более конкретным, какие математические понятия используются здесь?

Ответы [ 2 ]

49 голосов
/ 12 февраля 2010

Да, вы можете посмотреть на код; это в основном делает случай Фишера-Йейтса . Вот оно (спасибо OpenJDK и yay за открытый исходный код :-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]);
        }
    }
}

Метод обмена: 

 private static void swap(Object[] x, int a, int b) {
    Object t = x[a];
    x[a] = x[b];
    x[b] = t;
}
6 голосов
/ 12 февраля 2010

Коллекции JavaDoc предоставляет некоторую информацию об используемом методе случайного перемешивания.

Эта реализация перемещает список назад, от последнего элемента ко второму, многократно меняя произвольно выбранный элемент в «текущую позицию». Элементы выбираются случайным образом из той части списка, которая проходит от первого элемента до текущей позиции включительно.

Так что он начинается в конце и идет по списку назад. На каждом элементе он останавливается и заменяет текущий элемент предыдущим элементом из списка. Источником случайности по умолчанию в этом случае, вероятно, является Случайный объект, созданный с начальным числом по умолчанию.

...