ภาษา Go เตรียมเปลี่ยนฟังก์ชั่น sort จากเดิมใช้ QuickSort มาเป็น pdqsort หรือ pattern-defeating quicksort อัลกอริทึมเรียงลำดับที่ประสิทธิภาพโดยรวมดีขึ้นมากในหลายกรณี แม้ว่ากรณีที่แย่ที่สุดยังเป็น O(n log n)
เช่นเดิมก็ตาม
pdqsort พัฒนาโดย Orson R. L. Peters จากมหาวิทยาลัย Leiden ในเนธอร์แลนด์ เมื่อปี 2017 มีจุดได้เปรียบสำคัญคือยิ่งค่าที่เป็นไปได้ของข้อมูลมีน้อยแม้จำนวนข้อมูลจะมีจำนวนมาก เช่น เรียงเลขนับล้านตัว แต่มีเลขที่เป็นไปได้เพียง 0 ถึง 9 ในกรณีเช่นนี้ pdqsort จะมีประสิทธิภาพสูงมาก และหากโค้ดสำหรับเปรียบเทียบค่าไม่ต้องมี branch ประสิทธิภาพในการรันอัลกอริทึมก็จะสูงขึ้นมาก
ภาษา Rust นั้นใช้ pdqsort มาตั้งแต่ปี 2017
หลังอัลกอริทึมนี้ถูกเสนอมาไม่นาน เป็นฟังก์ชั่น sort_unstable
ส่วนภาษา Go นั้นมีการ เสนอให้เปลี่ยนมาตั้งแต่ปลายปีที่แล้ว
และ กำลังอยู่ระหว่างรีวิว
หากไม่มีปัญหาอะไรก็น่าจะได้ใช้ในเวอร์ชั่นต่อไป
ที่มา - golang/go
Comments
เพิ่งรู้ว่ายังมีเร็วกว่า Quick sort อีกนะเนี่ย
บล็อกส่วนตัวที่อัพเดตตามอารมณ์และความขยัน :P
Very Quick Sort
ในแง่ของ Big-O น่าจะไม่ได้เร็วกว่าครับ แต่เขาออกแบบโดยคำนึงถึงการทำงานของซีพียูในโลกความเป็นจริง เกิด branch mis-prediction (เดาว่า if-else ไปทางไหน) ในซีพียูจริงมันค่อนข้างแพง เพราะซีพียูจริงแอบรันโค้ดใน if ก่อนที่จะเช็คเงื่อนไขด้วยซ้ำ ถ้า if เป็นเท็จก็ค่อยยกเลิกผลทิ้ง
ผมยังไม่ได้อ่านละเอียด แต่คนพัฒนาระบุว่า pdqsort นี่คำนึงถึงเรื่องนี้ ทำให้มันเร็วขึ้นหลายเท่าตัว โดยเฉพาะถ้ากระบวนการเปรียบเทียบ object ที่จะ sort ไม่ต้องใช้ if-else ด้วย
lewcpe.com , @wasonliw
ที่จริงยังมีวิธีที่น่าจะเร็วว่า sort น่ะครับ
priority queueผมชอบไปแกะ code คนอื่น
เห็นบางคนไม่ใช้ sort แต่ ใช้ priority queue แทน ก็น่าสนใจดี
priority queue นี่เหมือนมันเก็บข้อมูลเรียงกันแต่ต้นเลยนี่ครับ คงไม่ต้องเรียงใหม่
ที่ผมเจอก็คือ เขา pop จาก unsort stack หรือ read จาก stream, resource
ไป push ลง priority queueแล้ว iterate จาก priority queue เลย
ดูแล้วมันก็ใช้ได้ดี น่าจะเร็วกว่าเอา stack ไป sort
ตามชื่อเลยครับ มันคือ pattern-defeating quicksort ก็คือจะเร็วกว่าแค่ในบาง pattern ซึ่งส่วนตัวผมคิดว่ามันน่าจะมี sort ทำนองนี้อยู่อีกไม่มากก็น้อยแต่คนละ pattern กันนั่นแหละครับ