Сгенерируйте два не повторяющихся случайных числа в диапазоне с помощью Javascript - сосредоточьтесь на производительности скорости
Я хочу сгенерировать 1000 объектов и поместить их в массив стека.
Внутри объекта есть 2 случайных и не повторяющихся числа.
Диапазон от 0 до 4.
Я хочу найти метод с лучшими показателями скорости.
Оценка тестов производительности: 34664
const stack = [];
for (let i = 0; i < 1000; i++) {
const range = [0, 1, 2, 3, 4];
let r = Math.round(Math.random() * (range.length - 1));
let x = range[r];
range.splice(r, 1);
let y = range[Math.round(Math.random() * (range.length - 1))];
stack.push({ x: x, y: y });
}
Оценка теста производительности: 41618
const stack = [];
for (let i = 0; i < 1000; i++) {
let range = [0, 1, 2, 3, 4];
let shuffled = shuffleArray(range);
let x = shuffled[0];
let y = shuffled[shuffled.length - 1];
stack.push({ x: x, y: y });
}
function shuffleArray(array) {
for (let i = array.length - 1; i > 0; i--) {
const j = Math.floor(Math.random() * (i + 1));
[array[i], array[j]] = [array[j], array[i]];
}
}
Ответы 1
Кажется медленным"? Почему вы так думаете? Вы проводили бенчмарк? Он слишком медленный для ваших нужд? Но да, есть некоторые моменты, чтобы сделать его правильным и быстрым...
Во-первых, slice здесь неправильно, вы, вероятно, имеете в виду splice.
Затем вы создаете новый массив на каждой итерации, это дорого. Тем более, если вы тоже splice делаете это. Лучше было бы, переключая элементы в существующем массиве. И, наконец, вам не нужно вычислять range.length-1 дважды на каждой итерации. Вы знаете, что значения будут 4 и 3...
Так что я бы сделал это так
let
stack = [],
range = [0,1,2,3,4];
for (let i = 0; i < 1000; i++){
let
a = Math.floor(Math.random()* 5),
b = Math.floor(Math.random()* 4),
x = range[a];
range[a] = range[4];
range[4] = x;
stack.push({ x, y: range[b]});
}
Как это работает:
Существует только один массив со всеми возможными значениями. Сначала выберите два случайных индекса: a в диапазоне [0, 4] и b в диапазоне [0, 3]. Тогда ваше первое случайное значение — это элемент с индексом a. Теперь поменяйте местами элемент с индексом a на последний элемент в массиве. Ваше второе случайное значение теперь является элементом с индексом b. Эти два значения должны быть разными (даже если a === b), потому что b никогда не сможет выбрать самый последний элемент массива. Это простая вариация классического алгоритма "Фишера-Йейтса"...
Небольшое примечание: stack объявлен как объект, но я предполагаю, что вы имеете в виду, что это массив.
Отличный ответ! Также обратите внимание, что если длина массива ограничена 4 или небольшим числом, массивы, из которых можно выбрать y, можно легко перечислить. { 0: [1,2,3,4], 1: [0,2,3,4], ...}
Оценка: 6421931, круто!
@TomFan - любопытно, сильно ли помогает моя идея (поиск объекта или 1 шаг в случайном порядке). Если вам это нравится, пожалуйста, напишите здесь оценку этой идеи.
Заменить: a = Math.random() * 5 | 0, b = Math.random() * 4 | 0, счет 6579393, быстрее
@danh для такого небольшого количества возможностей (всего 20 разных пар) вы также можете перечислить их все заранее, например [[0,1],[0,2], ..., [1,0],[1,2],...,[5,4]], а затем в цикле просто выбрать одну из пар случайным образом. В зависимости от того, сколько существует разных пар, сколько значений вам нужно и какой генератор случайных чисел вы используете, это также может быть быстрее. Но опять же, это должно быть определено эталоном
Вы можете объявить переменные вне цикла for, а затем переназначить их внутри цикла for. Как/где вы проводите тесты производительности?