อัลกอริทึมการสับเป็นปัญหาแบบสุ่มทั่วไปที่เราพบเมื่อเล่นเกมและการเรียงลำดับแบบสุ่ม มันสามารถสรุปได้เช่นนี้: รับอาร์เรย์คำสั่งซื้อแบบสุ่มของตัวเลขธรรมชาติทั้งหมดภายใน M.
การค้นหา "อัลกอริทึม reshuffle" บน Baidu ผลลัพธ์แรกคือ "Library Baidu - อัลกอริทึม reshuffle" หลังจากสแกนเนื้อหาเนื้อหาจำนวนมากเป็นเรื่องง่ายที่จะทำให้คนอื่นหลงผิดรวมถึงการใช้รายการที่เชื่อมโยงเพื่อแทนที่อาร์เรย์ในที่สุดซึ่งเป็นเพียงการเพิ่มประสิทธิภาพที่ จำกัด (รายการลิงก์ยังแนะนำการสูญเสียประสิทธิภาพการอ่าน)
วิธีแรกในบทความนี้สามารถอธิบายได้ง่ายๆว่า: สุ่มวาดการ์ดและใส่ไว้ในกลุ่มอื่น วาดพวกเขาอีกครั้งวาดซ้ำ ๆ เมื่อคุณวาดการ์ดเปล่า
"วาดการ์ดหลังจากวาดพวกเขาอีกครั้ง" จะนำไปสู่โอกาสที่เพิ่มขึ้นของการวาดการ์ดในภายหลังซึ่งเห็นได้ชัดว่าไม่มีเหตุผล
ขั้นตอนเดียวสามารถปรับให้เหมาะสม: หลังจากวาดการ์ดการ์ดต้นฉบับจะน้อยลง (แทนที่จะทิ้งการ์ดเปล่า)
รหัสมีดังนี้:
การคัดลอกรหัสมีดังนี้:
ฟังก์ชั่น shuffle_pick_1 (m) // shush // วิธีการวาดการ์ด
-
// สร้างการ์ด M
var arr = อาร์เรย์ใหม่ (m);
สำหรับ (var i = 0; i <m; i ++) {
arr [i] = i;
-
// วาดการ์ดทีละใบแล้ววางไว้ในกองอื่น เนื่องจากคุณจำเป็นต้องแยกองค์ประกอบจากอาร์เรย์และดึงองค์ประกอบที่ตามมาทั้งหมดไปข้างหน้าทีละตัวจึงใช้เวลานาน
var arr2 = new Array ();
สำหรับ (var i = m; i> 0; i--) {
var rnd = math.floor (math.random ()*i);
arr2.push (arr [rnd]);
arr.splice (rnd, 1);
-
return arr2;
-
นี่เป็นปัญหาที่เห็นได้ชัดเช่นกันเพราะถ้าอาร์เรย์มีขนาดใหญ่การลบองค์ประกอบบางอย่างที่อยู่ตรงกลางจะทำให้คิวก้าวไปข้างหน้าซึ่งเป็นการกระทำที่ใช้เวลานานมาก
จำจุดประสงค์ของ "ทำไมเราถึงลบองค์ประกอบนั้น" คือการหลีกเลี่ยงการ์ดที่ว่างเปล่า
นอกเหนือจากการลบองค์ประกอบนั้นเรามีวิธีอื่นในการลบการ์ดเปล่าหรือไม่?
---- ใช่เราเพียงแค่ต้องใส่การ์ดที่ยังไม่ปลดสายสุดท้ายไว้ในตำแหน่งการวาด
ดังนั้นเราสามารถเพิ่มประสิทธิภาพความคิดนี้ได้ดังนี้:
การคัดลอกรหัสมีดังนี้:
ฟังก์ชั่น shuffle_pick (M) // วิธีการวาดการ์ด // วิธีการวาดการ์ดเพื่อให้ดีที่สุดการ์ด
-
// สร้างการ์ด M
var arr = อาร์เรย์ใหม่ (m);
สำหรับ (var i = 0; i <m; i ++) {
arr [i] = i;
-
// วาดการ์ดทีละใบแล้ววางไว้ในกองอื่น ใส่การ์ด Undrawn ครั้งสุดท้ายลงบนที่นั่งเปิด
var arr2 = new Array ();
สำหรับ (var i = m; i> 0;) {
var rnd = math.floor (math.random ()*i);
arr2.push (arr [rnd]);
arr [rnd] = arr [-i];
-
return arr2;
-
นอกเหนือจากแนวคิดของการวาดการ์ดแล้วเรายังสามารถใช้ความคิดในการเปลี่ยนการ์ด
"อัลกอริทึม Baidu Wenku-Shut" กล่าวถึงแนวคิดการเปลี่ยนการ์ด: "เปลี่ยนตำแหน่งสองตำแหน่งแบบสุ่มและแลกเปลี่ยนพวกเขาทั้งหมด N ครั้งยิ่งใหญ่ยิ่งใหญ่ยิ่งใกล้จะสุ่ม"
วิธีการนี้ผิด แม้ว่า N จะมีขนาดใหญ่มาก (ตัวอย่างเช่น 10 ใบ, สวิตช์ 10 ตัว) แต่ก็ยังมีความเป็นไปได้สูงที่ "การ์ดบางใบไม่เปลี่ยนตำแหน่งเลย"
ทำตามความคิดนี้และทำการปรับเล็กน้อย: เปลี่ยนการ์ด i-th ด้วยการ์ดใดก็ได้และเพียงแค่เปลี่ยนเป็นหนึ่งรอบ
รหัสมีดังนี้:
การคัดลอกรหัสมีดังนี้:
ฟังก์ชั่น shuffle_swap (m) // shush // วิธีการเปลี่ยนการ์ด
-
// สร้างการ์ด M
var arr = อาร์เรย์ใหม่ (m);
สำหรับ (var i = 0; i <m; i ++) {
arr [i] = i;
-
// การ์ด i-th ใช้ในการเปลี่ยนที่นั่งและคุณสามารถเปลี่ยนได้หนึ่งรอบ
สำหรับ (var i = 0; i <m; i ++) {
var rnd = math.floor (math.random ()*(i+1))
temp = arr [rnd];
arr [rnd] = arr [i];
arr [i] = อุณหภูมิ;
-
กลับ arr;
-
นอกเหนือจากความคิดในการวาดและเปลี่ยนการ์ดแล้วเรายังสามารถใช้ความคิดในการแทรกการ์ด: ก่อนอื่นมีการ์ดใบเดียวการ์ดใบที่สองมีสองตำแหน่งที่จะแทรกแบบสุ่ม (ก่อนหรือหลังการ์ดใบแรก) การ์ดใบที่สามมีสามตำแหน่งที่จะแทรกแบบสุ่ม (วางไว้ข้างหลังหรือใส่ในตำแหน่งแรก
รหัสมีดังนี้:
การคัดลอกรหัสมีดังนี้:
ฟังก์ชั่น shuffle_insert_1 (m) // shunt // วิธีการแทรกการ์ด
-
// ในแต่ละครั้งการ์ดที่ใหญ่ที่สุดจะถูกสร้างและใส่ไว้ด้านหน้าการ์ดสุ่ม เนื่องจากคุณจำเป็นต้องแทรกองค์ประกอบลงในอาร์เรย์และบีบองค์ประกอบที่ตามมาทั้งหมดกลับมาทีละหนึ่งมันใช้เวลานาน
var arr = [0];
สำหรับ (var i = 1; i <m; i ++) {
arr.splice (math.floor (math.random ()*(i+1)), 0, i);
-
กลับ arr;
-
รหัสข้างต้นจะมีปัญหาบางอย่าง: เมื่อจำนวนการ์ดเพิ่มขึ้นมันจะกลายเป็นเรื่องยากมากขึ้นเรื่อย ๆ เพราะการแทรกการ์ดจะนำไปสู่การ์ดจำนวนมากที่ย้อนกลับไปหนึ่งก้าว
แน่นอนว่าเรายังสามารถปรับให้เหมาะสมอย่างเหมาะสม: ก่อนอื่นมีการ์ด N-1 การ์ด N-TH จะถูกวางไว้ในตอนท้ายแล้วแลกเปลี่ยนตำแหน่งด้วยการ์ดใด ๆ
รหัสมีดังนี้:
การคัดลอกรหัสมีดังนี้:
ฟังก์ชั่น shuffle_insert (m) // shush // วิธีการใส่การ์ดที่เหมาะสมที่สุดสามารถพิสูจน์ได้โดยการเหนี่ยวนำทางคณิตศาสตร์ว่าการสลับครั้งนี้มีความสม่ำเสมอ
-
// แต่ละครั้งสร้างการ์ดที่ใหญ่ที่สุดและแลกเปลี่ยนตำแหน่งด้วยการ์ดสุ่ม
var arr = อาร์เรย์ใหม่ (m);
arr [0] = 0;
สำหรับ (var i = 1; i <m; i ++) {
var rnd = math.floor (math.random ()*(i+1));
arr [i] = arr [rnd];
arr [rnd] = i;
-
กลับ arr;
-
ตกลงรหัสทั้งหมดมีดังนี้ นักเรียนที่สนใจสามารถลองใช้กับเครื่องของตัวเองเพื่อดูว่าประสิทธิภาพการดำเนินการตามลำดับหรือไม่และผลลัพธ์สุดท้ายคือการสุ่มในทางทฤษฎีหรือไม่
การคัดลอกรหัสมีดังนี้:
<html>
<head>
<meta http-equiv = "content-type" content = "text/html; charset = gb2312">>
<title> jk: อัลกอริทึมการสับเปลี่ยน JavaScript </title>
</head>
<body>
<script type = "text/javascript">
ฟังก์ชั่น shuffle_pick_1 (m) // shush // วิธีการวาดการ์ด
-
// สร้างการ์ด M
var arr = อาร์เรย์ใหม่ (m);
สำหรับ (var i = 0; i <m; i ++) {
arr [i] = i;
-
// วาดการ์ดทีละใบแล้ววางไว้ในกองอื่น เนื่องจากคุณจำเป็นต้องแยกองค์ประกอบจากอาร์เรย์และดึงองค์ประกอบที่ตามมาทั้งหมดไปข้างหน้าทีละตัวจึงใช้เวลานาน
var arr2 = new Array ();
สำหรับ (var i = m; i> 0; i--) {
var rnd = math.floor (math.random ()*i);
arr2.push (arr [rnd]);
arr.splice (rnd, 1);
-
return arr2;
-
ฟังก์ชั่น shuffle_pick (M) // วิธีการวาดการ์ด // วิธีการวาดการ์ดเพื่อให้ดีที่สุดการ์ด
-
// สร้างการ์ด M
var arr = อาร์เรย์ใหม่ (m);
สำหรับ (var i = 0; i <m; i ++) {
arr [i] = i;
-
// วาดการ์ดทีละใบแล้ววางไว้ในกองอื่น ใส่การ์ด Undrawn ครั้งสุดท้ายลงบนที่นั่งเปิด
var arr2 = new Array ();
สำหรับ (var i = m; i> 0;) {
var rnd = math.floor (math.random ()*i);
arr2.push (arr [rnd]);
arr [rnd] = arr [-i];
-
return arr2;
-
ฟังก์ชั่น shuffle_swap (m) // shush // วิธีการเปลี่ยนการ์ด
-
// สร้างการ์ด M
var arr = อาร์เรย์ใหม่ (m);
สำหรับ (var i = 0; i <m; i ++) {
arr [i] = i;
-
// การ์ด i-th ใช้ในการเปลี่ยนที่นั่งและคุณสามารถเปลี่ยนได้หนึ่งรอบ
สำหรับ (var i = 0; i <m; i ++) {
var rnd = math.floor (math.random ()*(i+1))
temp = arr [rnd];
arr [rnd] = arr [i];
arr [i] = อุณหภูมิ;
-
กลับ arr;
-
ฟังก์ชั่น shuffle_insert_1 (m) // shunt // วิธีการแทรกการ์ด
-
// ในแต่ละครั้งการ์ดที่ใหญ่ที่สุดจะถูกสร้างและใส่ไว้ด้านหน้าการ์ดสุ่ม เนื่องจากคุณจำเป็นต้องแทรกองค์ประกอบลงในอาร์เรย์และบีบองค์ประกอบที่ตามมาทั้งหมดกลับมาทีละหนึ่งมันใช้เวลานาน
var arr = [0];
สำหรับ (var i = 1; i <m; i ++) {
arr.splice (math.floor (math.random ()*(i+1)), 0, i);
-
กลับ arr;
-
ฟังก์ชั่น shuffle_insert (m) // shush // วิธีการใส่การ์ดที่เหมาะสมที่สุดสามารถพิสูจน์ได้โดยการเหนี่ยวนำทางคณิตศาสตร์ว่าการสลับครั้งนี้มีความสม่ำเสมอ
-
// แต่ละครั้งสร้างการ์ดที่ใหญ่ที่สุดและแลกเปลี่ยนตำแหน่งด้วยการ์ดสุ่ม
var arr = อาร์เรย์ใหม่ (m);
arr [0] = 0;
สำหรับ (var i = 1; i <m; i ++) {
var rnd = math.floor (math.random ()*(i+1));
arr [i] = arr [rnd];
arr [rnd] = i;
-
กลับ 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", "การเพิ่มประสิทธิภาพการ์ดแทรก"]
M = 10,000
ครั้ง = [];
สำหรับ (var i = 0; i <funcs.length; i ++) {
var d0 = วันที่ใหม่ ();
funcs [i] (m);
funcnames [i] = (วันที่ใหม่ () - d0) + '/t' + funcnames [i];
-
การแจ้งเตือน (funcnames.join ('/n'));
</script>
</body>
</html>