Зависит ли платформа java.util.Collections.shuffle?

У нас есть требование перетасовать ArrayList с использованием семени

Код примерно такой:

List<String> tempList =  new ArrayList<>()
//code to populdate the tempList
Random rng = new Random(2018);
Collections.shuffle(tempList, rng);

P.S. Причина, по которой мы предоставили статическое случайное начальное число, состоит в том, чтобы убедиться, что он всегда дает один и тот же результат после перетасовки.

Мы заметили, что результат перетасовки на машинах разработки (Mac) отличается от результата на наших машинах сборки (Linux).

Мне интересно, зависит ли сам этот метод от платформы?

Сведения о JDK Mac включен:

Java(TM) SE Runtime Environment (build 1.8.0_171-b11)
Java HotSpot(TM) 64-Bit Server VM (build 25.171-b11, mixed mode)

Сборка машины (мне нужно больше времени, чтобы узнать подробности, так как у меня нет доступа):

jdk1.8.0_162

java random random-seed
person DingDong    schedule 05.08.2018    source источник
comment
Вы используете разные JVM? Или официальный от Oracle (Hotspot)? Какая версия? Можете ли вы предоставить дополнительную информацию о тестовой установке и машинах? А как насчет самого объекта Random? Попробуйте сгенерировать несколько чисел, используя nextInt, и посмотрите, отличаются ли последовательности.   -  person Zabuzard    schedule 06.08.2018
comment
Будет ли он отличаться, если он находится на разных JVM? Я узнаю подробности версии и обновлю вопрос   -  person DingDong    schedule 06.08.2018
comment
Какова цель предсказуемой перетасовки?   -  person LMC    schedule 06.08.2018
comment
Его нужно перетасовать, чтобы список не располагался в алфавитном порядке. Причина, по которой это должно быть предсказуемым, заключается в том, что это один и тот же порядок на машинах разработки и сборки.   -  person DingDong    schedule 06.08.2018
comment
Повторное открытие, потому что, хотя ГСЧ гарантированно генерирует одну и ту же последовательность, разные версии/конфигурации JVM могут по-прежнему использовать разные алгоритмы перетасовки.   -  person Thilo    schedule 06.08.2018
comment
Не должно быть вариаций, даже если версии Java разные. Из документов: «Чтобы Чтобы гарантировать это свойство, для класса Random указываются определенные алгоритмы. Реализации Java должны использовать все показанные здесь алгоритмы для класса Random ради абсолютной переносимости кода Java».   -  person VGR    schedule 06.08.2018
comment
Таким образом, метод перемешивания может отличаться от ОС к ОС, верно?   -  person DingDong    schedule 06.08.2018
comment
Вы заявляете, что проблемный код «что-то вроде» того, что вы опубликовали. Вы на самом деле инициализируете свой экземпляр Random постоянным числовым аргументом? new Random() не будет одинаковым для всех вызовов программы.   -  person VGR    schedule 06.08.2018
comment
Я намеренно инициализирую экземпляр Random с постоянным числовым аргументом, если бы я опубликовал исходный код, это было бы слишком много и слишком отвлекает.   -  person DingDong    schedule 06.08.2018
comment
Как правило, переносимость между JVM или версиями часто не гарантируется. В частности, если вы используете внешнюю JVM вместо Hotspot. Из-за этого вы обычно должны использовать ту же самую JVM и версию, если это возможно. Пожалуйста, проверьте, генерирует ли Random разные последовательности. Если это так, то это ошибка алгоритмов перемешивания. В документации прямо указано, что все реализации Random должны создавать одну и ту же последовательность. Если это не так, реализация не соответствует документации.   -  person Zabuzard    schedule 06.08.2018

Ответы (1)


arrow_upward
0
arrow_downward

Насколько я понимаю, вы спрашиваете, гарантированно ли эта Java-программа печатает bcdea на каждой существующей реализации Java.

import java.util.Random;
import java.util.ArrayList;
import java.util.Collections;

class Main {
    public static void main(String[] args) {
        Random rng = new Random(42);
        ArrayList<String> list = new ArrayList<String>();
        list.add("a");
        list.add("b");
        list.add("c");
        list.add("d");
        list.add("e");
        Collections.shuffle(list, rng);
        for (String s : list) System.out.print(s);
    }
};

tio.run говорит, что он производит одинаковый результат, по крайней мере, между OpenJDK 8 и тем, что они выставляют за JDK. Но это очень маленькая и скучная выборка.

Официальная документация Oracle не обнадеживает:

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

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

То есть Oracle не утверждает, что каждая реализация работает именно так; они даже не удосужились задокументировать, каким образом случайным образом выбирается замененный элемент.

Кстати, я пришел к вашему вопросу после того, как увидел, что Collections.shuffle используется в программном обеспечении системы голосования в США именно с таким предположением: его поведение воспроизводимо независимо от того, какой JDK вы используете. Я согласен, что вообще не ясно, так ли это.

(Кстати, это не относится к C++ std::shuffle. Там разные реализации библиотек могут и делать дают разные перетасовки для одного и того же ввода.)

person Quuxplusone    schedule 24.06.2021