ในวิทยาการคอมพิวเตอร์ อัลกอริทึมการรวม k ทิศทางหรือการรวมหลายแบบเป็นลำดับขั้นตอนการรวมที่เฉพาะเจาะจงซึ่งมีความเชี่ยวชาญในการรวมลิสต์ที่ทำการจัดเรียงแล้วหลายๆลิสต์ให้กลายเป็นลิสต์ที่จัดเรียงแล้วลิสต์เดียว อัลกอริทึมการรวมเหล่านี้โดยทั่วไปหมายถึงอัลกอริทึมการรวมที่ใช้ในกับลิสต์ที่มีจำนวนมากกว่าตั้งแต่ 2 ลิสต์ขึ้นไป การรวมสองทิศทางจะเรียกว่าการรวมแบบไบนารี

การรวมสองทิศทาง

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

แสดงโดย A [1..p] และ B [1..q] สองอาร์เรย์เรียงตามลำดับที่เพิ่มขึ้น นอกจากนี้แสดงโดย C [1..n] อาร์เรย์ผลลัพธ์ อัลกอริธึมการรวมสองทิศทางวิธีตามรูปแบบ จัดเก็บดัชนี i, j และ k เป็น A, B และ C ตามลำดับ ตอนแรกดัชนีเหล่านี้อ้างอิงถึงองค์ประกอบแรกคือ 1. ถ้า A [i] <B [j] แล้วอัลกอริทึมจะทำสำเนา A [i] ลงใน C [k] และเพิ่ม i และ k มิฉะนั้นอัลกอริทึมจะคัดลอกไบนารีไปที่ C [k] และเพิ่มค่า j และ k กรณีพิเศษเกิดขึ้นถ้าทั้ง i หรือ j ถึงจุดสิ้นสุดของ A หรือ B ในกรณีนี้อัลกอริทึมจะคัดลอกองค์ประกอบที่เหลือของ B หรือ A ไปที่ C และสิ้นสุดลง

การรวม k ทิศทาง

ปัญหาการรวม k ทิศทาง ประกอบด้วยการรวม k อาเรย์ที่เรียงลำดับเพื่อสร้างอาร์เรย์ที่เรียงลำดับอาเรย์เดียวที่มีองค์ประกอบเดียวกัน แสดงด้วยจำนวนองค์ประกอบทั้งหมด n เท่ากับขนาดของอาร์เรย์ผลลัพธ์และผลรวมของขนาดของอาร์เรย์อินพุท k เพื่อความเรียบง่ายเราถือว่าไม่มีอาร์เรย์อินพุตว่างเปล่า เป็นผลให้ k <n ซึ่งช่วยลดความยุ่งยากในการทำงานที่รายงานไว้ ปัญหาสามารถแก้ไขได้ใน O (n log k) เวลาทำงานกับ O (n) พื้นที่ มีอัลกอริธึมหลายตัวที่สามารถใช้งานได้

การรวมสองทิศทางซ้ำ

ปัญหาสามารถผสานโดยการรวมสองอาร์เรย์ k โดยใช้การรวม 2 ทางจนกว่าจะมีเพียงอาร์เรย์เดียวที่เหลืออยู่ ถ้าอาร์เรย์ถูกรวมเข้าด้วยกันตามลำดับแล้วเวลาที่ใช้ในการประมวลผลจะเป็น O (kn) เท่านั้น นี่คือ suboptimal

เวลาในการทำงานสามารถปรับปรุงได้โดยการผสานรวมซ้ำเข้าด้วยกันเป็นครั้งแรกกับครั้งที่สองที่สามโดยที่สี่และอื่น ๆ เนื่องจากจำนวนอาร์เรย์ลดลงครึ่งหนึ่งในการทำซ้ำแต่ละครั้งมีเฉพาะการทำซ้ำ O (log k) ในแต่ละรอบจะมีการย้ายองค์ประกอบทั้งหมด 1 ครั้ง เวลาทำงานต่อการทำซ้ำเป็นดังนั้นใน O (n) เป็น n คือจำนวนขององค์ประกอบ ระยะเวลาในการทำงานทั้งหมดจึงอยู่ที่ O (n log k)

การรวม k ทิศทางโดยตรง

แนวคิดพื้นฐานของการรวม k ทิศทางโดยตรงประกอบด้วยการคำนวณองค์ประกอบต่ำสุดของอาร์เรย์ k ทั้งหมดอย่างมีประสิทธิภาพและจากนั้นถ่ายโอนไปยังอาร์เรย์ผลลัพธ์

การดำเนินการที่ซับซ้อนจะสแกนอาร์เรย์ k ทั้งหมดเพื่อกำหนดค่าต่ำสุด การดำเนินการที่ตรงไปตรงมานี้ส่งผลให้เวลาในการทำงานเป็น O (kn) โปรดทราบว่านี่เป็นเพียงความเป็นไปได้ในการพูดคุยเท่านั้น แม้ว่าจะใช้งานได้ แต่ผลไม่ค่อยดีนัก

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

def k_way_merge_sorted(klist):

  result = []

  k = len(klist)

  if k == 1:

    return klist[0]

  elif k == 0:

    return []

  stop = 0

  while stop < 2:

    min_point = 0

    pop_point = 0

    for i in range(k-1):

        if(klist[i+1] == []):

            pop_point = i+1

        elif(klist[min_point] == []):

            pop_point = min_point

        elif(klist[i+1][0] < klist[min_point][0]):

            min_point = i+1

            pop_point = min_point

    if(klist[pop_point] == []):

       klist.pop(pop_point)

       stop += 1

       k -= 1

    else:

       result.append(klist[min_point].pop(0))        

  result += klist[0]

  return result

การเรียงลำดับภายนอก

การรวม k ทิศทางใช้ในการจัดเรียงข้อมูลภายนอก อัลกอริทึมการเรียงลำดับภายนอกเป็นคลาสของอัลกอริทึมที่จัดเรียงที่สามารถจัดการข้อมูลจำนวนมหาศาล การจัดเรียงข้อมูลภายนอกจะต้องใช้เมื่อข้อมูลที่จัดเรียงไม่พอดีกับหน่วยความจำหลักของอุปกรณ์คอมพิวเตอร์ (โดยปกติคือ RAM) และแทนที่จะต้องอยู่ในหน่วยความจำภายนอกที่ช้ากว่า (โดยปกติจะเป็นฮาร์ดไดรฟ์) อัลกอริทึมการรวม k ทิศทาง มักจะเกิดขึ้นในขั้นตอนที่สองของอัลกอริทึมการเรียงลำดับภายนอกแบบเดียวกับที่ใช้ในการรวมการจัดเรียง

เราสามารถปรับปรุงอัลกอริธึมนี้ได้โดยการรวมสองอาร์เรย์ที่สั้นที่สุด ทำให้ช่วยลดระยะเวลาในการทำงานและถ้าเกิดว่าโชคร้ายอาเรย์เป็นไปตามที่อธิบายไว้ในย่อหน้าก่อนหน้านี้ เวลาทำงานจะเป็น O (n log k) แต่ถ้าโชคดีเวลาทำงานจะดีขึ้น ตัวอย่างเช่นกรณีที่โชคร้ายทั้งหมด แต่หนึ่งอาร์เรย์มีเพียงหนึ่งองค์ประกอบ ตามที่อธิบายไว้ในย่อหน้าก่อนจะต้องใช้เวลาในการทำงาน O (n log k) ในขณะที่ถ้าเราปรับปรุงแล้วจะใช้เวลาทำงานเพียง O (n)

อ้างอิง

เชิงอรรถ

Thomas H. Cormen; Charles E. Leiserson; Ronald L. Rivest; Clifford Stein (2001). Introduction To Algorithms. MIT Press. pp. 28–29. ISBN 978-0-262-03293-3.
Bentley, Jon Louis (2000). Programming Pearls (2nd ed.). Addison Wesley. pp. 147–162. ISBN 0201657880.
Knuth, Donald (1998). "Chapter 5.4.1. Multiway Merging and Replacement Selection". Sorting and Searching. The Art of Computer Programming. 3 (2nd ed.). Addison-Wesley. pp. 158–168. ISBN 0-201-89685-0.
Shaffer, Clifford A. (2012-07-26). Data Structures and Algorithm Analysis in C++, Third Edition. Courier Corporation. ISBN 9780486172620.

ผู้ใช้:Kacha001/อัลกอริทึมการรวม k ทิศทาง

เนื้อหา