вторник, 22 ноября 2011 г.

JavaScript: Случайные элементы массива

Родилось из C#-овой, но на JavaScript наглядней.

Нужно выбрать из массива 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);
}
И работать будет просто замечательно:

Комментариев нет:

Отправить комментарий