1. minodisk

    Posted

    minodisk
Changes in title
+Array#sort実装のshuffleは偏る
Changes in tags
Changes in body
Source | HTML | Preview
@@ -0,0 +1,180 @@
+## シャッフル実装
+Fisher-Yatesアルゴリズムで実装された`goodShuffle`と巷で見つけたsort実装された`badShuffle`を5個用意。
+
+```js
+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に近ければ均等にシャッフルされたことになる。
+
+```js
+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近辺なので均等といえる。
+
+```js
+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実装
+
+バラバラで偏りまくり
+
+```js
+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 }
+```
+```js
+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 }
+```
+```js
+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 }
+```
+```js
+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 }
+```
+```js
+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アルゴリズムを使おう。
+
+## 関連
+
+[Array.sort() should not be used to shuffle an array | Lambda](http://sroucheray.org/blog/2009/11/array-sort-should-not-be-used-to-shuffle-an-array/)
+[Will It Shuffle?](http://bost.ocks.org/mike/shuffle/compare.html)