Algoritma pengocok adalah masalah acak umum yang kami temui saat bermain game dan menyortir secara acak. Ini dapat diabstraksikan seperti ini: Dapatkan array pesanan acak dari semua bilangan alami dalam M.
Mencari "algoritma perombakan" di Baidu, hasil pertama adalah "Perpustakaan Baidu - Algoritma Perjamuan". Setelah memindai isinya, banyak konten mudah disesatkan dengan tersesat orang lain, termasuk menggunakan daftar tertaut untuk menggantikan array pada akhirnya, yang hanya optimasi terbatas (daftar tautan juga memperkenalkan hilangnya efisiensi baca).
Metode pertama dalam artikel ini dapat dengan mudah digambarkan sebagai: menggambar kartu secara acak dan memasukkannya ke dalam kelompok lain; Gambarlah lagi, gambarlah berulang kali saat Anda menggambar kartu kosong.
"Gambar kartu setelah menggambarnya lagi" akan menyebabkan peningkatan peluang menggambar kartu nanti, yang jelas tidak masuk akal.
Satu langkah dapat dioptimalkan: Setelah kartu ditarik, kartu asli menjadi lebih sedikit. (daripada meninggalkan kartu kosong)
Kodenya adalah sebagai berikut:
Salinan kode adalah sebagai berikut:
Fungsi shuffle_pick_1 (m) // shush // metode menggambar kartu
{
// menghasilkan kartu M.
var arr = array baru (m);
untuk (var i = 0; i <m; i ++) {
arr [i] = i;
}
// Gambarlah satu kartu sekaligus dan letakkan di tumpukan lain. Karena Anda perlu mengekstrak elemen dari array dan menarik semua elemen berikutnya ke depan satu per satu, itu memakan waktu.
var arr2 = array baru ();
untuk (var i = m; i> 0; i--) {
var rnd = math.floor (math.random ()*i);
arr2.push (arr [rnd]);
arr.splice (rnd, 1);
}
return arr2;
}
Ini juga jelas bermasalah, karena jika array besar, menghapus elemen tertentu di tengah akan menyebabkan antrian mengambil langkah maju, yang merupakan tindakan yang sangat memakan waktu.
Ingat tujuan "Mengapa kita menghapus elemen itu?" adalah untuk menghindari kartu kosong.
Selain menghapus elemen itu, apakah kita memiliki cara lain untuk menghapus kartu kosong?
---- Ya, kita hanya perlu meletakkan kartu tak terkejut terakhir di posisi draw.
Jadi, kita dapat mengoptimalkan ide ini sebagai berikut:
Salinan kode adalah sebagai berikut:
fungsi shuffle_pick (m) // shut // metode menggambar kartu untuk mengoptimalkan kartu
{
// menghasilkan kartu M.
var arr = array baru (m);
untuk (var i = 0; i <m; i ++) {
arr [i] = i;
}
// Gambarlah satu kartu sekaligus dan letakkan di tumpukan lain. Letakkan kartu undrawn terakhir di kursi terbuka.
var arr2 = array baru ();
untuk (var i = m; i> 0;) {
var rnd = math.floor (math.random ()*i);
arr2.push (arr [rnd]);
arr [rnd] = arr [-i];
}
return arr2;
}
Selain ide menggambar kartu, kami juga dapat menggunakan ide mengganti kartu.
"Algoritma Baidu Wenku-Shut" menyebutkan ide perubahan kartu: "Ganti dua posisi secara acak, dan pertukarannya N kali total. Semakin besar N, semakin dekat dengan acak."
Pendekatan ini salah. Bahkan jika N sangat besar (misalnya, 10 kartu, 10 sakelar), masih ada kemungkinan besar bahwa "beberapa kartu tidak mengubah posisi sama sekali."
Ikuti ide ini dan buat sedikit penyesuaian: Ubah kartu i-th dengan kartu apa pun, dan ubah saja satu putaran.
Kodenya adalah sebagai berikut:
Salinan kode adalah sebagai berikut:
fungsi shuffle_swap (m) // shush // metode perubahan kartu
{
// menghasilkan kartu M.
var arr = array baru (m);
untuk (var i = 0; i <m; i ++) {
arr [i] = i;
}
// Kartu i-th digunakan untuk mengganti kursi dan Anda dapat mengubahnya untuk satu putaran
untuk (var i = 0; i <m; i ++) {
var rnd = math.floor (math.random ()*(i+1)),
temp = arr [rnd];
arr [rnd] = arr [i];
arr [i] = temp;
}
return arr;
}
In addition to the idea of drawing and changing cards, we can also use the idea of inserting cards: first there is one card, the second card has two positions to be inserted randomly (before or behind the first card), the third card has three positions to be inserted randomly (placed behind, or inserted in the first position, or inserted in the second position), and so on
Kodenya adalah sebagai berikut:
Salinan kode adalah sebagai berikut:
fungsi shuffle_insert_1 (m) // shunt // metode penyisipan kartu
{
// Setiap kali, kartu terbesar dihasilkan dan dimasukkan di depan kartu acak. Karena Anda perlu memasukkan elemen ke dalam array dan memeras semua elemen berikutnya kembali satu per satu, itu memakan waktu.
var arr = [0];
untuk (var i = 1; i <m; i ++) {
arr.splice (math.floor (math.random ()*(i+1)), 0, i);
}
return arr;
}
Kode di atas juga akan memiliki beberapa masalah: ketika jumlah kartu meningkat, menjadi semakin sulit untuk memasukkan kartu, karena memasukkan kartu akan menyebabkan banyak kartu yang mengikuti satu langkah mundur.
Tentu saja, kami juga dapat mengoptimalkan dengan tepat: pertama ada kartu N-1, kartu ke-n ditempatkan di akhir, dan kemudian bertukar posisi dengan kartu apa pun.
Kodenya adalah sebagai berikut:
Salinan kode adalah sebagai berikut:
Fungsi shuffle_insert (m) // shush // versi yang dioptimalkan dari metode penyisipan kartu dapat dibuktikan dengan induksi matematika bahwa shuffle ini seragam.
{
// Setiap kali menghasilkan kartu terbesar dan menukar posisi dengan kartu acak
var arr = array baru (m);
arr [0] = 0;
untuk (var i = 1; i <m; i ++) {
var rnd = math.floor (math.random ()*(i+1));
arr [i] = arr [rnd];
arr [rnd] = i;
}
return arr;
}
Oke, semua kode adalah sebagai berikut. Siswa yang tertarik dapat mencobanya di mesin mereka sendiri untuk melihat apakah efisiensi eksekusi masing -masing dan apakah hasil akhirnya secara teoritis acak.
Salinan kode adalah sebagai berikut:
<Html>
<head>
<meta http-equiv = "konten tipe" content = "text/html; charset = gb2312">
<title> JK: Algoritma pengocok javascript </iteme>
</head>
<body>
<type skrip = "Teks/JavaScript">
Fungsi shuffle_pick_1 (m) // shush // metode menggambar kartu
{
// menghasilkan kartu M.
var arr = array baru (m);
untuk (var i = 0; i <m; i ++) {
arr [i] = i;
}
// Gambarlah satu kartu sekaligus dan letakkan di tumpukan lain. Karena Anda perlu mengekstrak elemen dari array dan menarik semua elemen berikutnya ke depan satu per satu, itu memakan waktu.
var arr2 = array baru ();
untuk (var i = m; i> 0; i--) {
var rnd = math.floor (math.random ()*i);
arr2.push (arr [rnd]);
arr.splice (rnd, 1);
}
return arr2;
}
fungsi shuffle_pick (m) // shut // metode menggambar kartu untuk mengoptimalkan kartu
{
// menghasilkan kartu M.
var arr = array baru (m);
untuk (var i = 0; i <m; i ++) {
arr [i] = i;
}
// Gambarlah satu kartu sekaligus dan letakkan di tumpukan lain. Letakkan kartu undrawn terakhir di kursi terbuka.
var arr2 = array baru ();
untuk (var i = m; i> 0;) {
var rnd = math.floor (math.random ()*i);
arr2.push (arr [rnd]);
arr [rnd] = arr [-i];
}
return arr2;
}
fungsi shuffle_swap (m) // shush // metode perubahan kartu
{
// menghasilkan kartu M.
var arr = array baru (m);
untuk (var i = 0; i <m; i ++) {
arr [i] = i;
}
// Kartu i-th digunakan untuk mengganti kursi dan Anda dapat mengubahnya untuk satu putaran
untuk (var i = 0; i <m; i ++) {
var rnd = math.floor (math.random ()*(i+1)),
temp = arr [rnd];
arr [rnd] = arr [i];
arr [i] = temp;
}
return arr;
}
fungsi shuffle_insert_1 (m) // shunt // metode penyisipan kartu
{
// Setiap kali, kartu terbesar dihasilkan dan dimasukkan di depan kartu acak. Karena Anda perlu memasukkan elemen ke dalam array dan memeras semua elemen berikutnya kembali satu per satu, itu memakan waktu.
var arr = [0];
untuk (var i = 1; i <m; i ++) {
arr.splice (math.floor (math.random ()*(i+1)), 0, i);
}
return arr;
}
Fungsi shuffle_insert (m) // shush // versi yang dioptimalkan dari metode penyisipan kartu dapat dibuktikan dengan induksi matematika bahwa shuffle ini seragam.
{
// Setiap kali menghasilkan kartu terbesar dan menukar posisi dengan kartu acak
var arr = array baru (m);
arr [0] = 0;
untuk (var i = 1; i <m; i ++) {
var rnd = math.floor (math.random ()*(i+1));
arr [i] = arr [rnd];
arr [rnd] = i;
}
return arr;
}
// alert (shuffle_pick (10))
var funcs = [shuffle_pick_1, shuffle_pick, shuffle_swap, shuffle_insert_1, shuffle_insert],
funcNames = ["Draw Card", "Draw Card Optimization", "Card Change", "Card Insert", "Card Insert Optimization"]
M = 10000,
kali = [];
untuk (var i = 0; i <funcs.length; i ++) {
var d0 = tanggal baru ();
funcs [i] (m);
funcNames [i] = (new date () - d0) + '/t' + funcNames [i];
}
waspada (funcnames.join ('/n'));
</script>
</body>
</html>