Это быстрее, чтобы перемешать список или генерировать его случайно?

Для использования в алгоритмах сортировки профилирования, я хочу ArrayList<Integer> с целыми миллионами долларов. Границы целых чисел не имеют значения: [0, MAX_VALUE ], [ MIN_VALUE, MAX_VALUE ] и т. д. все в порядке, но я хочу, чтобы они были широко распространены.

Я заметил, что когда я использую этот код:

for (int i=0; i<1_000_000; i++) {
    list.add(i);
}
Collections.shuffle(list);
mergeSorter.sort(list);

shuffle Выполнение вызова занимает около десяти секунд, а сортировка слиянием - всего 2 миллисекунды.

Таким образом, мой вопрос: было бы быстрее генерировать эти числа случайным образом ( list.add((int) (Math.random() * 1_000_000)) ) чем использовать shuffle , и почему?

(Я бы описал это сам, но моего домашнего оборудования недостаточно, чтобы проверить это. Кроме того, я хотел бы получить концептуальное / теоретическое объяснение.)

Источник

2 ответа

Решение

Collections.shuffle() использования Random под капотом.

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]);
        }
    }
}

Если вы посмотрите внимательно, два цикла выполняются.

  • Один для создания нового массива
  • Один для обновления списка.

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

Так что да, выполнение этого самостоятельно увеличит производительность, но временная сложность все равно будет O(n)

Источник

Будет ли быстрее генерировать эти числа случайно (list.add((int) (Math.random() * 1_000_000))) чем использовать shuffle и почему?

Подобные числа быстрее генерировать, но вы получите другой результат!

  • Если вы перетасуете список чисел от 0 до N-1, вы получите список без дубликатов.

  • Если вы сгенерируете потерянное из N случайных чисел в диапазоне от 0 до N-1, вы, вероятно, получите список с дубликатами.

Если генерация N случайных чисел в порядке, то это определенно будет быстрее, чем тасование. Как видно из кода, лучшая версия shuffle включает в себя создание N случайных чисел И выполнение N обменов.

Вызов shuffle занимает около десяти секунд, а сортировка слиянием - всего 2 миллисекунды.

Я не уверен, почему вы сравниваете shuffle и mergesort (или какой сортировщик слияний вы используете!), Но я подозреваю, что расхождение больше связано с тем, как вы закодировали тесты, чем с чем-либо еще. (Похоже, вы, возможно, не учли эффекты разогрева JVM.)

Источник
Другие вопросы по тегам