ชุมชนโปรแกรมเมอร์กำลังทบทวนเทคนิคการเพิ่มประสิทธิภาพการเรียงลำดับที่มีมาหลายทศวรรษ หลังจากมีการวิเคราะห์ใหม่เกี่ยวกับวิธีที่ภาษาโปรแกรมสมัยใหม่จัดการกับการแปลงข้อมูลที่มีต้นทุนสูง การอภิปรายนี้มีจุดศูนย์กลางอยู่ที่ Schwartzian Transform ซึ่งเป็นอัลกอริทึมการเรียงลำดับที่ชาญฉลาดที่เกิดขึ้นจากการเขียนโปรแกรม Perl ในช่วงทศวรรษ 1990 และความเกี่ยวข้องกับภูมิทัศน์การพัฒนาซอฟต์แวร์ในปัจจุบัน
ขั้นตอนของอัลกอริทึม Schwartzian Transform :
- ตกแต่ง (Decorate): รวมค่าเดิมกับคีย์การเรียงลำดับที่คำนวณแล้วในรูปแบบ tuples
- เรียงลำดับ (Sort): เรียงลำดับตามคีย์ที่คำนวณแล้วใน tuples
- ถอดตกแต่ง (Undecorate): ดึงค่าเดิมออกมาจาก tuples ที่เรียงลำดับแล้ว
รูปแบบนี้ช่วยลดการคำนวณคีย์ที่มีค่าใช้จ่ายสูงจาก O(n log n) เหลือเพียง O(n) ในด้านความซับซ้อน
ประสิทธิภาพของภาษาโปรแกรมแตกต่างกันอย่างมาก
การทดสอบล่าสุดในภาษาโปรแกรมมิ่งยอดนิยมเผยให้เห็นความไม่สอดคล้องที่น่าประหลาดใจในประสิทธิภาพการเรียงลำดับ ในขณะที่ C# เพิ่มประสิทธิภาพการเรียงลำดับโดยอัตโนมัติด้วยการประเมินฟังก์ชันการแปลงเพียงครั้งเดียวต่อรายการ ภาษาหลักอื่นๆ เช่น Java, Rust ของ sort_by_key() แบบเริ่มต้น และ C++20 จะเรียกใช้ฟังก์ชันการแปลงที่มีต้นทุนสูงซ้ำๆ ระหว่างการดำเนินการเรียงลำดับ นี่หมายความว่าในภาษาที่ไม่มีการเพิ่มประสิทธิภาพในตัว การเรียงลำดับรายการ 1,000 รายการอาจทำให้ฟังก์ชันการแปลงทำงานหลายพันครั้งแทนที่จะเป็น 1,000 ครั้งที่เหมาะสมที่สุด
ช่องว่างด้านประสิทธิภาพกลายเป็นสิ่งสำคัญเมื่อต้องจัดการกับการดำเนินการที่มีต้นทุนสูง เช่น การเรียกใช้ระบบไฟล์ การสืบค้นฐานข้อมูล หรือการคำนวณที่ซับซ้อน นักพัฒนาที่ทำงานกับภาษาเหล่านี้ต้องใช้รูปแบบ Schwartzian Transform ด้วยตนเองเพื่อให้ได้ประสิทธิภาพที่เหมาะสมที่สุด
การเปรียบเทียบประสิทธิภาพการเรียงลำดับของภาษาโปรแกรม:
- C: ประเมินฟังก์ชันการแปลงเพียงครั้งเดียวต่อรายการ (ได้รับการปรับปรุงประสิทธิภาพ)
- Java: ใช้ Comparators เรียกใช้การแปลงซ้ำๆ (ไม่ได้รับการปรับปรุงประสิทธิภาพ)
- Rust sort_by_key(): เรียกใช้การแปลงหลายครั้ง (ไม่ได้รับการปรับปรุงประสิทธิภาพ)
- Rust sort_by_cached_key(): ใช้การแคชขั้นสูงด้วยเวลาเชิงเส้นบนข้อมูลที่เรียงลำดับแล้ว (ได้รับการปรับปรุงประสิทธิภาพสูง)
- C++20 std::range: เรียกใช้ lambda ซ้ำๆ (ไม่ได้รับการปรับปรุงประสิทธิภาพ)
การถกเถียงระหว่างความเข้าถึงได้กับพลังงานกลับมาอีกครั้ง
การอภิปรายในชุมชนเผยให้เห็นความตึงเครียดที่ดำเนินต่อเนื่องระหว่างความสามารถในการอ่านโค้ดกับการเพิ่มประสิทธิภาพ ความขัดแย้งดั้งเดิมในช่วงทศวรรษ 1990 เกี่ยวกับ Schwartzian Transform มีจุดศูนย์กลางอยู่ที่ว่าภาษาโปรแกรมมิ่งควรให้ความสำคัญกับความเข้าใจในทันทีหรือฟังก์ชันการทำงานที่ทรงพลัง การถกเถียงนี้ยังคงดำเนินต่อไปในปัจจุบัน โดยนักพัฒนาบางคนสนับสนุนโซลูชันที่ชัดเจนและละเอียด ในขณะที่คนอื่นๆ ยอมรับรูปแบบการเขียนโปรแกรมเชิงฟังก์ชันที่กระชับ
ฉันพบว่าน่าสนใจที่การแปลงนี้เป็นที่ถกเถียงกันในช่วงทศวรรษ 90 วันนี้ดูเหมือนว่าเป็นโซลูชันปกติสำหรับปัญหานี้สำหรับฉัน และการถกเถียงดูเหมือนไร้สาระ
นักพัฒนาสมัยใหม่ที่มีประสบการณ์ใน JavaScript และแนวคิดการเขียนโปรแกรมเชิงฟังก์ชันโดยทั่วไปจะพบว่ารูปแบบนี้เข้าใจง่าย ในขณะที่ผู้ที่มาจากพื้นฐานการเขียนโปรแกรมแบบ imperative อาจยังคงชอบวิธีการแบบลูปแบบดั้งเดิม
 |
|---|
| ประวัติของ Schwartzian Transform : การศึกษาพื้นหลังของอัลกอริทึมและการถกเถียงด้านการเขียนโปรแกรมที่เกี่ยวข้อง |
Rust นำหน้าด้วยแนวทางคู่
ในบรรดาภาษาที่ทำการทดสอบ Rust แสดงให้เห็นแนวทางที่มีความคิดมากที่สุดโดยการจัดเตรียมทั้งเมธอด sort_by_key() และ sort_by_cached_key() เวอร์ชันแคชใช้อัลกอริทึมที่ซับซ้อนซึ่งไปไกลกว่า Schwartzian Transform พื้นฐาน โดยบรรลุประสิทธิภาพเวลาเชิงเส้นบนอินพุตที่เรียงลำดับแล้วในขณะที่ยังคงการใช้หน่วยความจำที่มีประสิทธิภาพ แนวทางคู่นี้ยอมรับว่าการดำเนินการเรียงลำดับส่วนใหญ่เกี่ยวข้องกับการแปลงที่ง่ายและราคาถูกที่ไม่ต้องการการแคช ในขณะที่ยังคงจัดเตรียมโซลูชันที่เพิ่มประสิทธิภาพสำหรับการดำเนินการที่มีต้นทุนสูง
ความสนใจที่เพิ่มขึ้นของชุมชนโปรแกรมเมอร์ในเทคนิคการเพิ่มประสิทธิภาพคลาสสิกนี้เน้นย้ำว่าแนวคิดอัลกอริทึมพื้นฐานยังคงมีความเกี่ยวข้องในทุกรุ่นของภาษา เมื่อแอปพลิเคชันจัดการกับการแปลงข้อมูลที่ซับซ้อนมากขึ้น การทำความเข้าใจและการใช้กลยุทธ์การเรียงลำดับที่มีประสิทธิภาพกลายเป็นสิ่งสำคัญสำหรับการพัฒนาที่ใส่ใจประสิทธิภาพ ไม่ว่าจะเลือกใช้ภาษาโปรแกรมมิ่งใดก็ตาม