Apakah benar menggunakan metode JavaScript Array.sort () untuk pengocokan?

Saya membantu seseorang dengan kode JavaScript-nya dan mata saya tertangkap oleh bagian yang terlihat seperti itu:

function randOrd(){
  return (Math.round(Math.random())-0.5);
}
coords.sort(randOrd);
alert(coords);

Namun yang pertama saya adalah: hei, ini tidak mungkin berhasil! Tapi kemudian saya melakukan beberapa percobaan dan menemukan bahwa itu memang setidaknya memberikan hasil acak yang bagus.

Kemudian saya melakukan pencarian web dan hampir di bagian atas menemukan artikel dari mana kode ini paling sering disalin. Tampak seperti situs dan penulis yang cukup terhormat ...

Tetapi firasat saya mengatakan kepada saya, bahwa ini pasti salah. Terutama karena algoritma penyortiran tidak ditentukan oleh standar ECMA. Saya pikir algoritma pengurutan yang berbeda akan menghasilkan shuffle yang tidak seragam yang berbeda. Beberapa algoritma penyortiran mungkin bahkan dapat diulang tanpa batas ...

Tapi bagaimana menurutmu?

Dan sebagai pertanyaan lain ... bagaimana saya sekarang pergi dan mengukur seberapa acak hasil dari teknik pengocokan ini?

pembaruan: Saya melakukan beberapa pengukuran dan memposting hasilnya di bawah ini sebagai salah satu jawaban.

Ini tidak pernah menjadi cara favorit saya untuk mengocok, sebagian karena ini spesifik implementasi seperti yang Anda katakan. Secara khusus, saya sepertinya ingat bahwa penyortiran pustaka standar dari Java atau .NET (tidak yakin yang mana) sering dapat mendeteksi jika Anda berakhir dengan perbandingan yang tidak konsisten antara beberapa elemen (misalnya Anda pertama kali mengklaim A < Bdan B < C, tetapi kemudian C < A).

Ini juga berakhir sebagai shuffle yang lebih kompleks (dalam hal waktu eksekusi) daripada yang Anda butuhkan.

Saya lebih suka algoritma shuffle yang secara efektif mem-partisi koleksi menjadi "shuffled" (pada awal koleksi, awalnya kosong) dan "unshuffled" (sisa koleksi). Pada setiap langkah algoritme, pilih elemen acak yang tidak diacak (yang bisa menjadi yang pertama) dan tukar dengan elemen yang tidak diacak - kemudian perlakukan sebagai elemen yang dikocok (mis. Gerakkan secara mental partisi untuk memasukkannya).

Ini O (n) dan hanya membutuhkan n-1 panggilan ke generator angka acak, yang bagus. Ini juga menghasilkan acak acak - elemen apa pun memiliki peluang 1 / n untuk berakhir di setiap ruang, terlepas dari posisi aslinya (dengan asumsi RNG masuk akal). Versi yang diurutkan mendekati distribusi yang merata (dengan asumsi bahwa generator angka acak tidak memilih nilai yang sama dua kali, yang sangat tidak mungkin jika mengembalikan acak ganda) tetapi saya merasa lebih mudah untuk alasan tentang versi acak ini :)

Pendekatan ini disebut shuffle Fisher-Yates .

Saya akan menganggapnya sebagai praktik terbaik untuk mengkodekan shuffle ini sekali dan menggunakannya kembali di mana pun Anda perlu mengacak item. Maka Anda tidak perlu khawatir tentang implementasi semacam dalam hal keandalan atau kompleksitas. Ini hanya beberapa baris kode (yang tidak akan saya coba di JavaScript!)

The artikel Wikipedia pada mengocok (dan khususnya bagian algoritma acak) berbicara tentang menyortir proyeksi acak - itu layak membaca bagian tentang implementasi miskin menyeret pada umumnya, sehingga Anda tahu apa yang harus dihindari.

Setelah Jon membahas teori ini , berikut ini implementasinya:

function shuffle(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;
}

Algoritma adalah O(n), sedangkan penyortiran seharusnya O(n log n). Bergantung pada overhead dari mengeksekusi kode JS dibandingkan dengan sort()fungsi asli , ini dapat menyebabkan perbedaan yang nyata dalam kinerja yang harus meningkat dengan ukuran array.

Dalam komentar untuk jawaban bobobobo , saya menyatakan bahwa algoritma yang dimaksud mungkin tidak menghasilkan probabilitas yang terdistribusi secara merata (tergantung pada implementasinya sort()).

Argumen saya sejalan dengan ini: Algoritma pengurutan memerlukan sejumlah cperbandingan, misalnya c = n(n-1)/2untuk Bubblesort. Fungsi perbandingan acak kami membuat hasil masing-masing perbandingan sama kemungkinannya, yaitu ada hasil yang 2^c sama - sama memungkinkan . Sekarang, setiap hasil harus sesuai dengan salah satu n!permutasi dari entri array, yang membuat pemerataan tidak mungkin dalam kasus umum. (Ini adalah penyederhanaan, karena jumlah aktual perbandingan yang dibutuhkan tergantung pada larik input, tetapi pernyataan tersebut harus tetap berlaku.)

Seperti yang ditunjukkan oleh Jon, ini saja bukan alasan untuk lebih memilih Fisher-Yates daripada menggunakan sort(), karena generator angka acak juga akan memetakan sejumlah terbatas nilai pseudo-acak ke n!permutasi. Tetapi hasil Fisher-Yates masih harus lebih baik:

Math.random()menghasilkan nomor pseudo-acak dalam kisaran [0;1[. Karena JS menggunakan nilai floating point presisi ganda, ini sesuai dengan 2^xnilai yang mungkin ada di mana 52 ≤ x ≤ 63(saya terlalu malas untuk menemukan angka aktual). Distribusi probabilitas yang dihasilkan menggunakan Math.random()akan berhenti berperilaku baik jika jumlah peristiwa atom adalah sama besarnya.

Saat menggunakan Fisher-Yates, parameter yang relevan adalah ukuran array, yang tidak boleh didekati 2^52karena keterbatasan praktis.

Saat menyortir dengan fungsi perbandingan acak, fungsi ini pada dasarnya hanya peduli jika nilai kembali positif atau negatif, jadi ini tidak akan menjadi masalah. Tetapi ada yang serupa: Karena fungsi perbandingan berperilaku baik, 2^chasil yang mungkin, sebagaimana dinyatakan, sama-sama kemungkinan. Jika c ~ n log nkemudian di 2^c ~ n^(a·n)mana a = const, yang paling tidak memungkinkan yang 2^cbesarnya sama dengan (atau bahkan kurang dari) n!dan dengan demikian mengarah pada distribusi yang tidak rata, bahkan jika algoritma pengurutan tempat memetakan ke permutasi secara merata. Jika ini memiliki dampak praktis ada di luar saya.

Masalah sebenarnya adalah bahwa algoritma pengurutan tidak dijamin untuk memetakan ke permutasi secara merata. Sangat mudah untuk melihat bahwa Mergesort melakukan apa yang simetris, tetapi alasan tentang sesuatu seperti Bubblesort atau, yang lebih penting, Quicksort atau Heapsort, tidak.

Intinya: Selama sort()menggunakan Mergesort, Anda harus cukup aman kecuali dalam kasus sudut (setidaknya saya berharap itu 2^c ≤ n!kasus sudut), jika tidak, semua taruhan dibatalkan.

Saya melakukan beberapa pengukuran seberapa acak hasil dari jenis acak ini ...

Teknik saya adalah mengambil array kecil [1,2,3,4] dan membuat semua (4! = 24) permutasi darinya. Lalu saya akan menerapkan fungsi pengocokan ke array sejumlah besar kali dan menghitung berapa kali setiap permutasi dihasilkan. Algoritma pengocokan yang baik akan mendistribusikan hasil cukup merata di semua permutasi, sementara yang buruk tidak akan menciptakan hasil yang seragam.

Menggunakan kode di bawah ini saya uji di Firefox, Opera, Chrome, IE6 / 7/8.

Yang mengejutkan bagi saya, jenis acak dan acak benar-benar menciptakan distribusi yang sama merata. Jadi sepertinya (seperti yang banyak disarankan) browser utama menggunakan semacam penggabungan. Ini tentu saja tidak berarti, bahwa tidak mungkin ada browser di luar sana, itu memang berbeda, tetapi saya akan mengatakan itu berarti, bahwa metode pengurutan acak ini cukup andal untuk digunakan dalam praktik.

EDIT: Tes ini tidak benar-benar mengukur keacakan atau ketiadaannya. Lihat jawaban lain yang saya posting.

Tetapi di sisi kinerja fungsi shuffle yang diberikan oleh Cristoph adalah pemenang yang jelas. Bahkan untuk array empat elemen kecil, shuffle yang sebenarnya dilakukan sekitar dua kali lebih cepat dari pengurutan acak!

// Fungsi shuffle yang diposting oleh Cristoph.
var shuffle = function (array) {
    var tmp, saat ini, atas = array.length;

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

    mengembalikan array;
};

// fungsi sortir acak
var rnd = function () {
  return Math.round (Math.random ()) - 0,5;
};
var randSort = function (A) {
  return A.sort (rnd);
};

var permutasi = function (A) {
  if (A.length == 1) {
    return [A];
  }
  lain {
    var perms = [];
    untuk (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 = permutasi (xs);
      untuk (var j = 0; j <subperms.length; j ++) {
        perms.push (x.concat (subperma [j]));
      }
    }
    mengembalikan izin;
  }
};

var test = function (A, iterations, func) {
  // permutasi init
  var stats = {};
  var perms = permutasi (A);
  for (var i in perms) {
    stats ["" + perms [i]] = 0;
  }

  // kocok berkali-kali dan kumpulkan statistik
  var start = Tanggal baru ();
  untuk (var i = 0; i <iterasi; i ++) {
    var shuffled = func (A);
    statistik ["" + dikocok] ++;
  }
  var end = Tanggal baru ();

  // hasil format
  var arr = [];
  for (var i in stats) {
    arr.push (i + "" + stats [i]);
  }
  return arr.join ("\ n") + "\ n \ nWaktu diambil:" + ((mulai-akhir) / 1000) + "detik.";
};

alert ("sort acak:" + test ([1,2,3,4], 100000, randSort));
alert ("shuffle:" + test ([1,2,3,4], 100000, shuffle));

Menariknya, Microsoft menggunakan teknik yang sama di halaman pilih-acak-peramban mereka.

Mereka menggunakan fungsi perbandingan yang sedikit berbeda:

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

Terlihat hampir sama dengan saya, tetapi ternyata tidak begitu acak ...

Jadi saya membuat beberapa testruns lagi dengan metodologi yang sama yang digunakan dalam artikel yang ditautkan, dan memang - ternyata metode penyortiran acak menghasilkan hasil yang cacat. Kode tes baru di sini:

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"));

Saya telah menempatkan halaman pengujian sederhana di situs web saya yang menunjukkan bias browser Anda saat ini dibandingkan dengan browser populer lainnya menggunakan metode berbeda untuk mengacak. Ini menunjukkan bias mengerikan hanya menggunakan Math.random()-0.5, shuffle 'acak' lain yang tidak bias, dan metode Fisher-Yates disebutkan di atas.

Anda dapat melihat bahwa pada beberapa browser ada peluang 50% bahwa elemen-elemen tertentu tidak akan berubah sama sekali selama 'shuffle'!

Catatan: Anda dapat membuat implementasi shuffle Fisher-Yates oleh @Christoph sedikit lebih cepat untuk Safari dengan mengubah kode menjadi:

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;
}

Hasil pengujian: http://jsperf.com/optimized-fisher-yates

Saya pikir tidak masalah untuk kasus di mana Anda tidak pilih-pilih tentang distribusi dan Anda ingin kode sumber menjadi kecil.

Dalam JavaScript (di mana sumber ditransmisikan secara konstan), kecil membuat perbedaan dalam biaya bandwidth.

Itu adalah retasan, tentu saja. Dalam praktiknya, algoritma pengulangan yang tidak terbatas tidak mungkin. Jika Anda menyortir objek, Anda bisa mengulang melalui array coords dan melakukan sesuatu seperti:

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;
}

(dan kemudian mengulanginya lagi untuk menghapus sortValue)

Tetap saja hack. Jika Anda ingin melakukannya dengan baik, Anda harus melakukannya dengan cara yang keras :)

Sudah empat tahun, tapi saya ingin menunjukkan bahwa metode pembanding acak tidak akan didistribusikan dengan benar, tidak peduli apa pun algoritma pengurutan yang Anda gunakan.

Bukti:

1. Untuk array nelemen, ada n!permutasi yang tepat (yaitu kemungkinan pengocokan).
2. Setiap perbandingan selama pengocokan adalah pilihan antara dua set permutasi. Untuk pembanding acak, ada peluang 1/2 untuk memilih setiap set.
3. Jadi, untuk setiap permutasi p, peluang berakhir dengan permutasi p adalah fraksi dengan penyebut 2 ^ k (untuk beberapa k), karena itu adalah jumlah dari fraksi tersebut (misalnya 1/8 + 1/16 = 3/16 ).
4. Untuk n = 3, ada enam permutasi yang kemungkinannya sama. Peluang setiap permutasi, adalah 1/6. 1/6 tidak bisa diekspresikan sebagai pecahan dengan kekuatan 2 sebagai penyebutnya.
5. Oleh karena itu, jenis flip koin tidak akan pernah menghasilkan distribusi shuffle yang adil.

Satu-satunya ukuran yang mungkin dapat didistribusikan dengan benar adalah n = 0,1,2.

Sebagai latihan, cobalah menggambar pohon keputusan dari algoritma pengurutan yang berbeda untuk n = 3.

Ada celah dalam buktinya: Jika algoritme pengurutan bergantung pada konsistensi pembanding, dan runtime tanpa batas dengan pembanding yang tidak konsisten, ia dapat memiliki jumlah probabilitas tak terbatas, yang diizinkan menambahkan hingga 1/6 bahkan jika setiap penyebut dalam jumlah adalah kekuatan 2. Cobalah untuk menemukan satu.

Juga, jika pembanding memiliki kesempatan tetap untuk memberikan salah satu jawaban (misalnya (Math.random() < P)*2 - 1, untuk konstan P), bukti di atas berlaku. Jika pembanding mengubah peluangnya berdasarkan jawaban sebelumnya, dimungkinkan untuk menghasilkan hasil yang adil. Menemukan pembanding seperti itu untuk algoritma pengurutan tertentu bisa menjadi makalah penelitian.

Jika Anda menggunakan D3 ada fungsi shuffle bawaan (menggunakan Fisher-Yates):

var days = ['Lundi','Mardi','Mercredi','Jeudi','Vendredi','Samedi','Dimanche'];
d3.shuffle(days);

Dan inilah Mike yang akan menjelaskannya:

http://bost.ocks.org/mike/shuffle/

Berikut ini pendekatan yang menggunakan satu array:

Logika dasarnya adalah:

Kode:

for(i=a.length;i--;) a.push(a.splice(Math.floor(Math.random() * (i + 1)),1)[0]);

Bisakah Anda menggunakan Array.sort()fungsi untuk mengocok array - Ya.

Apakah hasilnya cukup acak - Tidak.

Pertimbangkan potongan kode berikut:

var array = ["a", "b", "c", "d", "e"];
var stats = {};
array.forEach(function(v) {
  stats[v] = Array(array.length).fill(0);
});
//stats = {
//    a: [0, 0, 0, ...]
//    b: [0, 0, 0, ...]
//    c: [0, 0, 0, ...]
//    ...
//    ...
//}
var i, clone;
for (i = 0; i < 100; i++) {
  clone = array.slice(0);
  clone.sort(function() {
    return Math.random() - 0.5;
  });
  clone.forEach(function(v, i) {
    stats[v][i]++;
  });
}

Object.keys(stats).forEach(function(v, i) {
  console.log(v + ": [" + stats[v].join(", ") + "]");
})

Output sampel:

a [29, 38, 20,  6,  7]
b [29, 33, 22, 11,  5]
c [17, 14, 32, 17, 20]
d [16,  9, 17, 35, 23]
e [ 9,  6,  9, 31, 45]

Idealnya, jumlah harus didistribusikan secara merata (untuk contoh di atas, semua jumlah harus sekitar 20). Tetapi mereka tidak. Rupanya, distribusi tergantung pada algoritma pengurutan yang diterapkan oleh browser dan bagaimana pengulangan item array untuk pengurutan.

Wawasan lebih lanjut disediakan dalam artikel ini:
Array.sort () tidak boleh digunakan untuk mengocok array

Tidak ada yang salah dengan itu.

Fungsi yang Anda lewati .sort () biasanya terlihat seperti

function sortingFunc (pertama, kedua)
{
  // contoh:
  return first - second;
}

Pekerjaan Anda di sortingFunc adalah mengembalikan:

• angka negatif jika pertama berjalan sebelum detik
• angka positif jika pertama harus pergi setelah yang kedua
• dan 0 jika keduanya sama

Fungsi penyortiran di atas mengatur semuanya.

Jika Anda mengembalikan-dan + secara acak seperti apa yang Anda miliki, Anda mendapatkan pemesanan acak.

Seperti di MySQL:

SELECT * from table ORDER BY rand ()