อัลกอริทึมที่ฉันชอบ: การหาค่ามัธยฐานแบบเวลาเชิงเส้น (2018)

 (rcoh.me)
2 คะแนน โดย GN⁺ 2024-07-26 | 1 ความคิดเห็น | แชร์ทาง WhatsApp

การหาค่ามัธยฐานแบบ O(n log n)

  • วิธีที่ง่ายที่สุดคือจัดเรียงลิสต์แล้วเลือกค่ามัธยฐาน
  • ความซับซ้อนเชิงเวลาของการจัดเรียงแบบอิงการเปรียบเทียบคือ O(n log n)
  • ตัวอย่างโค้ด: 
    def nlogn_median(l):  
    l = sorted(l)  
    if len(l) % 2 == 1:  
        return l[len(l) // 2]  
    else:  
        return 0.5 * (l[len(l) // 2 - 1] + l[len(l) // 2])

การหาค่ามัธยฐานแบบ O(n) โดยเฉลี่ย

  • สามารถใช้อัลกอริทึม "quickselect" เพื่อหาค่ามัธยฐานได้ในเวลาเชิงเส้นโดยเฉลี่ย

  • เป็นอัลกอริทึมแบบเรียกซ้ำที่ Tony Hoare พัฒนาขึ้น

  • ขั้นตอน:

    1. เลือกดัชนีแบบสุ่มจากลิสต์แล้วตั้งเป็น pivot
    2. แบ่งลิสต์ออกเป็นสองกลุ่มโดยอิงจาก pivot:
      • องค์ประกอบที่น้อยกว่าหรือเท่ากับ pivot
      • องค์ประกอบที่มากกว่า pivot
    3. ค้นหาแบบเรียกซ้ำในกลุ่มที่มีค่ามัธยฐานอยู่

  • ตัวอย่างโค้ด:

    import random  

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))  

def quickselect(l, k, pivot_fn):  
    if len(l) == 1:  
        assert k == 0  
        return l[0]  

    pivot = pivot_fn(l)  
    lows = [el for el in l if el < pivot]  
    highs = [el for el in l if el > pivot]  
    pivots = [el for el in l if el == pivot]  

    if k < len(lows):  
        return quickselect(lows, k, pivot_fn)  
    elif k < len(lows) + len(pivots):  
        return pivots[0]  
    else:  
        return quickselect(highs, k - len(lows) - len(pivots), pivot_fn)

การพิสูจน์ค่าเฉลี่ย O(n)

  • หาก pivot แบ่งลิสต์ออกได้ประมาณครึ่งหนึ่ง การเรียกซ้ำแต่ละครั้งจะทำงานกับข้อมูลเพียงครึ่งหนึ่งของขั้นก่อนหน้า
  • การพิสูจน์ทางคณิตศาสตร์: 
    C = n + n/2 + n/4 + n/8 + ... = 2n = O(n)

O(n) แบบกำหนดแน่นอน

  • รับประกันเวลาเชิงเส้นแม้ในกรณีเลวร้ายที่สุด

  • ใช้อัลกอริทึม "median-of-medians" เพื่อเลือก pivot

  • ขั้นตอน:

    1. แบ่งลิสต์ออกเป็นกลุ่มละ 5 ค่า
    2. จัดเรียงแต่ละกลุ่มแล้วเลือกค่ามัธยฐาน
    3. เลือกค่ามัธยฐานของค่ามัธยฐานทั้งหมดมาเป็น pivot

  • ตัวอย่างโค้ด:

    def pick_pivot(l):  
    assert len(l) > 0  

    if len(l) < 5:  
        return nlogn_median(l)  

    chunks = chunked(l, 5)  
    full_chunks = [chunk for chunk in chunks if len(chunk) == 5]  
    sorted_groups = [sorted(chunk) for chunk in full_chunks]  
    medians = [chunk[2] for chunk in sorted_groups]  
    median_of_medians = quickselect_median(medians, pick_pivot)  
    return median_of_medians  

def chunked(l, chunk_size):  
    return [l[i:i + chunk_size] for i in range(0, len(l), chunk_size)]

สรุป

  • อัลกอริทึม quickselect สามารถหาค่ามัธยฐานได้ในเวลาเชิงเส้น หากเลือก pivot ได้เหมาะสม
  • อัลกอริทึม median-of-medians เป็นวิธีเลือก pivot ที่รับประกันเวลาเชิงเส้นแม้ในกรณีเลวร้ายที่สุด
  • ในทางปฏิบัติ การเลือก pivot แบบสุ่มมักมีประสิทธิภาพดีเพียงพอ

สรุปโดย GN⁺

  • บทความนี้อธิบายอัลกอริทึมหลายแบบสำหรับการหาค่ามัธยฐาน โดยเน้นเป็นพิเศษที่วิธีหาค่ามัธยฐานในเวลาเชิงเส้น
  • อัลกอริทึม quickselect เร็วโดยเฉลี่ย แต่หากต้องการรับมือกับกรณีเลวร้ายที่สุด ก็สามารถใช้อัลกอริทึม median-of-medians ได้
  • ในการใช้งานจริง การเลือก pivot แบบสุ่มมักมีประสิทธิภาพเพียงพอในเกือบทุกกรณี
  • อัลกอริทึมที่มีฟังก์ชันคล้ายกันอีกตัวคือ introselect ซึ่งถูกใช้ในไลบรารีมาตรฐานของ C++

บทความที่เกี่ยวข้อง

1 ความคิดเห็น

 
GN⁺ 2024-07-26
ความคิดเห็นบน Hacker News
  • เมื่อ 4 ปีก่อน มีการเขียนบทความยาวเปรียบเทียบอัลกอริทึมหาค่ามัธยฐานหลายแบบ
  • เมื่อ 10-15 ปีก่อน เคยใช้ MapReduce เพื่อหาค่ามัธยฐานจากรายการล็อกที่มีค่าหลายพันล้านค่า
    • หากรู้ความละเอียดและช่วงของข้อมูล ก็สามารถใช้ bucket sort ได้
    • แทนเวลาเป็นจำนวนเต็มหน่วยมิลลิวินาทีและสร้างฮิสโตแกรม ก็ทำให้หาค่ามัธยฐานได้ง่าย
  • ในปี 2017 มีการเผยแพร่งานวิจัยที่ทำให้แนวทาง median-of-medians แข่งขันกับ selection algorithm แบบอื่นได้มากขึ้น
    • Andrei Alexandrescu เคยบรรยายเกี่ยวกับอัลกอริทึมนี้ในปี 2016
  • รายชื่อผู้เขียนอัลกอริทึม median-of-medians ล้วนมีชื่อเสียงมาก
    • เช่น Manuel Blum, Robert Floyd, Ron Rivest, Bob Tarjan, Vaughan Pratt
  • อัลกอริทึม Floyd-Rivest ก็มีประสิทธิภาพเช่นกัน แต่เข้าใจได้ยาก
  • หากใช้อัลกอริทึมแบบสตรีมมิง ก็สามารถคำนวณค่าประมาณได้โดยไม่ต้องเก็บข้อมูลทั้งหมดไว้ในหน่วยความจำ
  • มีวิธีดัดแปลง quicksort เพื่อใช้เลือกค่ามัธยฐาน
  • เคยได้รับคำถามสัมภาษณ์เกี่ยวกับการหาค่ามัธยฐานจากลิสต์ที่มีตัวเลขระดับล้านล้านตัว
    • ใช้วิธีกำหนดขอบเขตบนและล่างเพื่อหาค่ามัธยฐาน แต่ไม่ใช่วิธีที่ดีที่สุด
    • มีวิธีที่มีประสิทธิภาพกว่าด้วยการใช้ priority heap
    • หลังจากนั้นก็เริ่มสมัครใช้ LeetCode
  • มีการแชร์ตัวอย่างง่าย ๆ ที่เขียนด้วย Go
  • Radix sort ใช้ได้กับข้อมูลหลายประเภทนอกเหนือจากจำนวนเต็ม เช่น สตริง