- มัธยฐานหาได้ง่ายด้วยการเรียงลำดับ แต่ด้วยต้นทุนของการเรียงลำดับ แม้แต่ปัญหาการเลือกสมาชิกเพียงตัวเดียวก็ยังติดเพดาน O(n log n)
- quickselect สามารถค้นหาเฉพาะฝั่งที่จำเป็นแบบเรียกซ้ำ เพื่อหา kth element หรือมัธยฐานได้ในเวลาเฉลี่ย O(n)
- pivot แบบสุ่มใช้งานได้ดีในทางปฏิบัติ แต่ถ้าเลือก pivot แย่ต่อเนื่อง จะตัดสมาชิกออกได้ทีละตัวเท่านั้น และแย่ลงได้ถึง O(n²)
- median-of-medians จัดกลุ่มทีละ 5 ตัว แล้วเลือกมัธยฐานอีกครั้งจากมัธยฐานของแต่ละกลุ่ม ทำให้แม้ในกรณีแย่ที่สุดก็สามารถตัดสมาชิกออกได้อย่างน้อย 30%
- ในการใช้งานจริง ต้นทุนการคำนวณ pivot อาจสูงได้ ดังนั้น introselect ซึ่งผสม quickselect กับ heapselect เหมือนในไลบรารีมาตรฐานของ C++ อาจเป็นตัวเลือกที่ใช้งานได้จริงกว่า
ข้อจำกัดของการหามัธยฐานด้วยการเรียงลำดับ
- วิธีคำนวณมัธยฐานที่ง่ายที่สุดคือเรียงลำดับลิสต์ แล้วเลือกค่าที่ตำแหน่งดัชนีกลาง
- สำหรับลิสต์ที่มีความยาวเป็นเลขคี่ จะคืนสมาชิกตรงกลาง และสำหรับลิสต์ที่มีความยาวเป็นเลขคู่ จะคืนค่าเฉลี่ยของสมาชิกตรงกลางสองตัว
- time complexity ที่เร็วที่สุดของการเรียงลำดับแบบอาศัยการเปรียบเทียบคือ O(n log n) ดังนั้นเวลารันของวิธีนี้จึงถูกครอบงำโดยการเรียงลำดับ
- แม้จะมีข้อดีคือโค้ดเรียบง่าย แต่สำหรับการหามัธยฐานเพียงค่าเดียว ถือว่าทำงานเกินจำเป็น
quickselect ที่ทำให้เป็นเวลาเฉลี่ย O(n)
- quickselect เป็นอัลกอริทึมแบบเรียกซ้ำที่ Tony Hoare สร้างขึ้น และสามารถหา kth element ใด ๆ ของลิสต์ได้ ไม่ใช่แค่มัธยฐาน
- ลำดับการทำงานพื้นฐานคือแบ่งลิสต์โดยใช้ pivot เป็นเกณฑ์ แล้วค้นหาต่อเฉพาะฝั่งที่มี kth element อยู่
- เลือก pivot หนึ่งตัวจากลิสต์
- แบ่งลิสต์เป็นสมาชิกที่น้อยกว่าหรือเท่ากับ pivot และสมาชิกที่มากกว่า pivot
- ตัดสินว่า kth element ที่ต้องการอยู่ฝั่งใด แล้วเรียกซ้ำเฉพาะในลิสต์ส่วนนั้น
- เมื่อลงไปยังลิสต์ส่วนขวา ให้ปรับค่า k ตามจำนวนสมาชิกฝั่งซ้ายที่ถูกตัดออกไปแล้ว
- ในลิสต์ตัวอย่าง
[9,1,0,2,3,4,6,8,7,10,5] เนื่องจากมีความยาว 11 จึงค้นหาสมาชิกที่เล็กเป็นอันดับ 6 และค่อย ๆ ลดช่วงตาม pivot จนสุดท้ายคืนค่า 5
quickselect_median ถ้าลิสต์มีความยาวเป็นเลขคี่ จะหาเพียงดัชนีกลางหนึ่งตำแหน่งด้วย quickselect และถ้าเป็นเลขคู่ จะหาดัชนีกลางสองตำแหน่งแล้วนำมาหาค่าเฉลี่ย- ถ้า pivot แบ่งลิสต์ได้เกือบครึ่งต่อครึ่ง ปริมาณงานจะเป็น
n + n/2 + n/4 + ... = 2n จึงกลายเป็น O(n)
หากต้องการหลีกเลี่ยงกรณีแย่ที่สุด จำเป็นต้องมี pivot ที่ดี
- ค่าเฉลี่ย O(n) ของ quickselect อาศัยเงื่อนไขว่าการเลือก pivot ดีพอ
- หากโชคร้าย เช่น เลือกค่าสูงสุดเป็น pivot ในทุกขั้นตอน แต่ละขั้นจะตัดสมาชิกออกได้เพียงหนึ่งตัว และกลายเป็น O(n²)
- เพื่อรับประกันเวลาเชิงเส้นแม้ในกรณีแย่ที่สุด ต้องส่ง pivot ที่ดีพอให้ quickselect ได้ในเวลาเชิงเส้น
- อัลกอริทึมเลือก pivot นี้พัฒนาในปี 1973 โดย Blum, Floyd, Pratt, Rivest, Tarjan และบทความที่เกี่ยวข้องลิงก์ไว้เป็น 1973 paper
การเลือก pivot แบบ median-of-medians
- median-of-medians เป็นกระบวนการเลือก pivot ที่ดีให้ quickselect ใช้
- ลำดับการทำงานมีดังนี้
- ถ้ามีสมาชิกน้อยกว่า 5 ตัว ให้ใช้ฟังก์ชันหามัธยฐานแบบเรียงลำดับเดิม
- แบ่งลิสต์เป็นกลุ่มละ 5 ตัว
- เพื่อความเรียบง่าย ให้ทิ้งกลุ่มที่ไม่ครบ 5 ตัว
- เรียงลำดับแต่ละกลุ่ม แล้วรวบรวมมัธยฐานที่ดัชนี 2
- หามัธยฐานอีกครั้งจากลิสต์ของมัธยฐานที่รวบรวมได้ แล้วคืนเป็น pivot
- เนื่องจากขนาดของแต่ละกลุ่มคงที่ที่ 5 ตัว การเรียงลำดับรายกลุ่มจึงถือเป็นเวลาคงที่ และโดยรวมเป็นงาน O(n)
- การเรียกซ้ำเพื่อหามัธยฐานของมัธยฐานจะถูกนับในการวิเคราะห์เป็นปัญหาย่อยขนาด
n/5
ทำไมจึงตัดออกได้อย่างน้อย 30%
- สามารถวิเคราะห์คุณภาพของ pivot ได้โดยมองว่าเรียงกลุ่มละ 5 ตัวแล้ววางเป็นคอลัมน์ จากนั้นเรียงมัธยฐานของแต่ละคอลัมน์อีกครั้งเพื่อเลือกมัธยฐานของมัธยฐาน
- แม้ในกรณีแย่ที่สุดที่ pivot เอนไปทางต้นลิสต์มากที่สุด ก็ยังรับประกันได้ว่าสมาชิกในควอดแรนต์บางส่วนจะน้อยกว่าหรือมากกว่า pivot
- เมื่อหยิบสมาชิก 3 ตัวจากแต่ละคอลัมน์ และพิจารณาครึ่งหนึ่งของคอลัมน์ จะสามารถตัดสมาชิกออกได้อย่างน้อย
3/5 * 1/2 * n = 3/10 n ตัว
- อัตราส่วนการตัดออกที่รับประกัน: {p:30}
- เวลารันรวมเขียนเป็น recurrence ต่อไปนี้
T(n) = n + T(n/5) + T(7n/10)
- ในที่นี้
n คือการแบ่งพาร์ทิชัน, T(n/5) คือการคำนวณ median-of-medians และ T(7n/10) คือการค้นหาแบบเรียกซ้ำของ quickselect
- เนื่องจาก recurrence นี้มีพจน์เรียกซ้ำสองพจน์ จึงไม่สามารถใช้ Master theorem แบบง่าย ๆ ได้ และการพิสูจน์ด้วยอุปนัยเป็นวิธีที่เข้าใจได้โดยสัญชาตญาณกว่า
ผลลัพธ์จากการผสาน: การหามัธยฐานในเวลาเชิงเส้น
- หากได้รับ pivot ที่ดีพอ quickselect สามารถหามัธยฐานได้ในเวลาเชิงเส้น
- median-of-medians สามารถเลือก pivot ที่ดีซึ่ง quickselect ต้องการได้ใน O(n)
- เมื่อนำสองอัลกอริทึมมารวมกัน จะได้อัลกอริทึมที่หามัธยฐานหรือสมาชิกตัวที่ n ของลิสต์ได้ใน เวลาเชิงเส้น
ตัวเลือกในการใช้งานจริง
- ในงานจริง การเลือก pivot แบบสุ่มมักเพียงพอแทบทุกครั้ง
- median-of-medians ก็เป็นเวลาเชิงเส้นเช่นกัน แต่ในทางปฏิบัติอาจช้าเพราะต้นทุนการคำนวณ pivot สูง
- ไลบรารีมาตรฐานของ C++ ใช้ introselect ซึ่งผสม heapselect กับ quickselect และมีขอบเขตบน O(n log n)
- introselect โดยทั่วไปจะเริ่มด้วยอัลกอริทึมที่เร็วแต่มีขอบเขตบนไม่ดี และเมื่อเลือก pivot ที่มีประสิทธิภาพไม่ได้ จะสลับไปใช้อัลกอริทึมที่ช้ากว่าแต่มีขอบเขตบนดีกว่า
- ในการเปรียบเทียบจำนวนสมาชิกที่ฟังก์ชัน quickselect ตรวจดู pivot แบบกำหนดแน่นอนพิจารณาสมาชิกน้อยกว่า pivot แบบสุ่มแทบทุกครั้ง แต่การเปรียบเทียบนี้ไม่ได้รวมต้นทุนการคำนวณ median-of-medians
- new paper ที่ออกในปี 2017 มีเนื้อหาเกี่ยวกับการทำให้แนวทาง median-of-medians สามารถแข่งขันกับอัลกอริทึมการเลือกแบบอื่นได้
1 ความคิดเห็น
ความคิดเห็นจาก Hacker News
เมื่อราว 4 ปีก่อน ฉันเคยเปรียบเทียบอัลกอริทึมหาค่ามัธยฐานหลายแบบ แต่บทความดันยาวกว่าที่คาดไว้มาก :)
https://danlark.org/2020/11/11/miniselect-practical-and-generic-selection-algorithms/
เมื่อ 10~15 ปีก่อน ฉันต้องหาค่ามัธยฐานของค่าหลายพันล้านค่าที่ parse มาจากรายการล็อกขนาดหลายกิโลไบต์เป็นประจำ ตอนนั้นงานประมวลผลขนาดใหญ่ใช้ MapReduce กันอยู่ และกับข้อมูลระดับนี้ก็ต้องการไม่ใช่แค่เวลาเชิงเส้น แต่ถ้าเป็นไปได้ก็อยากให้กระจายทำงานแบบหลายเครื่องได้ใน single pass ด้วย
การที่รู้ทั้งความละเอียดและช่วงของข้อมูลล่วงหน้าช่วยได้มาก ค่าที่มีเป็นเวลาในหน่วยมิลลิวินาทีแบบจำนวนเต็ม จึงไม่ติดลบ และยังรู้ด้วยว่าเปอร์เซ็นไทล์ที่ 90 ต่ำกว่า 1 วินาทีมาก
ปกติการหาค่ามัธยฐานต้องทำงานคล้ายการเรียงลำดับ แต่ภายใต้เงื่อนไขแบบนี้ใช้bucket sortได้เลย แค่สร้างดิกชันนารีที่คีย์เป็นเวลาแบบจำนวนเต็มมิลลิวินาที และค่าคือจำนวนครั้งที่พบ หรือก็คือฮิสโตแกรม
เพราะไม่รู้ค่าเวลาสูงสุด เพื่อไม่ให้ขนาดดิกชันนารีพุ่งเกินไป ค่าที่เกิน 999ms จึงถูกรวมลงในบัคเก็ต 999ms ทั้งหมด แบบนี้จะถูกจำกัดไว้ที่คีย์และค่าช่วง 0~999 รวมแล้วราว 2000 จำนวนเต็ม ส่วนนี้ต่างจาก bucket sort แบบทั่วไป และทำได้ง่ายมากใน single pass แม้จะกระจายด้วย MapReduce จากนั้นก็ดึงค่ามัธยฐานจากฮิสโตแกรมได้เลย
ตัวเลข 10,000 เป็นแค่ตัวอย่างลอยๆ แต่จำนวนตัวอย่างที่ต้องใช้ตามระดับความเชื่อมั่นที่ต้องการคำนวณทางสถิติได้ และน่าจะไม่ต้องใหญ่โตอะไรนัก
ในบางระบบที่ฉันเคยดูแล Prometheus ดูเหมือนจะมีเพดาน latency อยู่ราว 10 วินาที ดังนั้นคำขอที่เกินขีดจำกัดนั้น แม้จริงๆ จะนานกว่านั้น ก็จะถูกนับเป็น 10 วินาทีทั้งหมด น่าสนใจดี
มีปัจฉิมลิขิตบอกว่า ในปี 2017 มีงานวิจัยใหม่ที่ทำให้แนวทาง median-of-medians แข่งขันกับอัลกอริทึมเลือกค่าแบบอื่นได้ และ Andrei Alexandrescu ผู้เขียนงานวิจัยนั้นเป็นคนมาบอกเอง
เขายังมีบรรยายเกี่ยวกับอัลกอริทึมของตัวเองในปี 2016 ด้วย เป็นคนพูดที่สนุกมาก แนะนำอย่างยิ่ง
There's Treasure Everywhere - Andrei Alexandrescu
https://www.youtube.com/watch?v=fd1_Miy1Clg
ถ้าคุณเป็นคนที่ใช้ซอฟต์แวร์ ฉันแนะนำให้ลองฟังและอ่านงานเขียนกับบรรยายของ Andrei ทุกชิ้นที่หาได้ อันนี้ก็เป็นของดีจริงๆ
ตอนเรียนปริญญาตรีฉันเคยเรียนอัลกอริทึม median-of-medians quickselect และประทับใจมาก ลองเขียนเองแล้วรู้สึกว่าช้ามากอย่างน่ากลัว เวลาในการรันโตแบบเชิงเส้นก็จริง แต่กว่าจะมีความหมายได้ รายการต้องมีอย่างน้อยหลายพันล้านรายการ
ฉันเคยคุยเรื่องนี้กับเพื่อนที่เป็นนักศึกษาบัณฑิตศึกษา แล้วได้คำตอบประมาณว่า “มันช้าก็จริง แต่ประเด็นสำคัญคือมันพิสูจน์ได้ว่าการเลือกค่าจากลิสต์ที่ยังไม่เรียงสามารถทำได้ในเวลา O(n) ครั้งหนึ่งเราไม่รู้ด้วยซ้ำว่ามันเป็นไปได้ไหม และเมื่อรู้แล้วว่ามันทำได้ ก็อาจมีอัลกอริทึมเชิงเส้นที่เร็วกว่านี้ได้”
มันเป็นบทเรียนที่ทั้งเรียบง่ายและลึกมาก จนฉันแทบจะสมัครเรียนต่อบัณฑิตศึกษาเลย ไม่รู้ว่าเพื่อนคนนั้นยังจำบทสนทนานี้ได้ไหม แต่มันเป็นช่วงเวลาคล้ายจุดเปลี่ยนในการศึกษาของฉัน
อาจคิดได้เหมือนกันว่า “เมื่อรู้อยู่แล้วว่ามีอัลกอริทึมบางตัวอยู่ ก็อาจมีอัลกอริทึมที่เร็วกว่านั้นได้” แล้วทำไมการมีอยู่ของอัลกอริทึม O(n) ถึงเป็นสัญญาณที่แรงกว่าการมีอยู่ของอัลกอริทึม O(n log n)?
เหมือนจะจำได้ว่าค่าคงที่ของอัลกอริทึมนี้อยู่แถวๆ 22 แต่อาจเป็นอีกอัลกอริทึมที่เกี่ยวข้องก็ได้
หนึ่งในจุดที่น่าสนใจของอัลกอริทึม median-of-medians คือรายชื่อผู้เขียนนั้นเป็นระดับ ซูเปอร์สตาร์ ล้วน ๆ
Manuel Blum - ผู้ได้รับรางวัล Turing Award ปี 1995
Robert Floyd - ผู้ได้รับรางวัล Turing Award ปี 1978
Ron Rivest - ผู้ได้รับรางวัล Turing Award ปี 2002
Bob Tarjan - ผู้ได้รับรางวัล Turing Award ปี 1986 และผู้ได้รับรางวัล Nevanlinna Award คนแรกในปี 1982
Vaughan Pratt - เป็นคนเดียวในรายชื่อที่ไม่ได้รับ Turing Award แต่เป็นศาสตราจารย์กิตติคุณของ Stanford เป็นผู้นำโครงการ SUN ก่อนจะกลายมาเป็น Sun Microsystems มีบทบาทสำคัญในช่วงแรกของ Sun ทั้งในฐานะหัวหน้าฝ่ายวิจัยและผู้ออกแบบโลโก้ Sun และยังฝากผลงานเจ๋ง ๆ ไว้อีกมาก เช่น Pratt primality certificate
ทั้ง Turing Award อิสระ 4 รางวัลและ SPARCstation ก็มีครบอยู่ในเปเปอร์นี้
รายชื่อผู้เขียนน่าประทับใจจริง ๆ
ตัว “P” ในอัลกอริทึม KMP ก็มาจาก Pratt
return l[len(l) / 2]ผมไม่ใช่ผู้เชี่ยวชาญ Python แต่ใน Python ตัวดำเนินการ
/ไม่ได้คืนค่าเป็นเลขทศนิยมเหรอ? ทำไมไม่ใช้//ซึ่งเป็นการหารจำนวนเต็ม แทนการใช้เลขทศนิยมเป็นดัชนีของอาร์เรย์?ถ้าไม่ใช่อาร์เรย์ที่ใหญ่มากอาจไม่เป็นปัญหา แต่ก็ยังมีกลิ่น code smell อยู่พอสมควร ถ้าเป็นมือใหม่ Python ที่ไม่รู้ว่ามีตัวดำเนินการสองแบบแยกกัน ก็อาจปล่อยผ่านได้ แต่ในบทความยังมีโค้ดที่แปลกกว่านั้นอีก คือในแขนงหนึ่งใช้การหารจำนวนเต็ม แต่อีกแขนงหนึ่งใช้การหารเลขทศนิยม
def quickselect_median(l, pivot_fn=random.choice):if len(l) % 2 == 1:return quickselect(l, len(l) // 2, pivot_fn)else:return 0.5 * (quickselect(l, len(l) / 2 - 1, pivot_fn) +quickselect(l, len(l) / 2, pivot_fn))มีคอมเมนต์ตั้ง 50 อันแต่ดูเหมือนไม่มีใครสังเกตเรื่องนี้เลย เลยยิ่งตอกย้ำอคติเดิมของผมเกี่ยวกับ คุณภาพโค้ด Python โดยเฉลี่ย
ถ้าใช้เลขทศนิยมเป็นดัชนีอาร์เรย์ก็น่าจะเกิด exception
เขาเลือกใช้ภาษาจริงที่หน้าตาเหมือน pseudocode แทน pseudocode ตรง ๆ และสำหรับจุดประสงค์ด้านการอธิบาย ก็น่าจะเป็นโค้ดที่รันได้ดีพอ
ต้นฉบับอ่านสนุกมากจริง ๆ แต่ผมติดใจตรงที่บอกว่า “ถ้าเลือกสมาชิกที่ใหญ่ที่สุดเป็น pivot ทุกขั้น ก็อาจกลายเป็น O(n²) แทน O(n)”
ถ้ากังวลเรื่องอินพุตแบบ adversarial ก็สามารถ shuffle ข้อมูลก่อนด้วยเวลา O(n) เพื่อกันไม่ให้เกิดสถานการณ์นั้นแบบบังคับได้ ถ้าข้อมูลใหญ่เกินกว่าจะ shuffle ได้ง่าย ก็รอให้ bucket เล็กลงจนมีขนาดที่ shuffle ได้ แล้วค่อยสับแค่ครั้งเดียว
ถ้า shuffle แล้ว ก็รับประกันได้ในเชิงความน่าจะเป็นว่ากรณีเลวร้ายสุดแทบจะไม่เกิดขึ้นจริง ถ้าใครบอกว่า “ในทางเทคนิค” มันยังเป็นไปได้ ผมก็จะตอบว่า “ในทางเทคนิค” ผู้โจมตีก็อาจเดาบิตทั้งหมดของ private key 256 บิตได้เหมือนกัน
โลกของเราสร้างอยู่บนความน่าจะเป็น private key ทุกอันได้รับการปกป้องเพราะมันไม่ได้เป็นไปไม่ได้ในเชิงคณิตศาสตร์ที่ใครสักคนจะเดาได้ถูกทุกบิต
เท่าที่ผมอ่านมา quickselect หลัง shuffle แล้ว ในทางปฏิบัติก็คือ O(n)
แต่ถ้าเชื่อถือ RNG ได้ ความน่าจะเป็นที่จะใช้เวลาเกิน O(n) ก็น่าจะต่ำมากอยู่ดี
Floyd-Rivest ก็ทำสิ่งนั้นได้เหมือนกัน ถ้าจำไม่ผิดจะมีประสิทธิภาพกว่านิดหน่อย
แต่ผมก็ไม่เคยเข้าใจหลักการทำงานของมันจนสุด
https://en.m.wikipedia.org/wiki/Floyd%E2%80%93Rivest_algorithm
เวลาเลือกสมาชิกอันดับที่ n ถ้า n เล็กมากหรือใหญ่มาก median-of-medians อาจไม่ใช่ตัวเลือกที่ดีที่สุด
อาจใช้ pivot แบบเอนเอียงอย่างใน [1] แทน หรือใช้วิธีที่ผมเรียกว่า “j-th of k-th” ก็ได้ Floyd-Rivest ก็เร่งให้เร็วขึ้นได้เช่นกัน
มีโปรเจกต์เล่น ๆ ที่ทำ throughput ได้ 1.2 ถึง 2.0 เท่าเมื่อเทียบกับ quickselect ที่เขียนมาดีแล้ว: https://github.com/koskinev/turboselect
ถ้าใครมีแหล่งข้อมูลเกี่ยวกับอัลกอริทึม selection แบบ in-place ที่เร็วและใช้ได้ทั่วไป ผมสนใจมาก
[1] https://doi.org/10.4230/LIPIcs.SEA.2017.24
คุณยังสามารถใช้อัลกอริทึมแบบ streaming เพื่อคำนวณค่าประมาณของ quantile ใด ๆ ก็ได้ โดยไม่ต้องเก็บข้อมูลทั้งหมดไว้ในหน่วยความจำ
ยอมรับการคำนวณแบบประมาณได้จริงหรือไม่? ต้องตั้งสมมติฐานอะไรเกี่ยวกับข้อมูลเพื่อกำหนดขอบเขตความคลาดเคลื่อน? แล้วจะตรวจสอบได้อย่างไรว่าสมมติฐานนั้นยังใช้ได้อยู่เรื่อย ๆ?
ส่วนตัวผมคิดว่าคงเอนเอียงไปทางอัลกอริทึม quickselect จากบทความต้นฉบับ จนกว่าจะอยู่ในสถานการณ์ที่จำเป็นต้องพิจารณาวิธีประมาณค่ามัธยฐานแบบสตรีมมิงจริง ๆ