Qiita Teams that are logged in
You are not logged in to any team

Log in to Qiita Team
Community
OrganizationAdvent CalendarQiitadon (β)
Service
Qiita JobsQiita ZineQiita Blog
Help us understand the problem. What is going on with this article?

Array#sort実装のshuffleは偏る

More than 5 years have passed since last update.

シャッフル実装

Fisher-Yatesアルゴリズムで実装されたgoodShuffleと巷で見つけたsort実装のbadShuffleを5個用意。

var goodShuffle = function (arr) {
  var i, j, temp;
  arr = arr.slice();
  i = arr.length;
  if (i === 0) {
    return arr;
  }
  while (--i) {
    j = Math.floor(Math.random() * (i + 1));
    temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
  }
  return arr;
};

var badShuffle1 = function (arr) {
  return arr.slice().sort(function () {
    return Math.round(Math.random() * 2) - 1;
  });
};

var badShuffle2 = function (arr) {
  return arr.slice().sort(function () {
    return Math.round(Math.random());
  });
};

var badShuffle3 = function (arr) {
  return arr.slice().sort(function () {
    return Math.random() - Math.random();
  });
};

var badShuffle4 = function (arr) {
  return arr.slice().sort(function () {
    return parseInt(Math.random() * 3, 10) - 1;
  });
};

var badShuffle5 = function (arr) {
  return arr.slice().sort(function () {
    if (Math.random() > 0.5) {
      return 1;
    } else {
      return -1;
    }
  });
};

均等に分布しているかを調べるメソッドを実装

同じ配列に対してシャッフルし、何番目に配置されたかを記録。1000回繰り返して平均を出すプログラムを実装。10個の要素をシャッフルするので、全ての要素でこの値が4.5に近ければ均等にシャッフルされたことになる。

var array = ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J'];
var times = 1000;
var trial = function (shuffle) {
  var arr, average, elem, i, j, len;
  average = {};
  for (i = 0, len = array.length; i < len; i++) {
    average[array[i]] = 0;
  }
  i = times;
  while (i--) {
    arr = shuffle(array);
    for (j = 0, len = arr.length; j < len; j++) {
      elem = arr[j];
      average[elem] += j;
    }
  }
  for (elem in average) {
    average[elem] /= times;
  }
  return average;
};

結果

Fisher-Yatesアルゴリズム

4.5近辺なので均等に混ざっているといえる。

console.log(trial(goodShuffle));
{ A: 4.579,
  B: 4.358,
  C: 4.487,
  D: 4.575,
  E: 4.541,
  F: 4.341,
  G: 4.522,
  H: 4.519,
  I: 4.646,
  J: 4.432 }

Array#sort実装

元のインデックスに沿って並ぶので全然混ざらない。

console.log(trial(badShuffle1));
{ A: 0.38,
  B: 1.16,
  C: 2.023,
  D: 2.985,
  E: 3.949,
  F: 5.01,
  G: 6.013,
  H: 6.915,
  I: 7.896,
  J: 8.669 }
console.log(trial(badShuffle2));
{ A: 1.539,
  B: 1.55,
  C: 2.288,
  D: 3.108,
  E: 4.079,
  F: 4.876,
  G: 5.665,
  H: 6.565,
  I: 7.314,
  J: 8.016 }
console.log(trial(badShuffle3));
{ A: 1.65,
  B: 1.674,
  C: 2.255,
  D: 3.123,
  E: 4.014,
  F: 4.788,
  G: 5.748,
  H: 6.471,
  I: 7.327,
  J: 7.95 }
console.log(trial(badShuffle4));
{ A: 0.724,
  B: 1.155,
  C: 2.119,
  D: 2.929,
  E: 3.967,
  F: 4.991,
  G: 5.949,
  H: 6.956,
  I: 7.707,
  J: 8.503 }
console.log(trial(badShuffle5));
{ A: 1.624,
  B: 1.653,
  C: 2.117,
  D: 3.068,
  E: 3.899,
  F: 4.94,
  G: 5.779,
  H: 6.625,
  I: 7.296,
  J: 7.999 }

結論

Fisher-Yatesアルゴリズムを使おう。

関連

minodisk
冷やし中華はじめました
resily
OKR導入・運用改善コンサルティングと、自社開発のクラウドOKRツール『Resily』を展開するスタートアップ
https://resily.com/
Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away