พาวเวอร์ซอร์ต

ระดับ	อัลกอริทึมการเรียงลำดับ
โครงสร้างข้อมูล	อาร์เรย์
ประสิทธิภาพในกรณีที่เลวร้ายที่สุด	${\displaystyle O(n\log n)}$
ความซับซ้อนของพื้นที่ในกรณีที่เลวร้ายที่สุด	${\displaystyle O(n)}$
เหมาะสมที่สุด	ไม่; "เกือบเหมาะสมที่สุด" แต่สามารถเอาชนะได้ด้วยการควบม้าแบบขั้นสูงกว่า[ 1 ]

Powersortเป็นอัลกอริทึมการเรียงลำดับแบบปรับตัวได้ ซึ่งออกแบบมาเพื่อใช้ประโยชน์จากลำดับที่มีอยู่แล้วในข้อมูลอินพุตอย่างเหมาะสมที่สุด โดยมีค่าใช้จ่ายน้อยที่สุด ตั้งแต่เวอร์ชัน 3.11 Powersort เป็นอัลกอริทึมการเรียงลำดับรายการเริ่มต้นในCPython ^{[ 2 ] [ 3 ]} และยังใช้ในNumPy ^{[ 4 ]} , PyPy , AssemblyScript ^{[ 5 ]}และWebKit ของ Apple ^{[ 6 ]} Powersort จัดอยู่ในกลุ่มของ อัลกอริทึมการเรียงลำดับ แบบผสาน (merge sort ) โดยเฉพาะอย่างยิ่ง Powersort สร้างขึ้นบนTimsort ; มันเป็นตัวทดแทนโดยตรงสำหรับนโยบายการผสานแบบฮิวริสติกที่ไม่เหมาะสมของ Timsort แตกต่างจาก Timsort ตรงที่ Powersort ได้มาจากหลักการพื้นฐาน (ดูความเชื่อมโยงกับต้นไม้ค้นหาแบบไบนารีที่เกือบจะเหมาะสมที่สุด ) และให้การรับประกันประสิทธิภาพที่แข็งแกร่ง

เช่นเดียวกับ Timsort, Powersort มีเสถียรภาพและใช้การเปรียบเทียบคุณสมบัตินี้มีความสำคัญต่อการใช้งานหลายอย่าง^{[ 7 ]} Powersort ได้รับการเสนอโดย J. Ian Munro และ Sebastian Wild ^{[ 8 ]}

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

โหมดการทำงานที่ไม่ใช้การเรียกซ้ำนี้เป็นมิตร กับแคช เป็นพิเศษ

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

Powersort ปรับปรุง Timsort ในแง่ของนโยบายการรวม กล่าวคือ กฎที่ตัดสินใจว่ารันใดบนสแต็กรันจะถูกรวมเข้าด้วยกันก่อนที่จะดำเนินการต่อไป นโยบายดั้งเดิมของ Timsort ใช้ฮิวริสติกที่ไม่เหมาะสมโดยอาศัยความยาวของรันเพียงอย่างเดียว Powersort แทนที่สิ่งนี้ด้วยกฎที่จำลองอัลกอริทึมของ Mehlhorn สำหรับการคำนวณต้นไม้ค้นหาไบนารีที่เกือบจะเหมาะสมที่สุดโดยมีค่าใช้จ่ายต่ำ^{[ 8 ]}จึงบรรลุความสามารถในการปรับตัวที่เหมาะสมที่สุดจนถึงพจน์เชิงเส้นแบบบวก

รหัสเทียมด้านล่างแสดงการใช้งาน Powersort แบบง่ายๆ

อัลกอริทึม PowerSort (A[0..n)) S := สแต็กของลำดับการวิ่ง // ความจุ ⌈lg(n)⌉ + 1 ข1  := 0; อี1  := FirstRunOf (A[b 1 ..n)) // A[b 1 ..e 1 ) เป็นรันซ้ายสุด ในขณะที่ e 1 < n ข2  := อี1 + 1; อี2  := FirstRunOf(A[b 2 ..n)) // A[b 2 ..e 2 ) การทำงานครั้งต่อไป P := NodePower (n, b 1 , e 1 , b 2 , e 2 ) ในขณะที่ S.top().power > P (b 1 , e 1 ) := Merge (S.pop(), A[b 1 ..e 1 )) end while S.push((A[b 1 , e 1 ), P)); b 1  := b 2 ; e 1  := e 2 end while // ตอนนี้ A[b 1 ..e 1 ) คือลำดับขวาสุด while ¬S.empty() (b 1 , e 1 ) := Merge (S.pop(), A[b 1 ..e 1 )) end while

อัลกอริทึมNodePower (n, b 1 , e 1 , b 2 , e 2 ) n 1  := e 1 − b 1 ; n 2  := e 2 − b 2 ; a := (b 1 + n 1 /2)/n; b := (b 2 + n 2 /2)/n p := 0 ในขณะที่ ⌊a · 2 p ⌋ == ⌊b · 2 p ⌋ p := p + 1 สิ้นสุดในขณะที่ส่งคืน p 

การใช้งานMergeนั้นสืบทอดมาจาก TimSort และรวมถึงฮิวริสติกแบบ "galloping" ด้วย

การนำ Powersort มาใช้ในCPythonเริ่มต้นด้วยเวอร์ชัน 3.11 โดยแทนที่อัลกอริทึม Timsort เดิม การเปลี่ยนแปลงนี้เกิดจากประสิทธิภาพและความเสถียรที่เหนือกว่าของ Powersort การใช้งานหลักสามารถพบได้ในซอร์สโค้ดของ CPython ภายใน ไฟล์ listobject.cซึ่งเป็นที่ที่กำหนดฟังก์ชันการเรียงลำดับรายการ นโยบายการรวมและอัลกอริทึมโดยละเอียดมีอธิบายไว้ในlistsort.txt ... ^{[ 10 ] [ 11 ]}การเปลี่ยนไปใช้ Powersort เกี่ยวข้องกับการแก้ไขปัญหา #78742 ในที่เก็บ CPython ^{[ 12 ]}

โครงการPyPyซึ่งเป็นที่รู้จักในฐานะคอมไพเลอร์ Just-In-Time (JIT) ประสิทธิภาพสูงสำหรับ Python ยังได้รวม Powersort เข้าไปด้วย การเปลี่ยนแปลงที่เกี่ยวข้องซึ่งระบุว่าเป็น จะ6d2f7a78baa8d4d2f94f5fb709f697a560b45f4eให้รายละเอียดเกี่ยวกับการรวม Powersort เข้าไปในฟังก์ชันการเรียงลำดับรายการของ PyPy ^{[ 13 ]}

ในAssemblyScriptนั้น Powersort ถูกรวมเข้าด้วยกันเพื่อเพิ่มประสิทธิภาพของแอปพลิเคชัน WebAssembly คำขอพูลที่เกี่ยวข้อง #1904 และรายละเอียดการใช้งานสามารถพบได้ใน ไฟล์ sort.tsภายในไลบรารีมาตรฐานของ AssemblyScript ^{[ 14 ] [ 15 ]}การใช้งานเหล่านี้ในแพลตฟอร์มต่างๆ เน้นให้เห็นถึงความสามารถในการปรับตัวและประสิทธิภาพของ Powersort ในสภาพแวดล้อมการเขียนโปรแกรมต่างๆ

เช่นเดียวกับ TimSort การใช้งาน Powersort อย่างเต็มรูปแบบนั้นมีหลายร้อยบรรทัดและใหญ่เกินกว่าจะใส่ไว้ในบทความวิกิพีเดียได้ ผู้อ่านควรศึกษาจากแหล่งข้อมูลต่อไปนี้:

• การใช้งาน C จากCPythonเวอร์ชัน 3.13.5 เริ่มต้นที่บรรทัด 1577 และสิ้นสุดที่บรรทัด 3151 รวมทั้งหมด 1574 บรรทัด (974 ไม่รวมความคิดเห็นและบรรทัดว่าง) ^{[ 16 ]}
• การใช้งาน Python จากPyPy 3.11 เวอร์ชัน 7.3.19 จำนวน 680 บรรทัด (434 บรรทัดไม่รวมความคิดเห็นและบรรทัดว่าง) โค้ดนี้ยังคงใช้ชื่อ "TimSort" แต่กลยุทธ์การรวมได้เปลี่ยนเป็น "powersort" ^{[ 17 ]}

นโยบายการรวมข้อมูลเดิมของ Timsort ก่อให้เกิดปัญหาหลายประการก่อนที่จะถูกแทนที่ด้วย Powersort

ประการแรก ดังที่สังเกตโดยบังเอิญในระหว่างการตรวจสอบอย่างเป็นทางการของ Timsortสูตรดั้งเดิมของ Tim Peters ไม่รับประกันขอบเขตความสูงที่ต้องการสำหรับสแต็กการทำงาน ทำให้ทั้ง CPython และ OpenJDK เสี่ยงต่อการเกิดสแต็กโอเวอร์โฟลว์ปัญหานี้ได้รับการแก้ไขในที่สุดโดยการเพิ่มกฎข้อที่สี่ให้กับ Timsort แต่ต้องใช้แพตช์หลักสองรายการของ OpenJDK ^{[ 18 ]} แม้ว่าจะประสบความสำเร็จในที่สุด แต่การพิสูจน์ความถูกต้องของความสูงของสแต็กของ Timsort และการวิเคราะห์รันไทม์นั้นซับซ้อนมาก

นอกจากนี้ ยังพบว่านโยบายการรวมของ Timsort ยังมีจุดบอดด้านประสิทธิภาพอีกด้วย กล่าวคือ รูปแบบเฉพาะของความยาวการทำงานทำให้ Timsort ดำเนินการรวมที่ไม่สมดุลซ้ำๆ ส่งผลให้มีค่าใช้จ่ายเพิ่มขึ้นถึง 50% โดยประมาณ^{[ 19 ]}

Powersort ขจัดข้อจำกัดทั้งหมดเหล่านี้พร้อมกัน แม้จะมีพื้นฐานทางทฤษฎีขั้นสูง แต่การวิเคราะห์ก็ง่ายกว่ามาก^{[ 20 ]}และพิสูจน์ได้ว่าไม่เคยใช้การเปรียบเทียบมากกว่าโดยที่สำหรับความยาวของลำดับในข้อมูลป้อนเข้า ${\displaystyle n{\mathcal {H}}+O(n)}$${\displaystyle {\mathcal {H}}=\sum _{i=1}^{r}{\frac {\ell _{i}}{n}}\log _{2}\left({\frac {n}{\ell _{i}}}\right)}$${\displaystyle \ell _{1},\ldots ,\ell _{r}}$

Powersort ได้รับการพิสูจน์แล้วว่ามีประสิทธิภาพเหนือกว่า Timsort ถึง 30% ในข้อมูลอินพุตบางประเภทที่มีองค์ประกอบที่เรียงลำดับยาว^{[ 8 ]} Powersort ยังได้รับการขยายไปสู่การรวมแบบหลายทาง ซึ่งเป็นสิ่งที่ไม่สามารถทำได้ด้วย Timsort

Multiway Powersort ^{[ 20 ]}เป็นส่วนขยายของ Powersort ที่ขยายกระบวนการผสานแบบไบนารีไปสู่ การผสาน แบบ kทาง แนวทางนี้สามารถลดจำนวนการดำเนินการผสานและด้วยเหตุนี้จึงลดปริมาณการถ่ายโอนหน่วยความจำ ได้รับการเสนอโดย William Cawley Gelling, Markus E. Nebel, Benjamin Smith และ Sebastian Wild ในปี 2023

Multiway Powersort ยังคงรักษาเสถียรภาพและความสามารถในการปรับตัวของอัลกอริทึม Powersort ดั้งเดิม^{[ 20 ]}และวิเคราะห์ได้ง่ายเช่นกัน

ความแตกต่างที่สำคัญจาก Powersort ทั่วไปมีดังนี้:

• การคำนวณเลขยกกำลังใช้ฐานkแทนที่จะเป็น 2
• เมื่อรวมการทำงานเข้าด้วยกัน เราต้องนำ การทำงาน ทั้งหมดที่มีกำลังเท่ากับการทำงานบนสุดออกจากกองข้อมูล

รายละเอียดแสดงอยู่ในรหัสเทียมด้านล่างนี้

อัลกอริทึมk-wayPowerSort (A[0..n)) S := กองว่าง // ความจุ (k − 1)⌈log k (n) + 1⌉ ข1  := 0; e 1 = FirstRunOf (A[b 1..n )) ในขณะที่ e 1 < n ข2  := อี1 ; อี2  := FirstRunOf (A[b 2..n )) P := Power k (n, b 1 , e 1 , b 2 , e 2 ) ในขณะที่ S.top().power > P P':= S.top().power L := รายการว่าง; L.append(S.pop()) ในขณะที่ S.top().power == P′ L.append(S.pop()) end while // merge runs in L with A[b 1 ..e 1 ) (b 1 , e 1 ) := Merge (L, A[b 1 ..e 1 )) end while S.push((A[b 1 , e 1 ), P)) b 1  := b 2 ; e 1  := e 2 end while // ตอนนี้ A[b 1 ..e 1 ) คือลำดับขวาสุด while ¬S.empty() // ป๊อป (สูงสุด) k − 1 รัน รวมกับ A[b 1 ..e 1 ) (b 1 , e 1 ) := Merge (S.pop(k − 1), A[b 1 ..e 1 )) end while

อัลกอริทึม Power k (n, b 1 , e 1 , b 2 , e 2 ) n 1  := e 1 − b 1 ; n 2  := e 2 − b 2 ; p := 0 a := (b 1 + n 1 /2)/n; b := (b 2 + n 2 /2)/n ในขณะที่ ⌊a · k p ⌋ == ⌊b · k p ⌋ p := p + 1 สิ้นสุดในขณะที่ส่งคืน p 

• เกมPowersort's Pursuitเป็น วิธีที่สนุกสนานในการทำความเข้าใจนโยบายการรวมข้อมูล
• ในการบรรยายของ Sebastian Wild ในงาน PyCon US 2023ได้ใช้แนวทางการอธิบาย Powersort ที่เน้นภาพประกอบมากขึ้น