สรุปปัญหาที่พบในการเรียงลำดับส่วนหน้า

ดูเหมือนว่ามีความเข้าใจผิดในวงกลมส่วนหน้าเสมอ: ส่วนหน้าไม่สามารถใช้ความรู้อัลกอริทึมได้ เป็นเวลานานทุกคนอาจได้รับอิทธิพลจากคำพูดนี้ จนกว่าฉันจะพบกับความต้องการผลิตภัณฑ์เมื่อไม่นานมานี้ฉันมองย้อนกลับไปและพบว่านี่ไม่ใช่กรณี

การเรียงลำดับส่วนหน้า

สถานการณ์การเรียงลำดับส่วนหน้า

ส่วนหน้าผ่านเงื่อนไขการเรียงลำดับไปยังแบ็คเอนด์เป็นพารามิเตอร์การร้องขอและแบ็คเอนด์จะส่งคืนผลลัพธ์การเรียงลำดับเป็นการตอบสนองต่อการร้องขอไปยังส่วนหน้าซึ่งเป็นการออกแบบทั่วไป แต่มันไม่เหมาะสำหรับผลิตภัณฑ์บางอย่าง

ลองนึกภาพสถานการณ์: เมื่อคุณใช้แอพอาหารคุณมักจะเปลี่ยนวิธีการเรียงลำดับเรียงลำดับตามราคาแล้วจัดเรียงตามคะแนน

ในการผลิตจริงเนื่องจากปัจจัยเช่นต้นทุนเซิร์ฟเวอร์เมื่อการสืบค้นข้อมูลเดียวกลายเป็นคอขวดประสิทธิภาพโดยรวมมันก็ถือว่าเป็นการเพิ่มประสิทธิภาพประสิทธิภาพโดยการเรียงลำดับในส่วนหน้า

การเรียงลำดับอัลกอริทึม

ฉันรู้สึกว่าไม่จำเป็นต้องแนะนำสิ่งนี้ ในฐานะอัลกอริทึมพื้นฐานในวิทยาศาสตร์คอมพิวเตอร์คำอธิบายจะถูกคัดลอกโดยตรงจาก Wikipedia

วรรคนี้มีอยู่ที่นี่อย่างหมดจดเพื่อจุดประสงค์ในการสืบทอดครั้งแรก (มนุษย์) และที่สอง (shu)

การเรียงลำดับ JavaScript

เนื่องจากเราพูดถึงการเรียงลำดับส่วนหน้าเราจะนึกถึง Array.prototype.sort อินเตอร์เฟสดั้งเดิมของ JavaScript โดยธรรมชาติ

อินเทอร์เฟซนี้มีอยู่ตั้งแต่ ECMAScript 1st Edition มาดูกันว่าคำอธิบายของมันมีลักษณะอย่างไรในข้อกำหนดล่าสุด

array.prototype.sort ข้อกำหนด

Array.prototype.sort(compareFn)

การคัดลอกรหัสมีดังนี้:

องค์ประกอบของอาร์เรย์นี้ถูกจัดเรียง การเรียงลำดับไม่จำเป็นต้องเสถียร (นั่นคือองค์ประกอบที่เปรียบเทียบความเท่าเทียมไม่จำเป็นต้องอยู่ในลำดับเดิม) หากเปรียบเทียบไม่ได้กำหนดไว้ควรเป็นฟังก์ชั่นที่ยอมรับสองอาร์กิวเมนต์ x และ y และส่งคืนค่าลบถ้า x <y, zero ถ้า x = y หรือค่าบวกถ้า x> y

เห็นได้ชัดว่าข้อมูลจำเพาะไม่ได้ จำกัด สิ่งที่อัลกอริทึมการ sort ที่นำไปใช้ภายในคืออะไร แม้แต่การใช้งานอินเทอร์เฟซก็ไม่จำเป็นต้อง จัดเรียงเสถียร สิ่งนี้สำคัญมากและจะมีส่วนร่วมอีกหลายครั้งต่อไป

ในบริบทนี้การเรียงลำดับส่วนหน้าขึ้นอยู่กับการใช้งานเฉพาะของแต่ละเบราว์เซอร์ ดังนั้นเบราว์เซอร์กระแสหลักจะใช้การเรียงลำดับได้อย่างไร ต่อไปเราจะเปรียบเทียบ Chrome , Firefox และ Microsoft Edge สั้น ๆ ตามลำดับ

การใช้งานในโครเมี่ยม

เครื่องยนต์จาวาสคริปต์ของ Chrome คือ V8 เนื่องจากเป็นโอเพ่นซอร์สคุณสามารถดูซอร์สโค้ดได้โดยตรง

array.js ทั้งหมดถูกนำไปใช้ในภาษา JavaScript เห็นได้ชัดว่าส่วนวิธีการเรียงลำดับนั้นซับซ้อนกว่าการเรียงลำดับอย่างรวดเร็วที่ฉันเคยเห็น แต่เห็นได้ชัดว่าอัลกอริทึมหลักยังคงเป็นการเรียงลำดับอย่างรวดเร็ว เหตุผลสำหรับอัลกอริทึมที่ซับซ้อนคือ V8 ได้ทำการปรับให้เหมาะสมสำหรับการพิจารณาประสิทธิภาพมากมาย (ฉันจะพูดถึงเรื่องต่อไป)

การดำเนินการใน Firefox

เป็นไปไม่ได้ที่จะพิจารณาว่าอัลกอริทึมการเรียงลำดับอาร์เรย์ที่เครื่องยนต์ JavaScript ของ Firefox กำลังจะใช้ [3]

ตามข้อมูลที่มีอยู่ Spidermoney ใช้การรวมการเรียงลำดับภายใน

การใช้งานใน Microsoft Edge

ส่วนหลักของรหัสสำหรับจักระเครื่องยนต์ JavaScript ของ Microsoft Edge เปิดให้บริการใน GitHub ในต้นปี 2559

โดยการดูที่ซอร์สโค้ดเราจะพบว่าอัลกอริทึมการเรียงลำดับอาร์เรย์ของ Chakra ยังใช้การเรียงลำดับอย่างรวดเร็ว และเมื่อเทียบกับ V8 มันใช้การเรียงลำดับที่รวดเร็วอย่างหมดจดโดยไม่มีร่องรอยของการเพิ่มประสิทธิภาพประสิทธิภาพใน V8 เลย

ปัญหาเกี่ยวกับการเรียงลำดับอาร์เรย์ JavaScript

อย่างที่เราทราบกันดีว่าการเรียงลำดับอย่างรวดเร็วเป็นอัลกอริทึมการเรียงลำดับที่ไม่เสถียรในขณะที่การเรียงลำดับแบบผสานเป็นอัลกอริทึมการเรียงลำดับที่เสถียร เนื่องจากความแตกต่างในการเลือกอัลกอริทึมของเครื่องยนต์ที่แตกต่างกันส่วนหน้าอาศัยรหัส JavaScript ที่ดำเนินการโดยอาร์เรย์อินเตอร์เฟส prototype.sort และเอฟเฟกต์การเรียงลำดับจริงที่ดำเนินการในเบราว์เซอร์นั้นไม่สอดคล้องกัน

ความแตกต่างในความมั่นคงในการเรียงลำดับจะต้องถูกเรียกใช้โดยสถานการณ์เฉพาะก่อนที่จะมีปัญหา ในหลายกรณีการเรียงลำดับที่ไม่เสถียรจะไม่มีผลกระทบใด ๆ

หากไม่จำเป็นต้องมีความมั่นคงในการเรียงลำดับของอาร์เรย์ในการพัฒนาโครงการจริงคุณสามารถเห็นสิ่งนี้ได้จริงและความแตกต่างของการใช้งานระหว่างเบราว์เซอร์นั้นไม่สำคัญ

แต่ถ้าโครงการกำหนดให้การเรียงลำดับต้องมีเสถียรภาพการมีอยู่ของความแตกต่างเหล่านี้จะไม่ตรงกับความต้องการ เราต้องทำงานพิเศษเพื่อสิ่งนี้

ตัวอย่างเช่น:

กฎการชนะขั้นสุดท้ายสำหรับระบบการประมูลใบอนุญาตยานยนต์ในเมืองบางแห่งคือ:

1. เรียงลำดับตามราคาย้อนกลับ;

2. ราคาเดียวกันจะถูกจัดเรียงในเชิงบวกตามลำดับการเสนอราคา (เช่นเวลาการส่งราคา)

หากการเรียงลำดับเสร็จสิ้นในส่วนหน้าผู้ชนะที่แสดงในเบราว์เซอร์โดยใช้การเรียงลำดับอย่างรวดเร็วมีแนวโน้มที่จะไม่สอดคล้องกับความคาดหวัง

สำรวจความแตกต่าง

ก่อนที่จะหาวิธีแก้ปัญหาจำเป็นต้องสำรวจสาเหตุของปัญหา

ทำไม Chrome ใช้การเรียงลำดับอย่างรวดเร็ว

ในความเป็นจริงสถานการณ์นี้มีอยู่ตั้งแต่ต้น

Chrome Beta ได้รับการปล่อยตัวเมื่อวันที่ 2 กันยายน 2551 อย่างไรก็ตามไม่นานหลังจากการเปิดตัวนักพัฒนาบางคนส่งข้อเสนอแนะข้อผิดพลาด #90 ไปยังกลุ่มพัฒนาโครเมียม การจัดเรียงการจัดเรียงอาร์เรย์ของ V8 นั้นไม่เสถียร

การสนทนาปัญหาข้อผิดพลาดนี้ครอบคลุมมาก จนถึงวันที่ 10 พฤศจิกายน 2558 นักพัฒนายังคงให้ความเห็นเกี่ยวกับการดำเนินการเรียงลำดับอาเรย์ใน V8

ในเวลาเดียวกันเรายังสังเกตเห็นว่าปัญหาได้ถูกปิด อย่างไรก็ตามมีการเปิดใหม่โดยสมาชิกในทีมพัฒนาในเดือนมิถุนายน 2013 เป็นข้อมูลอ้างอิงสำหรับการอภิปรายของข้อกำหนด ECMASCript ถัดไป

และข้อสรุปสุดท้ายของ ES-Discuss คือ

การคัดลอกรหัสมีดังนี้:

มันไม่เปลี่ยนแปลง เสถียรเป็นส่วนย่อยของความไม่เสถียร และในทางกลับกันทุกอัลกอริทึมที่ไม่เสถียรจะส่งคืนผลลัพธ์ที่เสถียรสำหรับอินพุตบางอย่าง ประเด็นของมาร์คคือการต้องการ“ ไม่เสถียรเสมอ” ไม่มีความหมายไม่ว่าคุณจะเลือกภาษาใด

/Andreas

ตามที่อธิบายไว้ในข้อกำหนด ECMASCript 2015 ที่สรุปไว้ก่อนหน้านี้ในบทความนี้

ลักษณะของเวลา

IMHO ปัญหานี้ได้รับการรายงานในตอนต้นของการเปิดตัวของ Chrome ซึ่งอาจมีลักษณะพิเศษของตัวเองในเวลา

ดังที่ได้กล่าวไว้ข้างต้น Chrome เวอร์ชันแรกได้รับการปล่อยตัวในเดือนกันยายน 2551 ตามสถิติจาก StatCounter เบราว์เซอร์ทั้งสองที่มีส่วนแบ่งการตลาดสูงสุดในช่วงเวลานั้นคือ IE (IE6 และ IE7 ในเวลานั้น) และ Firefox โดยมีส่วนแบ่งการตลาดถึง 67.16% และ 25.77% ตามลำดับ กล่าวอีกนัยหนึ่งส่วนแบ่งการตลาดรวมของเบราว์เซอร์ทั้งสองเกิน 90%

ตามสถิติอัลกอริทึมการเรียงลำดับเบราว์เซอร์อื่นเบราว์เซอร์ทั้งสองที่มีส่วนแบ่งการตลาดมากกว่า 90% ใช้การเรียงลำดับอาเรย์ที่มีเสถียรภาพ ดังนั้นจึงมีเหตุผลที่จะถูกสอบสวนโดยนักพัฒนาในตอนต้นของการเปิดตัวของ Chrome

ปฏิบัติตามข้อกำหนด

จากการอภิปรายปัญหาข้อผิดพลาดเราสามารถเข้าใจการพิจารณาบางอย่างของสมาชิกทีมพัฒนาในการใช้การเรียงลำดับการใช้งานเครื่องมืออย่างรวดเร็ว

หนึ่งในนั้นคือพวกเขาเชื่อว่าเครื่องยนต์จะต้องปฏิบัติตามข้อกำหนด ECMASCRIPT เนื่องจากข้อกำหนดไม่จำเป็นต้องมีคำอธิบายของการเรียงลำดับที่มั่นคงพวกเขาเชื่อว่าการใช้งาน V8 นั้นสอดคล้องกับข้อกำหนดอย่างเต็มที่

ข้อควรพิจารณาด้านประสิทธิภาพ

นอกจากนี้พวกเขาเชื่อว่าการพิจารณาที่สำคัญในการออกแบบ V8 คือประสิทธิภาพของเครื่องยนต์

การเรียงลำดับอย่างรวดเร็วมีประสิทธิภาพโดยรวมที่ดีกว่าการเรียงลำดับการเรียงลำดับ:

ประสิทธิภาพการคำนวณที่สูงขึ้น การเรียงลำดับอย่างรวดเร็วนั้นเร็วกว่าในสภาพแวดล้อมการดำเนินการคอมพิวเตอร์จริงกว่าอัลกอริทึมการเรียงลำดับอื่น ๆ ที่มีความซับซ้อนในเวลาเดียวกัน (ในกรณีที่ไม่ได้เข้าร่วมการรวมกันที่เลวร้ายที่สุด)

ต้นทุนพื้นที่ต่ำลง อดีตมีความซับซ้อนของอวกาศ O (n) เพียงเมื่อเทียบกับความซับซ้อนของอวกาศ O (N) หลังการใช้หน่วยความจำน้อยกว่าในช่วงเวลารันไทม์

การเพิ่มประสิทธิภาพประสิทธิภาพของ V8 ในอัลกอริทึมการเรียงลำดับอาร์เรย์

เนื่องจาก V8 มีความสนใจในประสิทธิภาพของเครื่องยนต์มากมันจะทำอย่างไรในการเรียงลำดับอาเรย์?

โดยการอ่านซอร์สโค้ดฉันยังคงเรียนรู้ความรู้พื้นฐาน

การเรียงลำดับผสม

การเรียงลำดับอย่างรวดเร็วคือความคิดในการแบ่งและพิชิตการย่อยสลายอาร์เรย์ขนาดใหญ่และเรียกคืนพวกเขาลงด้วยเลเยอร์ อย่างไรก็ตามหากความลึกของการเรียกซ้ำมีขนาดใหญ่เกินไปการใช้ทรัพยากรหน่วยความจำของสแต็กการโทรแบบเรียกซ้ำจะมีขนาดใหญ่มากเช่นกัน การเพิ่มประสิทธิภาพที่ไม่ดีอาจทำให้สแต็คล้น

การใช้งานปัจจุบันของ V8 คือการตั้งค่าเกณฑ์และใช้การเรียงลำดับแทรกสำหรับอาร์เรย์ขนาดเล็กที่มีความยาว 10 หรือน้อยกว่าในชั้นต่ำสุด

ตามความคิดเห็นของรหัสและคำอธิบายใน Wikipedia แม้ว่าความซับซ้อนของเวลาเฉลี่ยของการเรียงลำดับการแทรกคือ O (n²) นั้นแย่กว่าการเรียงลำดับอย่างรวดเร็ว O (NN) อย่างไรก็ตามในสภาพแวดล้อมการทำงานประสิทธิภาพของการใช้การเรียงลำดับการเรียงลำดับของอาร์เรย์ขนาดเล็กนั้นมีประสิทธิภาพมากกว่าการเรียงลำดับที่รวดเร็วดังนั้นจึงไม่ได้ขยายที่นี่

ตัวอย่างรหัส V8

 var Quicksort = ฟังก์ชั่น Quicksort (a, จาก, ถึง) {...... ในขณะที่ (จริง) {// การเรียงลำดับการแทรกเร็วกว่าสำหรับอาร์เรย์สั้น ๆ ถ้า (ถึง - จาก <= 10) {insertionSort (a, จาก, ถึง); กลับ; -

ตัวเลขสามตัวอยู่ใน

ตามที่ทราบกันดีว่าส้น Achilles การเรียงลำดับอย่างรวดเร็วคืออัลกอริทึมเสื่อมสภาพในการรวมกันที่เลวร้ายที่สุด

แกนกลางของอัลกอริทึมการเรียงลำดับอย่างรวดเร็วคือการเลือกเดือยและสลายตัวอาร์เรย์ที่ได้รับการเปรียบเทียบและแลกเปลี่ยนเป็นสองพื้นที่ตามการอ้างอิงสำหรับการเรียกซ้ำครั้งต่อไป ลองนึกภาพว่าสำหรับอาร์เรย์ที่สั่งซื้อแล้วองค์ประกอบแรกหรือสุดท้ายจะถูกเลือกเสมอทุกครั้งที่เลือกองค์ประกอบอ้างอิงจะมีพื้นที่ตัวเลขที่ว่างเปล่าทุกครั้งและจำนวนเลเยอร์ที่เรียกซ้ำจะถึง N ซึ่งในที่สุดจะนำไปสู่ความซับซ้อนของอัลกอริทึม ดังนั้นทางเลือกของเดือยจึงสำคัญมาก

V8 ใช้การเพิ่มประสิทธิภาพของ median-of-three : นอกเหนือจากองค์ประกอบทั้งสองในตอนต้นและจุดสิ้นสุดแล้วองค์ประกอบอื่นจะถูกเลือกให้เข้าร่วมในการแข่งขันขององค์ประกอบมาตรฐาน

กลยุทธ์การเลือกสำหรับองค์ประกอบที่สามคือประมาณ:

เมื่อความยาวของอาร์เรย์น้อยกว่าหรือเท่ากับ 1,000 ให้เลือกองค์ประกอบที่ตำแหน่งครึ่งเป็นองค์ประกอบเป้าหมาย

เมื่อความยาวของอาร์เรย์เกิน 1,000 ให้เลือกองค์ประกอบหนึ่งที่ระยะทาง 200-215 (ไม่ได้คงที่การเปลี่ยนแปลงด้วยความยาวของอาร์เรย์) เพื่อกำหนดชุดขององค์ประกอบผู้สมัครก่อน จากนั้นจัดเรียงองค์ประกอบของผู้สมัครในชุดนี้และใช้ค่ามัธยฐานผลลัพธ์เป็นองค์ประกอบเป้าหมาย

ในที่สุดใช้ค่ามัธยฐานขององค์ประกอบทั้งสามเป็นเดือย

ตัวอย่างรหัส V8

 var getThirdIndex = function (a, จาก, ถึง) {var t_array = new internalArray (); // ใช้ทั้ง 'จาก' และ 'ถึง' เพื่อกำหนดผู้สมัครที่หมุนได้ var เพิ่ม = 200 + ((ถึง - จาก) & 15); var j = 0; จาก += 1; ถึง -= 1; สำหรับ (var i = จาก; i <to; i += เพิ่ม) {t_array [j] = [i, a [i]]; J ++; } t_array.sort (ฟังก์ชั่น (a, b) {return comparefn (a [1], b [1]);}); var tholes_index = t_array [t_array.length >> 1] [0]; return third_index;}; var quicksort = function Quicksort (a, จาก, ถึง) {...... ในขณะที่ (จริง) {...... ถ้า (ถึง - จาก> 1,000) {thold_index = getthirdindex (a, จาก, ถึง); } else {thold_index = จาก + ((ถึง - จาก) >> 1); -

จัดเรียง

ในขณะที่ตรวจสอบอัลกอริทึมการเรียงลำดับที่รวดเร็วฉันเห็นตัวอย่างมากมายของการใช้งานโดยใช้ JavaScript บนอินเทอร์เน็ต

แต่ฉันพบว่าส่วนใหญ่ของการใช้รหัสมีดังนี้

 var QuickSort = function (arr) {if (arr.length <= 1) {return arr; } var pivotindex = math.floor (arr.length / 2); var pivot = arr.splice (pivotindex, 1) [0]; var left = []; var right = []; สำหรับ (var i = 0; i <arr.length; i ++) {ถ้า (arr [i] <pivot) {left.push (arr [i]); } else {right.push (arr [i]); }} ส่งคืน Quicksort (ซ้าย) .concat ([pivot], Quicksort (ขวา));};

ปัญหาหลักของรหัสข้างต้นคือ: การใช้สองพื้นที่ ด้านซ้าย และ ขวา เพื่อจัดเก็บ subarrays แบบเรียกซ้ำดังนั้นจึงต้องใช้พื้นที่เก็บข้อมูลเพิ่มเติมของ O (n) นี่คือความแตกต่างใหญ่เมื่อเทียบกับความซับซ้อนเชิงพื้นที่โดยเฉลี่ยในเชิงทฤษฎี o (n)

ค่าใช้จ่ายพื้นที่เพิ่มเติมจะส่งผลกระทบต่อความเร็วโดยรวมของรันไทม์จริง นี่เป็นหนึ่งในเหตุผลที่การเรียงลำดับอย่างรวดเร็วสามารถทำงานได้ในช่วงเวลาที่เกิดขึ้นจริงเกินกว่าความซับซ้อนของเวลาในระดับเดียวกัน ดังนั้นการพูดอย่างรวดเร็วโดยทั่วไปด้วยประสิทธิภาพที่ดีขึ้นจะนำการเรียงลำดับมาใช้ในสถานที่

การใช้งานในซอร์สโค้ด V8 คือการแลกเปลี่ยนองค์ประกอบในอาร์เรย์ดั้งเดิม

เหตุใด Firefox จึงใช้การเรียงลำดับการผสาน

นอกจากนี้ยังมีเรื่องราวเบื้องหลัง

ในความเป็นจริงเมื่อ Firefox ได้รับการปล่อยตัวในตอนแรกมันไม่ได้ใช้อัลกอริทึมการเรียงลำดับที่มั่นคงเพื่อใช้การเรียงลำดับอาเรย์ซึ่งเป็นเอกสารที่ดี

อัลกอริทึมการเรียงลำดับอาร์เรย์ที่ดำเนินการโดย Firefox เวอร์ชันดั้งเดิม (Firebird) คือการเรียงลำดับของกองซึ่งเป็นอัลกอริทึมการเรียงลำดับที่ไม่เสถียร ดังนั้นมีคนส่งข้อผิดพลาดในภายหลัง

ทีมพัฒนา Mozilla ได้ดำเนินการอภิปรายเกี่ยวกับปัญหานี้

จากกระบวนการสนทนาเราสามารถวาดบางประเด็น

1. คู่แข่งของ Mozilla ในช่วงเวลาเดียวกันคือ IE6 จากสถิติด้านบนเราจะเห็นว่า IE6 มีความเสถียรในการเรียงลำดับ

2. Brendan Eich พ่อของ JavaScript คิดว่าความมั่นคงเป็นสิ่งที่ดี

3. Firefox ใช้การเรียงลำดับอย่างรวดเร็วก่อนการเรียงลำดับ

จากหลักฐานหลักที่ว่าสมาชิกกลุ่มการพัฒนามีแนวโน้มที่จะใช้อัลกอริทึมการเรียงลำดับที่มั่นคง Firefox3 ใช้การเรียงลำดับการเรียงลำดับเป็นการใช้งานใหม่ของการเรียงลำดับอาเรย์

แก้ปัญหาความแตกต่างในการเรียงลำดับความมั่นคง

ฉันได้กล่าวไว้ข้างต้นเป็นหลักเพื่อบอกความแตกต่างในการจัดเรียงการเรียงลำดับของเบราว์เซอร์แต่ละตัวและเพื่ออธิบายเหตุผลบางอย่างที่ผิวเผินมากขึ้นว่าทำไมความแตกต่างเหล่านี้จึงมีอยู่

แต่หลังจากอ่านสิ่งนี้ผู้อ่านอาจยังมีคำถาม: ฉันควรทำอย่างไรถ้าโครงการของฉันต้องการพึ่งพาการเรียงลำดับที่มั่นคง?

สารละลาย

ในความเป็นจริงความคิดในการแก้ปัญหานี้ค่อนข้างง่าย

เบราว์เซอร์เลือกอัลกอริทึมการเรียงลำดับที่แตกต่างกันสำหรับการพิจารณาที่แตกต่างกัน บางคนอาจมีแนวโน้มที่จะมีประสิทธิภาพอย่างมากในขณะที่คนอื่นมักจะให้ประสบการณ์การพัฒนาที่ดี แต่มีกฎที่ต้องปฏิบัติตาม

เมื่อพิจารณาจากสถานการณ์ที่รู้จักในปัจจุบันเบราว์เซอร์กระแสหลักทั้งหมด (รวมถึง IE6, 7, 8) สามารถระบุการใช้อัลกอริทึมการเรียงลำดับอาเรย์:

1. การเรียงลำดับ/timsort

2. จัดเรียงอย่างรวดเร็ว

ดังนั้นเราสามารถเปลี่ยนการเรียงลำดับอย่างรวดเร็วให้เป็นการเรียงลำดับที่มั่นคงได้หรือไม่?

โดยทั่วไปแล้วการใช้การเรียงลำดับที่ไม่เสถียรสำหรับอาร์เรย์วัตถุจะส่งผลต่อผลลัพธ์ ในขณะที่อาร์เรย์ประเภทอื่น ๆ ใช้ผลลัพธ์การเรียงลำดับที่เสถียรหรือไม่เสถียรเท่ากัน ดังนั้นแผนจึงมีดังนี้:

ประมวลผลล่วงหน้าอาร์เรย์ที่จะจัดเรียงและเพิ่มแอตทริบิวต์การสั่งซื้อตามธรรมชาติให้กับแต่ละวัตถุที่จะจัดเรียงเพื่อไม่ให้ขัดแย้งกับคุณลักษณะอื่น ๆ ของวัตถุ

วิธีการเปรียบเทียบการเรียงลำดับแบบกำหนดเองเปรียบเทียบกับการสั่งซื้อตามธรรมชาติเป็นมิติการตัดสินครั้งที่สองเมื่อการตัดสินล่วงหน้าเท่ากัน

เมื่อเผชิญกับการใช้งานเช่นการเรียงลำดับการรวมเนื่องจากอัลกอริทึมนั้นมีความเสถียรการเปรียบเทียบลำดับตามธรรมชาติเพิ่มเติมจะไม่เปลี่ยนผลลัพธ์การเรียงลำดับดังนั้นความเข้ากันได้ของโครงการจึงดีกว่า

อย่างไรก็ตามมันเกี่ยวข้องกับการปรับเปลี่ยนอาร์เรย์ที่จะจัดเรียงและจำเป็นต้องมีพื้นที่เพิ่มเติมเพื่อจัดเก็บคุณสมบัติการสั่งซื้อตามธรรมชาติ เป็นไปได้ว่าเครื่องยนต์เช่น V8 ไม่ควรใช้วิธีการที่คล้ายกัน อย่างไรก็ตามมันเป็นไปได้เป็นแผนการเรียงลำดับที่กำหนดโดยนักพัฒนา

ตัวอย่างรหัสโครงการ

 'ใช้อย่างเข้มงวด'; const index = symbol ('index'); ฟังก์ชั่น getComparer (เปรียบเทียบ) {ฟังก์ชันส่งคืน (ซ้าย, ขวา) {ให้ผลลัพธ์ = เปรียบเทียบ (ซ้าย, ขวา); ส่งคืนผลลัพธ์ === 0? ซ้าย [ดัชนี] - ขวา [ดัชนี]: ผลลัพธ์; };} การเรียงลำดับฟังก์ชัน (อาร์เรย์, เปรียบเทียบ) {array = array.map ((รายการ, ดัชนี) => {ถ้า (typeof item === 'Object') {item [index] = index;} return item;}); return array.sort (getComparer (เปรียบเทียบ));}

ข้างต้นเป็นเพียงตัวอย่างการปรับเปลี่ยนอัลกอริทึมอย่างง่ายที่ตอบสนองการเรียงลำดับที่มั่นคง

เหตุผลที่มันง่ายคือโครงสร้างข้อมูลเป็นอินพุตอาร์เรย์ในสภาพแวดล้อมการผลิตจริงมีความซับซ้อนและจำเป็นต้องตัดสินว่าจำเป็นต้องมีการสั่งซื้อล่วงหน้าเพิ่มเติมตามสถานการณ์จริงหรือไม่

ติดแท็ก

1. ส่วนหน้าตอนนี้เป็นแนวคิดที่ค่อนข้างกว้าง ส่วนหน้าในบทความนี้ส่วนใหญ่หมายถึงสภาพแวดล้อมโดยใช้เบราว์เซอร์เป็นผู้ให้บริการและ JavaScript เป็นภาษาการเขียนโปรแกรม

2. บทความนี้ไม่ได้ตั้งใจจะเกี่ยวข้องกับอัลกอริทึมโดยรวม ฉันต้องการใช้อัลกอริทึมการเรียงลำดับทั่วไปเป็นจุดเริ่มต้น

3. เมื่อยืนยันอัลกอริทึมที่ดำเนินการโดย Firefox Array Sorting พบข้อผิดพลาดที่เกี่ยวข้องกับการเรียงลำดับใน Spidermoney โดยทั่วไปในระหว่างการสนทนามีคนแนะนำให้ใช้อัลกอริทึม Timsort ที่มีประสิทธิภาพที่ดีขึ้นในกรณีที่รุนแรงเพื่อแทนที่การเรียงลำดับการผสาน แต่วิศวกร Mozilla กล่าวว่าเนื่องจากปัญหาการอนุญาตใบอนุญาตของอัลกอริทึม Timsort ไม่มีวิธีการใช้อัลกอริทึมโดยตรงในซอฟต์แวร์ของ Mozilla

สรุป

ข้างต้นเป็นบทสรุปและวิธีแก้ปัญหาที่พบในการเรียงลำดับส่วนหน้า ในช่วงไม่กี่ปีที่ผ่านมามีโครงการที่มีการเปลี่ยนแปลงไปสู่แอปพลิเคชันลูกค้าที่หลากหลายและสัดส่วนของส่วนหน้าในโครงการเพิ่มขึ้น ด้วยการปรับปรุงพลังการคำนวณเบราว์เซอร์ต่อไปในอนาคตทำให้การคำนวณที่ซับซ้อนมากขึ้น ด้วยการเปลี่ยนแปลงความรับผิดชอบแบบฟอร์มส่วนหน้าอาจได้รับการเปลี่ยนแปลงที่สำคัญบางอย่าง เมื่อเดินในโลกคุณต้องมีทักษะเสมอ