CoE KKU

อัลกอริทึมในการจัดเรียงที่กล่าวมาแล้วทั้งหมดนั้นต้องให้ข้อมูลทั้งหมดสามารถบรรจุอยู่ในหน่วยความจำหลัก ซึ่งเรียกว่า Internal sorting อย่างไรก็ตาม ในการประยุกต์ใช้งานทั่วไปนั้นมักมีปัญหาที่ไม่สามารถนำข้อมูลทั้งหมดมาบรรจุลงในหน่วยความจำหลักได้ในคราวเดียว ในหัวข้อนี้จะกล่าวถึงอัลกอริทึมการจัดเรียงที่เรียกว่า external sorting ซึ่งใช้จัดการกับข้อมูลอินพุตขนาดใหญ่มาก ๆ

internal sorting ใช้ประโยชน์จากความจริงที่ว่าเราสามารถเข้าถึงหน่วยความจำได้โดยตรง ซึ่ง Shellsort เทียบค่า a[i] และ a[i - hk] โดยใช้เวลา 1 หน่วยเวลา อัลกอริทึม Heapsort เทียบค่าระหว่าง a[i] และ a[i*2+1] โดยใช้ 1 หน่วยเวลา Quicksort ที่ใช้ median-of-three partitioning เทียบค่าของ a[left], a[center], และ a[right] ด้วยเวลาคงที่ แต่ถ้าอินพุตอยู่ในเทป (หรือ disk) การทำงานดังกล่าวนั้นย่อมสูญเสียประสิทธิภาพไปเนื่องจากข้อมูลที่อยู่ในเทปนั้นต้องเข้าถึงแบบ sequential ถึงแม้ข้อมูลจะอยู่ในจานแม่เหล็กการทำงานดังกล่าวในทางปฏิบัติแล้วก็สูญเสียประสิทธิภาพไป เช่นกันเนื่องจากต้องใช้เวลาในการเข้าถึงหน่วยข้อมูลในจานแม่เหล็ก

external sorting ขึ้นอยู่กับชนิดของ storage devices ที่ใช้ว่าเป็นชนิดใด อัลกอริทึมที่จะกล่าวถึงนี้ใช้สำหรับข้อมูลที่จัดเก็บอยู่ในหน่วยเก็บข้อมูลที่เป็นเทปซึ่งต้องเข้าถึงด้วยการหมุนม้วนเทปไปยังตำแหน่งที่ต้องการข้อมูล (ในทิศทางไปและกลับ)

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

อัลกอริทึมของ external sorting แบบพื้นฐานใช้ฟังก์ชันการควบรวมจาก mergesort สมมติเรามีเทป 4 ตัว คือ Ta1, Ta2, Tb1, Tb2, ซึ่งจะใช้เป็นอินพุตสองตัวและใช้เป็นเอาต์พุตสองตัว เทป a และ b จะเป็น input หรือ output นั้นขึ้นอยู่กับจุดที่ทำงานในระหว่างการทำงานของอัลกอริทึม สมมติให้ข้อมูลเริ่มต้นอยู่ใน Ta1 และหน่วยความจำหลักสามารถบรรจุข้อมูล (และจัดเรียง) ได้จำนวน M ตัวจากอินพุตในแต่ละเวลา ขั้นตอนแรกของการทำงานคือ อ่านค่าคราวละจำนวน M ตัวจากเทปอินพุตลงในหน่วยความจำหลักแล้วทำการจัดเรียงด้วย internal sort และเขียนกลับไปใน Tb1 และ Tb2 สลับกัน ชุดข้อมูลที่จัดเรียงแล้วและเขียนกลับไปนั้นเรียกว่า run เมื่อเสร็จขั้นตอนนี้ก็จะหมุนเทปกลับทั้งหมด สมมุติเรามีข้อมูลชุดเดียวกับที่แสดงในหัวข้อ Shellsort อยู่ในเทป ดังนี้

ถ้า M = 3 แล้วหลังจากสร้าง runs ก็จะได้ข้อมูลในเทปดังนี้

ขณะนี้ใน Tb1 และ Tb2 มีกลุ่มของ runs บรรจุอยู่ ให้นำ run แรกจากเทปแต่ละตัวมาควบรวมกันซึ่งจะได้ผลเป็น run ที่มีขนาดความยาวเป็นสองเท่าแล้วเขียนลงใน Ta1 ยังคงจำกันได้ว่าการควบรวมรายการ 2 รายการที่มีการจัดเรียงแล้วนั้นทำได้โดยเกือบจะไม่จำเป็นต้องใช้เนื้อที่หน่วยความจำเลย เนื่องจากการควบรวมทำได้โดยเลื่อน Tb1 และ Tb2 ไปข้างหน้า จากนั้นนำ run ต่อไปจากเทปทั้งสองมาควบรวมแล้วเขียนผลลงใน Ta2 ทำเช่นนี้ไปเรื่อย ๆ โดยใช้เทปสลับกันระหว่าง Ta1 และ Ta2 จนกว่าข้อมูลใน Tb1 หรืออาจจะใน Tb2 หมด

ในขณะนี้อาจจะอยู่ในสถานะที่เทปทั้งสองไม่มีข้อมูลเหลืออยู่หรืออยู่ในสถานะที่มีข้อมูลเหลืออยู่เพียงหนึ่ง run ในเทปตัวใดตัวหนึ่ง ถ้าเป็นสถานะหลังก็ให้ทำการคัดลอก run ที่เหลือนั้นไปลงในเทปตามทีควรจะเป็น จากนั้นให้กรอเทปทั้ง 4 กลับแล้วดำเนินการตามขั้นตอนข้างบนซ้ำอีก แต่ในเวลานี้จะใช้เทป a เป็นอินพุตและใช้เทป b เป็นเอาต์พุตซึ่งจะได้ runs ขนาดความยาวเป็น 4M เราจะทำซ้ำกระบวนการข้างบนจนกว่าจะได้ผลเหลือเพียงหนึ่ง run ที่มีความยาวเท่ากับ N

อัลกอริทึมที่ใช้นี้ต้องใช้จำนวนรอบ (pass) ในการทำงานเท่ากับ ⌈log(N/M) ⌉ รอบ บวกกับรอบของการสร้าง run เริ่มแรก เช่น ถ้าเรามีข้อมูลจำนวน 10 ล้านหน่วยข้อมูลโดยแต่ละหน่วยใช้พื้นที่ 128 ไบต์ และถ้ามีหน่วยความจำหลักขนาด 4 ล้านไบต์ นั่นคือ ในรอบแรกจะสร้าง run ได้ 320 runs และเราต้องใช้การทำงานอีก 9 รอบเพื่อจัดเรียงจนเสร็จสิ้น สำหรับกรณีตัวอย่างข้างบนเราต้องใช้จำนวนรอบการทำงานเพิ่มอีก ⌈log(13/3)⌉ = 3 รอบ ดังรูปข้างล่างนี้

พิจารณา running time ของอัลกอริทึม ดังนี้ หลังจากการสร้าง run เริ่มต้น จะได้จำนวน k runs: k = N/M
หลังการทำงานรอบแรก (1st pass) ของการทำงานจะได้จำนวน runs = ⌈N / 2*M⌉ runs
หลังการทำงานรอบที่สอง (2nd pass) ของการทำงานจะได้จำนวน runs = ⌈N / 2*2*M⌉ runs
…
ณ จุดสิ้นสุดการทำงานจะเหลือจำนวน runs เพียง 1 run ในรอบที่ $x^{th}$ นั่นคือ
หลังการทำงานรอบที่ x (xth pass) ของการทำงานจะได้จำนวน runs = $⌈N / 2^x * M⌉$ runs
ดังนั้น
\begin{align*} ⌈N / 2^x * M⌉ & = 1 \\ ⌈2^x⌉ & = ⌈N / M⌉ \\ x & = ⌈lg\ (N / M)⌉\\ & = \text{จำนวนรอบที่ใช้ในการทำงาน} \\ \end{align*}

ถ้าเรามีจำนวนเทปเพิ่มขึ้น เราก็สามารถลดจำนวนรอบการทำงานการจัดเรียงลงได้ และทำได้โดยการขยายการทำงานการควบรวมที่ใช้เดิม (ซึ่งเรียกว่าการทำงานแบบ two-way) ให้เป็นแบบ k-way merge

ในกรณีที่มีเทปสำหรับอินพุตสองตัว เราจะกรอเทปทั้งสองกลับไปจุดเริ่มต้นของแต่ละ run แล้วทำการควบรวมด้วยการหาค่าที่น้อยที่สุด (จากจำนวนสองตัวในเทปทั้งสอง) แต่ถ้าเรามีเทปสำหรับอินพุตจำนวน k ตัว วิธีการที่ใช้ก็จะยังคงเดิม แต่การหาค่าที่น้อยที่สุดก็ซับซ้อนขึ้น วิธีการที่ใช้ในการหาค่าที่น้อยที่สุดของสมาชิกเหล่านี้ก็คือการใช้ priority queue การให้ได้มาซึ่งค่าถัดไปที่จะเขียนลงในเทปที่เป็น output ก็จะใช้การทำงาน deleteMin จากนั้นเลื่อนเทปตัวที่ถูกอ่านค่าออกเอาต์พุตไปข้างหน้าหนึ่งตำแหน่งและถ้ายังมีค่าข้อมูลตัวถัดไปอยู่ก็จะทำการ insert ค่าใหม่นี้ลงใน priority queue จากข้อมูลตัวอย่างเดิมเราจะกระจายค่าอินพุตลงในเทป 3 ตัว จะได้ runs เริ่มต้นดังนี้

จากนี้ต้องทำงานอีก 2 รอบก็จะได้รายการที่มีการจัดเรียงค่า ดังนี้

หลังจากการสร้าง run เริ่มต้นแล้ว k-way merging ต้องใช้การทำงานอีกจำนวน ⌈logk(N/M)⌉ รอบ เนื่องจาก run ที่ได้จะมีขนาดใหญ่ขึ้นเป็น k เท่าของแต่ละรอบ จากตัวอย่างข้างบน เราจึงต้องการรอบการทำงานอีก ⌈log3 13/3⌉ = 2 ถ้าเรามีเทป 10 ตัว นั่นคือ k = 5 และจากตัวอย่างขนาดใหญ่ที่กล่าวมาแล้ว เราต้องใช้รอบการทำงานเพิ่มอีก ⌈log5 320⌉ = 4 รอบ

สำหรับ k-way merge หลังการสร้าง run เริ่มต้น จะได้จำนวน runs ทั้งสิ้น N / M runs
หลังการทำงานรอบแรก (1st pass) จะเหลือจำนวน runs = ⌈N / k*M⌉ runs
หลังการทำงานรอบที่สอง (2st pass) จะเหลือจำนวน runs = ⌈N / k*k*M⌉ runs
…
สุดท้ายเมื่อจบการทำงานจะเหลือจำนวน 1 runs เท่านั้น คือหลังการทำงานรอบที่ x^th นั่นคือ
หลังการทำงานรอบที่ x (x^th pass) จะเหลือจำนวน runs = $⌈N / k^x * M⌉$ runs (ซึ่งคือ 1 run)
ดังนั้น
\begin{align*} ⌈N / k^x * M⌉ & = 1\\ ⌈k^x⌉ & = ⌈N / M⌉ \\ x & = ⌈log_k (N/M)⌉ = \text{จำนวนรอบที่ใช้ในการทำงาน}\\ \end{align*}

สำหรับการใช้การควบรวมแบบ k-way ที่กล่าวมาแล้วนั้นจะต้องใช้เทปจำนวน 2k ตัว ซึ่งบางครั้งอาจจะไม่สะดวกหรือทำไม่ได้ อย่างไรก็ตามเป็นไปได้ที่จะใช้เทป k + 1 ตัว เช่นการทำ two-way merging จะใช้เทปเพียง 3 ตัว

สมมุติเรามีเทปอยู่ 3 ตัวคือ T1, T2, และ T3, และข้อมูลอินพุตอยู่ในเทป T1 ซึ่งมี 34 runs ทางเลือกแรกในการทำงานต่อไป คือ บรรจุข้อมูลลงในเทป T2 และ T3 ตัวละ 17 runs จากนั้นนำผลการควบรวมลงใน T1 ซึ่งก็จะมีข้อมูลจำนวน 17 runs ปัญหาก็คือ ข้อมูลทั้งหมดได้ถูกเก็บอยู่ในเทปเพียงตัวเดียว แต่เราต้องให้มี run บางชุดอยู่ใน T2 เพื่อจะทำการควบรวมได้ ซึ่งทำได้ด้วยการคัดลอก 8 run แรกจาก T1 ไปลงใน T2 แล้วจึงทำการควบรวม ข้อเสียคือมีการทำงานเพิ่มขึ้นครึ่งรอบสำหรับการทำงานในแต่ละรอบ

อีกทางเลือกคือ แบ่งจำนวน 34 runs ออกเป็นสองส่วนที่ไม่ต้องเท่ากัน เช่นเก็บ 21 runs ใน T2 และ 13 runs ใน T3 จากนั้นทำการควบรวม 13 runs ไปไว้ใน T1 แล้วกรอ T1 และ T3 กลับแล้วทำการควบรวม T1 ที่มี 13 runs เข้ากับ T2 ที่มี 8 runs (เหลือจากการควบรวมรอบที่แล้ว) ลงใน T3 ซึ่งการควบรวมรอบนี้ใช้ 8 runs ใน T2 จนหมด ส่วนใน T1 ยังคงเหลือ 5 runs และขณะนี้มี 8 runs ใน T3 ให้ทำการควบรวม T1 และ T3 และต่อไปเรื่อย ๆ ดังแสดงในรูปข้างล่างนี้

การจัดแบ่ง runs เริ่มต้นมีผลอย่างมากต่อการทำงานด้วยวิธีที่กล่าวมานี้ เช่นถ้าเราแบ่ง 22 runs ลงใน T2 และ 12 ลงใน T3 หลังการควบรวมครั้งแรกจะทำให้ได้ 12 runs ใน T1 และ 10 runs ใน T2 หลังจากควบรวมอีกรอบจะได้ 10 run ใน T3 และ 2 run ใน T1 จากนี้ไปการทำงานจะช้ามากเนื่องจากเราสามารถควบรวมได้คราวละ 2 runs เท่านั้นก่อนจำนวน run ใน T3 สุดท้ายจะเหลือจำนวน 2 runs ใน T2 เท่านั้น ทำให้ต้องคัดลอก 1 run จาก T2 ไปยังเทปอื่นตัวใดก็ได้ แล้วทำการควบรวมอีกครั้งหนึ่งเพื่อจบการทำงาน ดังรูปข้างล่างนี้

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

จากข้อสังเกตที่กล่าวมาข้างบนนี้ทำให้เราสามารถสร้างอัลกอริทึมเพื่อการสร้าง runs ได้ด้วยเทคนิคที่เรียกว่า replacement selection โดยเริ่มต้นอ่านค่าจำนวน M ตัวลงในหน่วยความจำหลักและสร้าง priority queue จากนั้นทำ deleteMin เพื่อนำค่าที่น้อยที่สุดของ heap ส่งออกไปยังเทปเอาต์พุต อ่านค่าตัวถัดไปจากเทปอินพุต ถ้าค่าที่อ่านมานี้มีค่ามากกว่าค่าที่เพิ่งจะถูกเขียนออกเทปเอาต์พุตเราก็สามารถรวมค่าที่อ่านเข้ามานี้เข้าเป็นส่วนของ priority queue ได้ ถ้าค่าที่อ่านมานี้เป็นค่าน้อยกว่าค่าที่เพิ่งจะถูกเขียนออกเทปเอาต์พุตแสดงว่ามันจะรวมอยู่ใน run เดียวกับค่าที่เพิ่งเขียนออกเอาต์พุตไม่ได้และเราจะเก็บค่าไว้ในพื้นที่ที่เราเรียกว่า dead space ของ priority queue เอาไว้ไปจนกว่าจะจบ run และใช้ข้อมูลตัวดังกล่าวนี้สำหรับ run ต่อไป เราจะทำเช่นนี้ไปจนกว่าจะได้ขนาดของ priority queue เป็นศูนย์ ซึ่งเป็นจุดจบ run เราจะเริ่มสร้าง run ใหม่ด้วยการสร้าง priority queue ใหม่ด้วยสมาชิกที่อยู่ใน dead space รูปที่ 7.18 แสดงการสร้าง run สำหรับตัวอย่างขนาดเล็กโดยมี M = 3 สมาชิกใน Dead space มีเครื่องหมายดอกจันกำกับอยู่

รูปที่ 7.18 ตัวอย่างการสร้าง run

ในกรณีที่อินพุตเป็นอินพุตที่มีการจัดเรียงหรือเกือบทั้งหมดมีการจัดเรียงมาก่อนแล้ว การใช้ replacement selection จะทำให้ได้จำนวน runs น้อย ๆ ที่แต่ละ run เป็นรายการขนาดใหญ่และจะทำให้จำนวนรอบของการควบรวมของ external sort น้อยลงไปด้วย