Blog. Just Blog

Перемешивание массива на JavaScript

Версия для печати Добавить в Избранное Отправить на E-Mail | Категория: Web-мастеру и не только | Автор: ManHunter
Перемешивание массива на JavaScript
Перемешивание массива на JavaScript

Несмотря на особенности сортировки массивов в JavaScript, которые нашли отражение даже в интернет-мемах, без этой самой сортировки не обойтись. Случайное перемешивание массива - тоже своеобразный вариант сортировки. Для его реализации в этих ваших интернетах обычно рекомендуют воспользоваться следующим или каким-то подобным кодом:
  1. var test_array=[1,2,3,4,5,6,7,8,9,10];
  2.  
  3. test_array.sort(
  4.     function() { return (Math.random()-0.5); }
  5. );
  6. // test_array -> перемешанный массив
На первый взгляд функция рабочая, но при тестировании, особенно на больших массивах, результат оставляет желать лучшего. В зависимости от поведения рандомайзера, в массиве могут оставаться целые последовательности неперемешанных элементов.

Если нужно качественное перемешивание массива, то я пользуюсь следующей функцией. Помню, что-то подобное мы делали на школьных уроках информатики.
  1. //-------------------------------------------------
  2. // Функция случайной сортировки массива
  3. //-------------------------------------------------
  4. function shuffle(ar) {
  5.     var jtmp;
  6.     for(var i=0i<ar.lengthi++) {
  7.         // Случайный индекс элемента для обмена
  8.         do {
  9.             j=parseInt(Math.random()*ar.length);
  10.         } while(i==j);
  11.         // Обменять местами два элемента массива
  12.         tmp=ar[i];
  13.         ar[i]=ar[j];
  14.         ar[j]=tmp;
  15.     }
  16.     return ar;
  17. };
  18.  
  19. // Перемешать массив
  20. var test_array=[1,2,3,4,5,6,7,8,9,10];
  21. shuffle(test_array);
  22. // test_array -> перемешанный массив
Такое перемешивание дает более равномерный результат. Для достижения максимального эффекта эту функцию можно вызвать несколько раз подряд или сразу заложить несколько проходов в саму функцию перемешивания массива. Естественно, учитывая при этом объемы обрабатываемых данных.

Поделиться ссылкой ВКонтакте Поделиться ссылкой на Facebook Поделиться ссылкой на LiveJournal Поделиться ссылкой в Мой Круг Добавить в Мой мир Добавить на ЛиРу (Liveinternet) Добавить в закладки Memori Добавить в закладки Google
Просмотров: 156 | Комментариев: 1

Комментарии

Отзывы посетителей сайта о статье
Infocatcher (21.11.2020 в 23:22):
В интернетах встречается рекомендация вот такого:
https://ru.wikipedia.org/wiki/...ный_алгоритм
https://en.wikipedia.org/wiki/...rn_algorithm
Например, вот: https://stackoverflow.com/ques...wer-12646864

Насчет проверки равномерности можно попробовать из массива с несколькими наборами 0…255 собрать черно-белые картинки на canvas'е – чем-то подобным наглядно видно, насколько хорошо сделана реализация самого random().

И можно, если это действительно необходимо, использовать
https://developer.mozilla.org/...RandomValues


Выглядит, впрочем, для большинства нужд чрезмерно:

var arr = [];
for(var i = 1; i <= 10; ++i)
arr.push(i);
shuffle(arr);

function shuffle(arr) {
var i = arr.length;
while(--i) {
  var rnd = Math.floor(random()*(i + 1));
  var tmp = arr[i];
  arr[i] = arr[rnd];
  arr[rnd] = tmp;
}
return arr;
}
function random() {
var crypto = (function() {
  var crypto = window.crypto || window.msCrypto || null;
  if(crypto && "getRandomValues" in crypto && "Uint32Array" in window)
   return crypto;
  return null;
})();
random = crypto
  ? function cryptoRandom() {
   try { // Note: shouldn't throw per new spec
    var rnd = cryptoRandom.__rndArr || (cryptoRandom.__rndArr = new Uint32Array(1));
    crypto.getRandomValues(rnd);
    return rnd[0]/0x100000000;
   }
   catch(e) {
    setTimeout(function() { throw e; }, 0);
    return Math.random();
   }
  }
  : function() {
   return Math.random();
  };
return random();
}

Добавить комментарий

Заполните форму для добавления комментария
Имя*:
Текст комментария (не более 2000 символов)*:

*Все поля обязательны для заполнения.
Комментарии, содержащие рекламу, ненормативную лексику, оскорбления и т.п., а также флуд и сообщения не по теме, будут удаляться. Нарушителям может быть заблокирован доступ к сайту.
Наверх
Powered by PCL's Speckled Band Engine 0.2 RC3
© ManHunter / PCL, 2008-2020
При использовании материалов ссылка на сайт обязательна
Время генерации: 0.06 сек. / MySQL: 2 (0.0029 сек.) / Память: 4.75 Mb
Наверх