1. บทนำสู่การจัดเรียงถัง
การเรียงลำดับของ Bucket เป็นอัลกอริทึมการเรียงลำดับแบบนับ หลักการทำงานคือการแบ่งข้อมูลออกเป็นจำนวนที่ จำกัด ของถังและแต่ละถังจะถูกจัดเรียงแยกกัน (เป็นไปได้ที่จะใช้อัลกอริทึมการเรียงลำดับอื่น ๆ หรือจัดเรียงต่อไปในลักษณะที่เกิดขึ้นซ้ำ) เมื่อค่าในข้อมูลที่จะจัดเรียงมีการกระจายอย่างสม่ำเสมอความซับซ้อนของเวลาในการเรียงลำดับถังคือθ (n) การเรียงลำดับของถังนั้นแตกต่างจากการเรียงลำดับอย่างรวดเร็วไม่ใช่การเรียงลำดับการเปรียบเทียบและไม่ได้รับผลกระทบจากขีด จำกัด ที่ต่ำกว่าของความซับซ้อนของเวลา o (nlogn)
การเรียงลำดับถังจะดำเนินการใน 4 ขั้นตอนต่อไปนี้:
(1) ตั้งจำนวนถังว่างจำนวนคงที่
(2) ใส่ข้อมูลลงในถังที่เกี่ยวข้อง
(3) เรียงลำดับข้อมูลในแต่ละถังที่ไม่ว่างเปล่า
(4) ประกบข้อมูลจากถังที่ไม่ว่างเปล่าเพื่อรับผลลัพธ์
การเรียงลำดับถังส่วนใหญ่เหมาะสำหรับข้อมูลจำนวนเต็มขนาดเล็กและมีการกระจายอย่างอิสระและเท่าเทียมกัน จำนวนข้อมูลที่สามารถคำนวณได้มีขนาดใหญ่และตรงตามเวลาที่คาดหวังเชิงเส้น
2. การสาธิตอัลกอริทึมการเรียงลำดับถัง
ตัวอย่างเช่นขณะนี้มีชุดข้อมูล [7, 36, 65, 56, 33, 60, 110, 42, 42, 94, 59, 22, 83, 84, 63, 77, 67, 101] จะเรียงลำดับจากขนาดเล็กไปใหญ่ได้อย่างไร?
ขั้นตอนการดำเนินการ:
(1) ตั้งค่าจำนวนถังเป็น 5 ถังเปล่าค้นหาค่าสูงสุดที่ 110 และค่าต่ำสุดที่ 7 และช่วงของแต่ละถังคือ 20.8 = (110-7+1)/5
(2) สำรวจข้อมูลต้นฉบับใส่ไว้ในถังที่เกี่ยวข้องกับโครงสร้างรายการที่เชื่อมโยง หมายเลข 7, ค่าดัชนีถังคือ 0, สูตรการคำนวณคือพื้น ((7 7) / 20.8), หมายเลข 36, ค่าดัชนีถังคือ 1, พื้นสูตรการคำนวณ ((36 7) / 20.8)
(3) เมื่อแทรกข้อมูลไปยังถังที่มีดัชนีเดียวกันเป็นครั้งที่สองให้กำหนดขนาดของตัวเลขที่มีอยู่และตัวเลขที่แทรกใหม่ในถังและแทรกตามลำดับจากซ้ายไปขวาจากขนาดเล็กไปใหญ่ ตัวอย่างเช่นเมื่อใส่ถังที่มีดัชนี 2 ใส่เมื่อแทรก 63 มี 4 หมายเลข 56, 59, 60 และ 65 ในถังแล้วหมายเลข 63 จะถูกแทรกไปทางซ้าย 65
(4) รวมถังที่ไม่ว่างเปล่ารวม 0, 1, 2, 3 และ 4 ถังตามลำดับจากซ้ายไปขวา
(5) รับโครงสร้างของการจัดเรียงถัง
3. การใช้งานโปรแกรม NodeJS
ไม่ใช่เรื่องยากที่จะใช้อัลกอริทึมที่เป็นผู้ใหญ่เช่นการเรียงลำดับถัง ตามแนวคิดข้างต้นฉันเขียนโปรแกรมง่ายๆเพื่อนำไปใช้ ฉันรู้สึกว่าส่วนที่ลำบากที่สุดคือการใช้ JavaScript เพื่อจัดการรายการที่เชื่อมโยง
รหัสจริงมีดังนี้:
'ใช้ เข้มงวด';//////////////////////////////////////////////////////// - - - - - - - เรียงลำดับ ([1,4,1,5,3,2,3,3,3,2,5,2,8,9,2,1], 5) * เรียงลำดับ ([1,4,1,1,5,3,2,3,3,2,5,2,8,9,9,2,1], 5,0,5) */การส่งออก นับ = นับ || (นับ> 1? นับ: 10); // ตัดสินค่าสูงสุดและค่าต่ำสุด var min = arr [0], max = arr [0]; สำหรับ (var i = 1; i <arr.length; i ++) {min = min <arr [i]? ขั้นต่ำ: arr [i]; สูงสุด = สูงสุด> arr [i]? สูงสุด: arr [i]; } var delta = (สูงสุด - min + 1) / count; // console.log (min+","+max+","+delta); // เริ่มต้น bucket var buckets = []; // ข้อมูลการจัดเก็บเป็น bucket สำหรับ (var i = 0; i <arr.length; i ++) {var idx = math.floor ((arr [i] - min) /delta); // ดัชนีถังถ้า (buckets [idx]) {// bucket ที่ไม่ว่างเปล่า var bucket = buckets [idx]; var insert = false; // แทรกหินธง l.retraVersal (bucket, ฟังก์ชั่น (รายการ, เสร็จแล้ว) {ถ้า (arr [i] <= item.v) {// เล็กกว่า, แทรก l.append (รายการ, _val (arr [i])); if (! แทรก) {// มากกว่า, แทรก l.append (bucket, _val (arr [i])); }} else {// bucket var bucket = l.init (); L.Append (Bucket, _val (arr [i])); buckets [idx] = bucket; // การใช้งานรายการลิงก์}} var result = []; สำหรับ (var i = 0, j = 0; i <count; i ++) {l.retraversal (buckets [i], ฟังก์ชั่น (รายการ) {// console.log (i+":"+item.v); ผลลัพธ์ [j ++] = item.v;}); } return result;} // linked list storage object function _val (v) {return {v: v}}เรียกใช้โปรแกรม:
var algo = ต้องการ ('./ index.js'); var data = [7, 36, 65, 56, 33, 60, 110, 42, 42, 94, 59, 22, 83, 84, 63, 77, 67, 101]; console.log (ข้อมูล); console.log (algo.bucketsort.sort (ข้อมูล, 10)); // 10 ถังเอาท์พุท:
7, 22, 33, 36, 42, 42, 56, 67, 67, 77, 83, 84, 94, 101, 110] [7, 22, 33, 36, 42, 42, 56, 59, 60, 63, 65, 67, 77, 83, 84, 94, 101 63, 65, 67, 77, 83, 84, 94, 101, 110] [7, 22, 33, 36, 42, 42, 56, 59, 60, 63, 65, 67, 77, 83, 84, 94, 101, 110] 84, 94, 101, 110] [7, 22, 33, 36, 42, 42, 56, 59, 60, 63, 65, 67, 77, 83, 84, 94, 101, 110] [7, 22, 33, 36, 42, 42, 56, 59, 63
สิ่งที่ต้องอธิบายคือ:
(1) เรียงลำดับในถังสามารถนำไปใช้ในระหว่างกระบวนการแทรกตามที่อธิบายไว้ในโปรแกรม หรือสามารถแทรกได้โดยไม่ต้องเรียงลำดับจากนั้นจัดเรียงระหว่างกระบวนการผสานและการเรียงลำดับที่รวดเร็วสามารถเรียกได้
(2) รายการที่เชื่อมโยง ใน API พื้นฐานของโหนดมีการใช้งานรายการที่เชื่อมโยง ฉันไม่ได้ใช้โดยตรง แต่เรียกมันผ่านแพ็คเกจ LinkList: https://github.com/nodejs/node-v0.x-archive/blob/master/lib/_linklist.js
4. กรณี: สถิติการเรียงลำดับของ Bucket เกี่ยวกับคะแนนการสอบเข้าวิทยาลัย
หนึ่งในสถานการณ์แอพพลิเคชั่นที่มีชื่อเสียงที่สุดสำหรับการเรียงลำดับถังคือการนับคะแนนของการสอบเข้าวิทยาลัย จำนวนผู้สมัครสอบเข้าวิทยาลัยแห่งชาติในหนึ่งปีคือ 9 ล้านและคะแนนเป็นมาตรฐานโดยมีอย่างน้อย 200 และสูงสุด 900 ไม่มีทศนิยม หากมีการจัดเรียงตัวเลข 9 ล้านตัวเราควรทำอย่างไร?
การวิเคราะห์อัลกอริทึม:
(1) หากคุณใช้การเรียงลำดับการเปรียบเทียบการเรียงลำดับอย่างรวดเร็วความซับซ้อนของเวลาเฉลี่ยคือ O (nlogn) = O (9000000*log9000000) = 144114616 = 144 ล้านเปรียบเทียบ
(2) หากคุณใช้การเรียงลำดับแบบนับการเรียงลำดับและความซับซ้อนโดยเฉลี่ยคุณสามารถควบคุมความซับซ้อนเชิงเส้นได้ เมื่อสร้างถัง 700 ถังหนึ่งถังจาก 200 นาทีถึง 900 นาที, o (n) = o (90000000) มันเทียบเท่ากับการสแกนข้อมูล 900w ชิ้นหนึ่งครั้ง
เราเรียกใช้โปรแกรมเพื่อเปรียบเทียบการเรียงลำดับอย่างรวดเร็วและการจัดเรียงที่เก็บในครั้งเดียว
// สร้างข้อมูล 100w ชิ้นใน [200,900] ช่วงเวลาปิดข้อมูล var = algo.data.randomdata (1,000*1,000,200,900); var s1 = วันที่ใหม่ (). getTime (); Algo.quicksort.sort (data) Buckets var s3 = วันที่ใหม่ (). getTime (); console.log ("เวลา Quicksort: %sms", s2-s1); console.log ("เวลาเก็บ: %SMS", S3-S2);เอาท์พุท:
เวลา Quicksort: 14768msbucket เวลา: 1089ms
ดังนั้นสำหรับกรณีของการให้คะแนนการสอบเข้าวิทยาลัยการเรียงลำดับถังจึงเหมาะสมกว่า! การใช้อัลกอริทึมที่เหมาะสมของเราในสถานการณ์ที่เหมาะสมจะนำการปรับปรุงประสิทธิภาพไปสู่โปรแกรมนอกเหนือจากฮาร์ดแวร์
5. การวิเคราะห์ต้นทุนการเรียงลำดับถัง
แต่...
การเรียงลำดับของ Bucket ใช้ความสัมพันธ์การทำแผนที่ของฟังก์ชั่นลดงานเปรียบเทียบเกือบทั้งหมด ในความเป็นจริงการคำนวณค่า F (k) ของการเรียงลำดับของการเรียงลำดับเทียบเท่ากับการแบ่งตามลำดับอย่างรวดเร็วและได้แบ่งข้อมูลจำนวนมากออกเป็นบล็อกข้อมูลที่สั่งโดยทั่วไป (ถัง) จากนั้นคุณจะต้องทำการเปรียบเทียบขั้นสูงและการเรียงลำดับข้อมูลจำนวนเล็กน้อยในถัง
ความซับซ้อนของเวลาของการเรียงลำดับของคำหลัก n แบ่งออกเป็นสองส่วน:
(1) การวนรอบเพื่อคำนวณฟังก์ชั่นการแมปแบบถังของแต่ละคำหลักและความซับซ้อนในเวลานี้คือ o (n)
(2) ใช้อัลกอริทึมการเรียงลำดับการเปรียบเทียบขั้นสูงเพื่อจัดเรียงข้อมูลทั้งหมดในแต่ละถังด้วยความซับซ้อนของเวลาของ ∑O (Ni*logni) โดยที่ NI คือจำนวนข้อมูลของถัง i-th
เห็นได้ชัดว่าส่วน (2) เป็นปัจจัยกำหนดประสิทธิภาพของการเรียงลำดับของถัง การลดจำนวนข้อมูลในถังเป็นวิธีเดียวที่จะปรับปรุงประสิทธิภาพ (เนื่องจากความซับซ้อนของเวลาเฉลี่ยที่ดีที่สุดตามการเรียงลำดับการเปรียบเทียบสามารถเข้าถึง o (n*logn) เท่านั้น) ดังนั้นเราต้องพยายามอย่างเต็มที่เพื่อทำสองจุดต่อไปนี้:
(1) ฟังก์ชั่นการแมป F (k) สามารถจัดสรรข้อมูล n ให้กับถัง M ได้อย่างสม่ำเสมอเพื่อให้แต่ละถังมีปริมาณข้อมูล [n/m]
(2) พยายามเพิ่มจำนวนบาร์เรล ในกรณีที่รุนแรงแต่ละถังสามารถรับข้อมูลได้เพียงข้อมูลเดียวเท่านั้นซึ่งจะหลีกเลี่ยงการดำเนินการเรียงลำดับ "เปรียบเทียบ" ของข้อมูลในถัง แน่นอนว่ามันไม่ใช่เรื่องง่ายที่จะทำเช่นนี้ เมื่อปริมาณข้อมูลมีขนาดใหญ่ฟังก์ชั่น F (k) จะทำให้จำนวนคอลเลกชันถังขนาดใหญ่และของเสียในพื้นที่นั้นร้ายแรง นี่คือการแลกเปลี่ยนระหว่างค่าใช้จ่ายและพื้นที่
สำหรับข้อมูลที่จะจัดเรียงและถัง M ความซับซ้อนของเวลาในการเรียงลำดับถังเฉลี่ยของข้อมูลแต่ละถัง [n/m] คือ:
o (n)+o (m*(n/m)*log (n/m)) = o (n+n*(logn-logm)) = o (n+n*logn-n*logm)
เมื่อ n = m นั่นคือเมื่อมีเพียงข้อมูลเดียวต่อถังภายใต้ขีด จำกัด ประสิทธิภาพที่ดีที่สุดของการเรียงลำดับถังสามารถเข้าถึง o (n)
6. สรุป
ความซับซ้อนของเวลาเฉลี่ยของการเรียงลำดับถังคือเส้นตรง o (n+c) โดยที่ c = n*(logn-logm) หากจำนวนบาร์เรล M มีขนาดใหญ่ขึ้นเมื่อเทียบกับ N เดียวกันประสิทธิภาพของมันจะสูงขึ้นและความซับซ้อนของเวลาที่ดีที่สุดถึง o (n) แน่นอนความซับซ้อนของพื้นที่ของการเรียงลำดับของถังคือ o (n+m) หากข้อมูลอินพุตมีขนาดใหญ่มากและจำนวนถังมีขนาดใหญ่มากต้นทุนพื้นที่จะมีราคาแพงอย่างไม่ต้องสงสัย นอกจากนี้การเรียงลำดับของถังยังคงมีเสถียรภาพ
ที่จริงแล้วฉันมีความรู้สึกอื่น: ในบรรดาอัลกอริทึมการค้นหาความซับซ้อนของเวลาที่ดีที่สุดของอัลกอริทึมการค้นหาที่ใช้การเปรียบเทียบคือ O (logn) ตัวอย่างเช่นการค้นหาครึ่งต้นต้นไม้ไบนารีที่สมดุลต้นไม้สีแดงและสีดำ ฯลฯ อย่างไรก็ตามตารางแฮชมีประสิทธิภาพการค้นหาระดับเชิงเส้น O (c) (ประสิทธิภาพการค้นหาถึง o (1) ในกรณีที่ไม่มีความขัดแย้ง) มาดูกันดีกว่า: ความคิดและการจัดเรียงถังของตารางแฮชเป็นเพลงเดียวกันหรือไม่?