[javascript] 셔플 링에 JavaScript Array.sort () 메소드를 사용하는 것이 맞습니까?

이 무작위 정렬 결과가 얼마나 무작위인지 측정했습니다.

내 기술은 작은 배열 [1,2,3,4]을 취하고 그것의 모든 (4! = 24) 순열을 만드는 것이었다. 그런 다음 셔플 링 함수를 배열에 여러 번 적용하고 각 순열이 몇 번 생성되는지 계산합니다. 좋은 셔플 링 알고리즘은 모든 순열에 대해 결과를 균등하게 분배하지만 나쁜 것은 균일 한 결과를 생성하지 않습니다.

아래 코드를 사용하여 Firefox, Opera, Chrome, IE6 / 7 / 8에서 테스트했습니다.

놀랍게도, 무작위 정렬과 실제 셔플은 모두 똑같이 균일 한 분포를 만들었습니다. 그래서 (많은 사람들이 제안했듯이) 주요 브라우저는 병합 정렬을 사용하고있는 것 같습니다. 물론 이것은 다른 브라우저를 사용할 수 없다는 것을 의미하지는 않지만,이 임의 정렬 방법이 실제로 사용하기에 충분히 신뢰할 수 있음을 의미합니다.

편집 : 이 테스트는 실제로 무작위 또는 그 부족을 올바르게 측정하지 못했습니다. 내가 게시 한 다른 답변을 참조하십시오.

그러나 성능 측면에서 크리스토프가 제공하는 셔플 기능은 확실한 승자였습니다. 작은 4 요소 어레이의 경우에도 실제 셔플은 임의 정렬보다 약 2 배 빠릅니다!

// Cristoph가 게시 한 셔플 기능.
var shuffle = 함수 (배열) {
    var tmp, current, top = array.length;

    if (top) while (-top) {
        전류 = Math.floor (Math.random () * (top + 1));
        tmp = 배열 ​​[현재];
        배열 [현재] = 배열 ​​[위];
        배열 [상단] = tmp;
    }

    배열 반환;
};

// 랜덤 정렬 함수
var rnd = function () {
  반환 Math.round (Math.random ())-0.5;
};
var randSort = 함수 (A) {
  return A.sort (rnd);
};

var 순열 = function (A) {
  if (A.length == 1) {
    반환 [A];
  }
  다른 {
    var perms = [];
    (var i = 0; i <A.length; i ++) {
      var x = A.slice (i, i + 1);
      var xs = A.slice (0, i) .concat (A.slice (i + 1));
      var subperms = 순열 (xs);
      for (var j = 0; j <subperms.length; j ++) {
        perms.push (x.concat (subperms [j]));
      }
    }
    반환 파마;
  }
};

var test = 함수 (A, 반복, 기능) {
  // 초기화 순열
  var 통계 = {};
  var perms = 순열 (A);
  for (var i in perms) {
    통계 [ ""+ perms [i]] = 0;
  }

  // 여러 번 섞어 통계를 수집
  var start = new Date ();
  for (var i = 0; i <iterations; i ++) {
    var shuffled = func (A);
    통계 [ ""+ shuffled] ++;
  }
  var end = new Date ();

  // 결과 형식
  var arr = [];
  for (통계의 var i) {
    arr.push (i + ""+ stats [i]);
  }
  return arr.join ( "\ n") + "\ n \ n 걸린 시간 :"+ ((end-start) / 1000) + "seconds.";
};

alert ( "무작위 정렬 :"+ 테스트 ([1,2,3,4], 100000, randSort));
alert ( "셔플 :"+ 테스트 ([1,2,3,4], 100000, 셔플));

답변

function RandomSort(a,b) {
    return (0.5 - Math.random());
}

function shuffle(arr) {
  arr.sort(function(a,b) {
    return (0.5 - Math.random());
  });
}

function shuffle2(arr) {
  arr.sort(function(a,b) {
    return (Math.round(Math.random())-0.5);
  });
}

function shuffle3(array) {
  var tmp, current, top = array.length;

  if(top) while(--top) {
    current = Math.floor(Math.random() * (top + 1));
    tmp = array[current];
    array[current] = array[top];
    array[top] = tmp;
  }

  return array;
}

var counts = [
  [0,0,0,0,0],
  [0,0,0,0,0],
  [0,0,0,0,0],
  [0,0,0,0,0],
  [0,0,0,0,0]
];

var arr;
for (var i=0; i<100000; i++) {
  arr = [0,1,2,3,4];
  shuffle3(arr);
  arr.forEach(function(x, i){ counts[x][i]++;});
}

alert(counts.map(function(a){return a.join(", ");}).join("\n"));

function shuffle(array) {
  for (var tmp, cur, top=array.length; top--;){
    cur = (Math.random() * (top + 1)) << 0;
    tmp = array[cur]; array[cur] = array[top]; array[top] = tmp;
  }
  return array;
}

for (var i = 0; i < coords.length; i++)
    coords[i].sortValue = Math.random();

coords.sort(useSortValue)

function useSortValue(a, b)
{
  return a.sortValue - b.sortValue;
}