Родилось из C#-овой, но на JavaScript наглядней.
Нужно выбрать из массива N случайных элементов. Как это сделать быстро?
Если длина массива <= N - это очевидно. А если нет? Сначала склонируем массив:
Потом создадим новый массив и скопируем в него нужное число элементов, а из оригинала удалим:
Нужно выбрать из массива N случайных элементов. Как это сделать быстро?
Если длина массива <= N - это очевидно. А если нет? Сначала склонируем массив:
Object.prototype.clone = function() {
var newObj = (this instanceof Array) ? [] : {};
for (i in this) {
if (i == 'clone') continue;
newObj[i] = (this[i] && typeof this[i] == "object") ? this[i].clone() : this[i];
return newObj;
};
Потом создадим новый массив и скопируем в него нужное число элементов, а из оригинала удалим:
function selectRemoveAdd(arr, max)
{
var arrLength = arr.length;
if(max >= arrLength)
return arr.clone();
var newArray = [];
var cloneArray = arr.clone();
var i = 0, newPos = 0;
while(i++ < max)
{
newPos = getRandom(arrLength);
newArray.push(cloneArray[newPos]);
cloneArray.splice(newPos, 1);
arrLength--;
}
return newArray;
}
Такой вариант обычно предлагают на форумах. Но зачем создавать ещё одни массив? Можно взять исходный и удалить всё лишнее:
var arrLength = arr.length; if(max >= arrLength) return arr.clone(); var newArray = arr.clone(); while(arrLength-- > max) newArray.splice(getRandom(arrLength), 1); return newArray;Какой вариант быстрее? Правильный ответ, что быстрее оба, но по-разному. Если N меньше arr.length / 2, то первый, если больше - то второй. Поэтому самый красивый и правильный способ - это:
function selectRemoveOnly(arr, max)
{
var arrLength = arr.length;
var newArray = arr.clone();
while(arrLength-- > max)
newArray.splice(getRandom(arrLength), 1);
return newArray;
}
function selectRemoveAdd(arr, max)
{
var arrLength = arr.length;
var newArray = [];
var cloneArray = arr.clone();
var i = 0, newPos = 0;
while(i++ < max)
{
newPos = getRandom(arrLength);
newArray.push(cloneArray[newPos]);
cloneArray.splice(newPos, 1);
arrLength--;
}
return newArray;
}
function selectOptimised(arr, max)
{
if(max >= arr.Length)
return arr.clone();
if(max <= arr.length / 2)
return selectRemoveAdd(arr, max);
else
return selectRemoveOnly(arr, max);
}
И работать будет просто замечательно:
