Как это работает с Math Rand? - PullRequest
Новая
       41

Как это работает с Math Rand?

1 голос
/ 15 апреля 2020

Я видел этот код, чтобы перетасовать список: 

public static void shuffle(List<Integer> numbers) {
        if(numbers == null || numbers.isEmpty()) return;
        for(int i = 0; i < numbers.size(); ++i) {
            int index = (int) (i + Math.random()*(numbers.size() - i));
            swap(numbers, i, index);
        }
    }

Код, кажется, работает, но я не понимаю этот фрагмент: 

            int index = (int) (i + Math.random()*(numbers.size() - i));

В основном это i + R*(n-i) но как это гарантирует, что: i) мы не получим индекс выхода за границы или ii) я не буду изменять тот же элемент, то есть index == i, и случайное перемешивание не будет таким случайным?

Ответы [ 5 ]

2 голосов
/ 15 апреля 2020

Math.random() возвращает равномерное случайное число в интервале [0, 1), а numbers.size() - i, в идеале, масштабирует это число до интервала [0, numbers.size() - i). Например, если i равно 2, а размер списка равен 5, в идеальном случае таким образом выбирается случайное число в интервале [0, 3). Наконец, к номеру добавляется i, а приведение (int) отбрасывает дробную часть числа. Таким образом, в этом примере случайное целое число в [2, 5) (т. Е. 2, 3 или 4) генерируется случайным образом, так что на каждой итерации число в индексе X меняется на себя или число, следующее за ним ,

Однако здесь есть одна тонкость. Из-за природы чисел с плавающей точкой и ошибки округления при масштабировании числа, в крайне редких случаях вывод Math.random()*(numbers.size() - i) может быть равен numbers.size() - i, даже если Math.random() выводит число, которое исключает 1. ошибка округления может привести к тому, что идиома Math.random()*(numbers.size() - i) смещает некоторые результаты по сравнению с другими. Например, это происходит всякий раз, когда 2 ^ 53 не делится на numbers.size() - i, поскольку Math.random() использует java.util.Random под колпаком, и его алгоритм генерирует числа с точностью 53 бита. Из-за этого Math.random() - не лучший способ написания этого кода, и вместо этого код мог бы использовать метод, специально разработанный для генерации случайных целых чисел (такой как nextInt метод java.util.Random). См. Также этот вопрос и этот вопрос .

РЕДАКТИРОВАТЬ: Как выясняется, идиома Math.random() * integer не создает проблему, которую он может вернуть integer, по крайней мере, когда integer является любым положительным int и округление до ближайшего Режим округления используется как в Java. См этот вопрос .

1 голос
/ 15 апреля 2020

Math.random () всегда возвращает число с плавающей точкой от 0 (включительно) до 1 (исключая). Поэтому, когда вы делаете Math.random()*(numbers.size() - i), результат всегда будет между 0 (включительно) и n-i (исключительно).

Затем вы добавляете i к нему в i + Math.random()*(numbers.size() - i).

Теперь результат, как вы можете видеть, будет между i (включительно) и n (исключительно).

После этого вы приводите его к int. Когда вы приводите double к int, вы усекаете его, поэтому теперь значение индекса будет где-то из `` i to n - 1``` (включительно для обоих).

Следовательно, вы будете не иметь ArrayIndexOutOfBoundsException, поскольку он всегда будет как минимум на 1 меньше размера массива.

Однако значение индекса может быть равно i, так что да, вы правы в том, что число может поменяйся собой и останься там. Это прекрасно.

1 голос
/ 15 апреля 2020

  1. У вас есть список от 1 до 50 дюймов.

  2. Так что получите случайное значение от 0 до 49 включительно, чтобы проиндексировать его. скажем, это 30.

  3. Получить элемент по индексу 30.

  4. Теперь замените элемент по индексу 30 на элемент по индексу 49.

  5. В следующий раз создайте число от 0 до 48 включительно. 49 никогда не будет достигнут, и номер, который был там, занимает слот последнего использованного номера.

  6. Продолжайте этот процесс, пока вы не исчерпаете список.

Примечание: выражение (int)(Math.random() * n) будет генерировать случайное число от 0 до n-1 включительно, поскольку Math.random генерирует число от 0 до 1 exclusive.

0 голосов
/ 15 апреля 2020

Вместо использования такого пользовательского метода я рекомендую использовать OOTB Collections.shuffle . Отметьте this , чтобы понять логи c, реализованные для Collections.shuffle.

Анализ вашего кода:

Math.random () возвращает double значение с положительным знаком, большее или равное 0.0 и меньшее 1.0.

Теперь давайте предположим, что numbers.size() = 5 и dry запустят for l oop: 

When i = 0, index = (int) (0 + Math.random()*(5 - 0)) = (int) (0 + 4.x) = 4
When i = 1, index = (int) (1 + Math.random()*(5 - 1)) = (int) (1 + 3.x) = 4
When i = 2, index = (int) (2 + Math.random()*(5 - 2)) = (int) (2 + 2.x) = 4
When i = 3, index = (int) (3 + Math.random()*(5 - 3)) = (int) (3 + 1.x) = 4
When i = 4, index = (int) (4 + Math.random()*(5 - 4)) = (int) (4 + 0.x) = 4

Как видите, значение index будет оставаться 4 на каждой итерации, когда numbers.size() = 5.

Ваши запросы:

как это гарантирует, что: i) мы не получим индекс выхода за пределы

Как уже объяснялось выше при использовании прогона dry, он никогда не будет go за пределами .

или ii) Я не буду изменять тот же элемент, т.е. index == i, и случайное перемешивание не будет таким случайным?

swap(numbers, i, index); меняет местами элемент по индексу i с элементом по индексу 4 каждый раз, когда numbers.size() = 5. Это иллюстрируется следующим примером:

Скажем, numbers = [1, 2, 3, 4, 5] 

When i = 0, numbers will become [5, 2, 3, 4, 1]
When i = 1, numbers will become [5, 1, 3, 4, 2]
When i = 2, numbers will become [5, 1, 2, 4, 3]
When i = 3, numbers will become [5, 1, 2, 3, 4]
When i = 4, numbers will become [5, 1, 2, 3, 4]
0 голосов
/ 15 апреля 2020
  1. int index = (int) (i + Math.random()*(numbers.size() - i)); - важно отметить, что Math.random () сгенерирует число, которое принадлежит <0; 1). Таким образом, оно никогда не превысит предел dry, так как эксклюзивный максимум будет: i + 1 * (number.size () -i) = number.size </li>
  2. Эта точка действительна, это может произойти.
...