on
ภาษา 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
เพิ่งรู้ว่ายังมีเร็วกว่า
itpcc Thu, 21/04/2022 - 17:10
เพิ่งรู้ว่ายังมีเร็วกว่า Quick sort อีกนะเนี่ย
Very Quick Sort
heart Fri, 22/04/2022 - 10:12
In reply to เพิ่งรู้ว่ายังมีเร็วกว่า by itpcc
Very Quick Sort
ในแง่ของ Big-O
lew Fri, 22/04/2022 - 10:39
In reply to เพิ่งรู้ว่ายังมีเร็วกว่า by itpcc
ในแง่ของ Big-O น่าจะไม่ได้เร็วกว่าครับ แต่เขาออกแบบโดยคำนึงถึงการทำงานของซีพียูในโลกความเป็นจริง เกิด branch mis-prediction (เดาว่า if-else ไปทางไหน) ในซีพียูจริงมันค่อนข้างแพง เพราะซีพียูจริงแอบรันโค้ดใน if ก่อนที่จะเช็คเงื่อนไขด้วยซ้ำ ถ้า if เป็นเท็จก็ค่อยยกเลิกผลทิ้ง
ผมยังไม่ได้อ่านละเอียด แต่คนพัฒนาระบุว่า pdqsort นี่คำนึงถึงเรื่องนี้ ทำให้มันเร็วขึ้นหลายเท่าตัว โดยเฉพาะถ้ากระบวนการเปรียบเทียบ object ที่จะ sort ไม่ต้องใช้ if-else ด้วย
ที่จริงยังมีวิธีที่น่าจะเร็วว
rattananen Fri, 22/04/2022 - 10:46
In reply to เพิ่งรู้ว่ายังมีเร็วกว่า by itpcc
ที่จริงยังมีวิธีที่น่าจะเร็วว่า sort น่ะครับ
priority queue
ผมชอบไปแกะ code คนอื่น
เห็นบางคนไม่ใช้ sort แต่ ใช้ priority queue แทน ก็น่าสนใจดี
priority queue
mr_tawan Fri, 22/04/2022 - 20:38
In reply to ที่จริงยังมีวิธีที่น่าจะเร็วว by rattananen
priority queue นี่เหมือนมันเก็บข้อมูลเรียงกันแต่ต้นเลยนี่ครับ คงไม่ต้องเรียงใหม่
ที่ผมเจอก็คือ เขา pop จาก
rattananen Fri, 22/04/2022 - 22:17
In reply to priority queue by mr_tawan
ที่ผมเจอก็คือ เขา pop จาก unsort stack หรือ read จาก stream, resource
ไป push ลง priority queue
แล้ว iterate จาก priority queue เลย
ดูแล้วมันก็ใช้ได้ดี น่าจะเร็วกว่าเอา stack ไป sort
ตามชื่อเลยครับ มันคือ pattern
iqsk131 Fri, 22/04/2022 - 11:17
In reply to เพิ่งรู้ว่ายังมีเร็วกว่า by itpcc
ตามชื่อเลยครับ มันคือ pattern-defeating quicksort ก็คือจะเร็วกว่าแค่ในบาง pattern ซึ่งส่วนตัวผมคิดว่ามันน่าจะมี sort ทำนองนี้อยู่อีกไม่มากก็น้อยแต่คนละ pattern กันนั่นแหละครับ