@seventeenroad

Почему при выносе массива из цикла в глобальную переменную, сортировка имеет разную вероятность?

function shuffle(array){
   array.sort((a,b) => Math.random(a) > Math.random(b)? 1 : -1);
 }

 let count = {
   '123': 0,
   '132': 0,
   '213': 0,
   '231': 0,
   '321': 0,
   '312': 0
 };

 for(let i = 0; i < 1000000; i++){
    let arr = [1, 2, 3];
   shuffle(arr);
   count[arr.join('')]++;

 } 

for (let key in count) {
  alert(`${key}: ${count[key]}`);
}

let arr = [1, 2, 3];

function shuffle(array){
   array.sort((a,b) => Math.random(a) > Math.random(b)? 1 : -1);
 }

 let count = {
   '123': 0,
   '132': 0,
   '213': 0,
   '231': 0,
   '321': 0,
   '312': 0
 };

 for(let i = 0; i < 1000000; i++){
   shuffle(arr);
   count[arr.join('')]++;

 } 

for (let key in count) {
  alert(`${key}: ${count[key]}`);
}
  • Вопрос задан
  • 69 просмотров
Решения вопроса 2
Aetae
@Aetae Куратор тега JavaScript
Тлен
В первом случае ты сортируешь уже отсортированный массив повторно(при каждой сортировке начальное состояние разное), во втором ты сортируешь каждый раз новый(начальное состояние одно и то же).

Использование Math.random в sort в любом случае не даст нормального распределения, т.к. под капотом используется определённый оптимизированный алгоритм сортировки, к тому же браузерозаивисимый и разный для разных случаев.
Как это всё влияет на конечный результат - одному богу известно (или дотошному математику, который засядет с сырцами браузера и распишет километровые формулы, да).
Если нормальное распределение получилось на практике - это совпадение, а не гарантия, что так и будет впредь.

Факт в том, что не надо использовать метод sort ни для чего, кроме его предназначения - детерминированной сортировки.

Используй нормальный алгоритм перемешивания и будет тебе счастье.
первый попасшийся вариант
function shuffle( array ) {	// Shuffle an array
	// 
	// +   original by: Jonas Raoni Soares Silva (http://www.jsfromhell.com)

	for(var j, x, i = array.length; i; j = parseInt(Math.random() * i), x = array[--i], array[i] = array[j], array[j] = x);
	return true;
}
Ответ написан
Комментировать
sergiks
@sergiks Куратор тега JavaScript
♬♬
DISCLAIMER Реализации сортировки могут быть разными.

Добавьте в функцию сортировки вывод итерации, a, b и полученного случайного результата.
spoiler
{ // выполнить в консоли браузера
  const oneTest = () => {
    let iterations = 0;
    [1, 2, 3].sort((a, b) => {
      const result = Math.random() > Math.random() ? 1 : -1;
      console.log(`${iterations}: ${a} vs ${b} = ${result}`);
      iterations++;

      return result;
    });

    return iterations;
  }

  console.clear();
  const totalTests = 10;
  const stats = {};
  
  for (let test = 0; test < totalTests; test++) {
    console.group(`Test ${test + 1} of ${totalTests}`);
    const iterations = oneTest();
    stats[iterations] ??= 0;
    stats[iterations]++;
    console.groupEnd();
  }
  console.log(JSON.stringify(stats, null, 2));
}

Выводит шаги сортировки. И общую статистику: у меня вышло 5 раз по 3, 5 раз по 2 сравнения из 10.

Иногда требуется 3 сравнения, если у первых двух разные знаки.
Иногда достаточно двух, когда у первых двух сравнений знаки совпадают.

Из этой оптимизации и следует неравномерность результатов, когда начальные условия одни и те же. Вспоминайте теор.вер.
Ответ написан
Комментировать
Пригласить эксперта
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы