58
Help us understand the problem. What are the problem?

More than 5 years have passed since last update.

posted at

updated at

Array#sort実装のshuffleは偏る

シャッフル実装

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アルゴリズムを使おう。

関連

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
Sign upLogin
58
Help us understand the problem. What are the problem?