การจัดเรียงข้อมูลในหน่วยเก็บภายนอก (External Sort)

External Sorting

เป็นการจัดเรียงข้อมูลที่อยู่ในหน่วยความจำภายนอก (ถึงเรียกว่า External) เช่น เทป (Tape) หรือจะนำมาประยุกต์กับ Disk หรือ CD-ROM ก็ได้ หน่วยความจำภายนอกมีข้อดีคือมีขนาดใหญ่กว่า RAM จึงเก็บข้อมูลได้มากกว่า แต่มีข้อเสียคือ มีระยะเวลาในการอ่านเขียนช้ากว่า RAM มาก ดังนั้นวิธีการทำงานกับหน่วยความจำภายนอกมีหลักการคือ จะต้องอ่านเขียนให้น้อยที่สุด โดยอ่านขึ้นมาใส่ไว้ใน RAM ให้ได้มากที่สุดที่ RAM พอจะรับได้ และหลังจากประมวลผลเสร็จแล้ว จึงเขียนกลับออกไป

ในตัวอย่างต่อไปนี้เราจะสมมุติว่าหน่วยความจำภายนอกของเราคือเทปเสมอ ซึ่งมีข้อจำกัดคือเวลาอ่านเทปจะต้องอ่านจากต้นไปถึงสุดปลายโดยระหว่างกลางทางไม่สามารถถอยหลังได้ ถ้าอยากถอยหลังจะต้องกลับที่จุดเริ่มต้นใหม่เสมอ การกลับมาอ่านใหม่ที่จุดเริ่มต้นเราเรียกว่า rewind

สมมุติว่าเทปของเราเก็บข้อมูลเป็นตัวเลขไว้จำนวน 13 ตัว และหน่วยความจำ RAM ของเรามีที่พอสำหรับเก็บข้อมูลเลข 3 ตัวดังนี้

Simple Algorithm

การจัดเรียงแบบง่ายที่สุดในกรณีที่เรามีเทปอยู่ 4 เครื่อง และมี RAM อยู่ 3 หน่วย สามารถทำได้ดังนี้

เริ่มต้นมีข้อมูลเป็นเลข 13 ตัวอยู่ใน Tape 1 เราจะอ่านขึ้นมาใน RAM ทีละ 3 ตัว และจัดเรียงใน RAM เช่น จัดเรียงด้วยวิธี Insertion, Shell หรือ Quick ตามที่ได้ศึกษาผ่านมาแล้ว หลังจากจัดเรียงใน RAM เสร็จเราจะเขียนกลับออกไปไว้ที่ Tape 3 ดังนี้

การจัดเรียง 1 ชุดย่อย และนำชุดย่อยที่เรียงเรียบร้อยแล้วไปบันทึกไว้ที่เทปอีกตัว เราจะเรียก 1 ชุดย่อยนี้ว่า 1 Run จากภาพข้างต้นเป็นกรรมวิธีในการทำ 1 Run ในกรณีที่เรามี RAM แค่ 3 หน่วยเก็บ

จากตัวอย่างข้างต้นถ้าเราทำ Run ที่ 2 จะได้ภาพดังนี้

และถ้าเราทำแบบนี้ไปเรื่อยๆทีละ Run โดยสลับการเขียนระหว่าง Tape 3 และ Tape 4 เราจะได้ภาพสุดท้ายออกมาดังนี้

การอ่านและสร้าง Run ขึ้นมาแบบนี้ 1 ครั้งเราเรียกว่า 1 Pass ดังนั้นจากภาพบน เรียกได้ว่าเราทำ 1 Pass สำหรับ Tape 1 และเกิด 5 Run อยู่ Tape 3 และ Tape 4

จะสังเกตว่าข้อมูลยังไม่ได้ถูกจัดเรียงจนเสร็จ เรายังคงต้องทำการจัดเรียงต่อ โดยผสม (Merge) ข้อมูลที่อยู่ใน Tape 3 กับ Tape 4 เข้าด้วยกัน และเขียนกลับลงไปที่ Tape 1 และ Tape 2

เหตุผลที่เขียนกลับไปที่ Tape 1 ได้นั้นเนื่องจากข้อมูลบน Tape 1 เราถือว่าไม่มีค่าใดๆแล้ว เพราะเป้าหมายที่เราต้องการคือข้อมูลที่จัดเรียง เมื่อข้อมูลถูกอ่านไปที่ Tape 3 กับ Tape 4 หมดสิ้นแล้ว Tape 1 ถือว่าว่างเปล่าและสามารถเขียนทับไปได้

วิธีการอ่านและรวมข้อมูลเข้าด้วยกันเราจะใช้วิธีการ Merge Sort ตามที่ได้ศึกษาผ่านไปแล้ว ตัวอย่างเช่น หากเรา Merge ข้อมูล Run 1 และ Run 2 เข้าด้วยกันและนำไปเขียนไว้ที่ Tape 1 จะได้ภาพดังนี้

และถ้า Merge Run 3 กับ Run 4 เข้าด้วยกัน และนำไปเขียนลงใน Tape 2 จะได้ดังนี้

สุดท้าย Merge Run 5 (ซึ่งจริงๆไม่มีอะไรให้ Merge ด้วย) และนำไปเขียนลงใน Tape 1 จะได้ภาพดังนี้

เมื่อทำจนจบอีก Pass ที่ 2 เราจะได้ข้อมูลที่จัดเรียงเรียบร้อยไว้แล้ว 3 Run อยู่ใน Tape 1 กับ Tape 2 ส่วนข้อมูลใน Tape 3 กับ Tape 4 ถือว่าไม่มีประโยชน์ใดแล้วสามารถเขียนทับได้

ถึงตอนนี้เราทำไปแล้ว 3 Pass และเรากำลังจะจัดเรียงต่อ โดย Merge Run 1 กับ Run 2 เข้าด้วยกันและเขียนไปที่ Tape 3

และทำอีกรอบสำหรับ Merge Run 3 ซึ่งมี 15 อยู่เลขเดียว และนำไปเขียนไว้ที่ Tape 4 เมื่อเสร็จสิ้นการ Merge รอบนี้จะได้ผลลัพธ์ดังนี้

รอบสุดท้าย เราจะ Merge Run 1 กับ Run 2 เข้าด้วยกันและเขียนไปที่ Tape 1 จะได้ผลลัพธ์สุดท้ายดังนี้

จะสังเกตว่าเราทำงานทั้งหมด 4 Pass โดย

o    Pass ที่ 1 อ่าน Tape 1 สร้าง Run 1, 2, 3, 4, 5 โดยวิธี Internal Sort อะไรก็ได้

o    Pass ที่ 2 อ่าน Tape 3 และ Tape 4 สร้าง Run 1, 2, 3 โดยวิธี Merge Sort

o    Pass ที่ 3 อ่าน Tape 1 และ Tape 2 สร้าง Run 1, 2 โดยวิธี Merge Sort

o    Pass ที่ 4 อ่าน Tape 3 และ Tape 4 สร้าง Run 1 โดยวิธี Merge Sort

ถ้าเราใช้วิธีการ Simple นี้ในการจัดเรียงแบบ External Sort เราจะใช้จำนวน Pass ในการ Merge เท่ากับ Ceil(Log₂ (N/M)) เช่น ในกรณีนี้ N = 13 และ M = 3 จำนวน Pass ที่ใช้ในการ Merge คือ

                      จำนวน Pass ที่ใช้ Merge คือ         = Ceil(Log₂(13/3))

                                                          = Ceil(Log₂(4.33))

                                                          = Ceil(2.12)

                                                          = 3 Pass

ถ้าต้องการจำนวน Pass ทั้งหมด เราต้องบวกเพิ่มอีก 1 ที่เป็นจำนวน Pass รอบแรกที่ใช้อ่านอินพุตเข้ามา จึงได้จำนวน Pass ทั้งหมด เป็น 3 + 1 = 4 Pass ซึ่งจะตรงกับที่เราได้ทดลองไปแล้วตามภาพข้างต้น

ตัวอย่างการคำนวณ จำนวน Pass ของวิธี Simple เช่น ถ้ากำหนดให้มีเรคอร์ด (Record) อยู่ในเทปเป็นจำนวน 10 ล้านเรคอร์ด แต่ละเรคอร์ดยาว 128 ไบต์ และเรามี Internal Memory (RAM) จำนวน 4 เมกะไบต์ จงหาว่าต้องใช้จำนวน Pass ทั้งหมดกี่ Pass ในการจัดเรียงข้อมูลชุดนี้

                      M = 4 x 1024 x 1024 / 128         = 4,194,304 / 128

                                                                        = 32,768

                     

                      M = 32,768 เรคอร์ด

                      N = 10,000,000 เรคอร์ด

                     

                      จำนวน Pass ที่ใช้ Merge คือ         = Ceil(Log₂(N/M))

                                                                        = Ceil(Log₂(10,000,000 / 32,768))

                                                                        = Ceil(Log₂(305.1758))

                                                                        = Ceil(8.25)

                                                                        = 9 Pass

                      จำนวน Pass ทั้งหมดคือ                 = 9 + 1 = 10 Pass

Multiway Merge

แทนที่เราจะแตก Run ออกทีละ 2 เทปในกรณีที่เรามีจำนวนเทปเพียงพอ เราสามารถแตก Run ออกให้กระจายลงไปที่เทปได้มากกว่า 2 เทป ซึงจะช่วยลดจำนวน Pass ลงได้ เช่น ถ้าเรามีเทป 6 ตัว ดังนี้

สมมุติว่า M = 3 เหมือนเดิม เราจะอ่าน Tape 1 และแตกออกเป็น Run เขียนลงไปที่ Tape 4, 5, 6 ได้ดังนี้

เสร็จไป 1 Pass เราจะได้ 5 Run อยู่ใน Tape 4, 5, 6 ตามภาพข้างบน และ Tape 1 ถือว่าว่างเปล่า สามารถเขียนทับได้

วิธีการ Multiway Merge จะอ่านข้อมูลทั้ง 3 Run พร้อมกัน คือทั้ง Run 1, Run 2, Run 3 และ Merge เข้าด้วยกันให้กลายเป็น Run เดียว และเขียนลงไปที่ Tape 1 ดังนี้

และเมื่อ Merge Run 4 กับ Run 5 เข้าด้วยกันจะได้ภาพดังนี้

เมื่อผ่าน Pass 2 จะเหลือจำนวน Run เพียงแค่ 2 Run เท่านั้นอยู่ใน Tape 1 และ Tape 2 ดังนี้

และถ้าเราทำ Pass ที่ 3 เพื่อ Merge Run 1 กับ Run 2 นี้เข้าด้วยกัน และนำไปเขียนไว้ที่ Tape 4 จะได้ ผลลัพธ์สุดท้ายที่จัดเรียงแล้วดังนี้

สังเกตว่าถ้าเราเพิ่มจำนวนเทปเข้าไปและทำ Multiway Merge จะทำให้จำนวน Pass ลดลง ซึ่งการคำนวณหาจำนวน Pass ที่จะใช้ Merge จะเปลี่ยนจาก Log₂ กลายเป็น Log₃ คือ Ceil(Log₃(N/M))

เช่น ในที่นี้ N = 13, M = 3 เราสามารถคำนวณหาจำนวน Pass ได้คือ

จำนวน Pass ที่ Merge          = Ceil(Log₃(13/3))

                                           = Ceil(Log₃(4.33))

                                           = Ceil(1.33)

                                           = 2 Pass

จำนวน Pass ทั้งหมดคือ          = 2 + 1 = 3 Pass

อย่างไรก็ตามวิธีนี้มีข้อเสียคือ ในความเป็นจริงเราไม่สามารถหาซื้อเครื่องอ่านเขียนเทปได้มากขนาดนั้น จึงมีเทปอยู่จำนวนจำกัด

Polyphase Merge

จากตัวอย่างที่ผ่าน ถ้าเราจะ Merge ครั้งละ 3 Run เราต้องการเทปเป็นจำนวน 6 ตัว ดังนั้นถ้าเราจะ Merge ครั้งละ k Run เราต้องการเทปทั้งหมด 2k ตัว ซึ่งเป็นจำนวนที่ค่อนข้างมาก

วิธีการ Polyphase Merge ต้องการเทปเพียงแค่ k + 1 ตัวเท่านั้น เช่น ถ้าเราจะ Merge ครั้งละ 2 Run เหมือนกับวิธี Simple เราต้องการเทปเพียงแค่ 3 ตัว โดยทำตามลำดับดังนี้

เริ่มต้นเรามีเทป 3 ตัวโดย Tape 1 เป็นอินพุตที่ยังไม่จัดเรียง ส่วน Tape 2 กับ 3 เป็นตัวช่วย สมมุติว่าเรากำหนดให้ M = 3 เหมือนเดิม เราจะแตก Run ออกเป็น 5 Run และวางไว้ใน Tape 1 กับ 2 ได้ดังนี้ (ส่วนนี้ยังมีกระบวนการเหมือนกับ Simple เพราะฉะนั้นไม่ต้องคิดมาก)

เนื่องจากการจัดเรียงตัวเลขภายใน Run ไม่น่าสนใจเท่าไร เพราะทำเหมือนๆกันทุกครั้ง ดังนั้นต่อไปนี้จะเสนอภาพแบบสรุปจำนวน Run ในเทปแต่ละตัวแทน โดยเป็นภาพดังนี้

หมายความว่า Pass ที่ 1 ทำให้เกิดจำนวน Run ที่ Tape 1 จำนวน 0 Run (คือไม่มีเลย) และเกิดจำนวน Run ที่ Tape 2 จำนวน 3 Run และจำนวน Run ที่ Tape 3 จำนวน 2 Run ตามตารางสรุปด้านขวามือ

จากภาพข้างต้นเราจะเห็นว่าถ้าเราจะ Merge Run 1 กับ Run 2 เข้าด้วย เราต้องเอาไปเขียนฝากไว้ที่ Tape 1 ดังนี้

แต่ปัญหาคือ ถ้าเราจะ Merge Run 3 กับ Run 4 เข้าด้วยกัน เราจะไม่มีที่วางสลับเทปเหมือนกับวิธี Simple ที่ผ่านมา สำหรับวิธี Polyphase Merge อนุญาตให้วาง Run ต่อเนื่องลงไปที่ Tape เดียวกันได้เลย เพราะฉะนั้นเราจะ Merge Run 3 กับ Run 4 แล้วนำไปเขียนต่อไว้ที่ Tape 1 จะได้ภาพดังนี้

เมื่อมาถึงจุดนี้ต้องหยุดการ Merge เนื่องจาก Tape 3 เดินไปจนจุดสุดปลายแล้วจะได้ผลลัพธ์คือ Tape 1 มีจำนวน Run อยู่ 2 Run และ Tape 2 มีจำนวน Run ค้างอยู่ 1 Run เขียนเป็นตารางสรุปได้ดังนี้

รอบต่อมาเราจะ rewind เทปกลับไปที่จุดเริ่มต้นได้ภาพเป็นดังนี้

และเริ่ม Pass ที่ 3 โดย Merge Run 1 กับ Run 5 เข้าด้วยกัน นำไปเขียนไว้ที่ Tape 3 ได้ดังนี้

ดังนั้นเมื่อจบ Pass 3 เราจะมีจำนวน Run ในแต่ละ Tape ดังนี้

เรา rewind Tape 2, 3 กลับไปที่จุดเริ่มต้นและเริ่ม Pass ที่ 4 โดย Merge Run ที่เหลืออยู่ใน Tape 1 กับ Tape 3 และนำไปเขียนไว้ที่ Tape 2 สุดท้ายจะได้ภาพดังนี้

ซึ่งถือว่าเสร็จสิ้นกระบวนการ Polyphase Merge โดยใช้ Pass ทั้งหมด 4 Pass และใช้เทปเพียง 3 ตัวเท่านั้น

ด้วยวิธี Polyphase Merge เราจะหาจำนวน Pass ที่เกิดขึ้นได้อย่างไร ลองสมมุติว่าถ้าเรามีข้อมูลจำนวนหนึ่ง หลังจากสร้าง Run ครั้งแรกแล้วเราได้มาจำนวน 34 Run โดยแบ่งวางไว้ที่ Tape 2 จำนวน 21 Run และแบ่งวางไว้ที่ Tape 3 จำนวน 13 Run ดังนี้

ใช้วิธีการเดิมเพื่อ Merge Run ที่อยู่ใน Tape 2 กับ Tape 3 เข้าด้วยกัน จะได้มาเพียงแค่ 13 Run เท่านั้น เพราะ Tape 3 มีอยู่แค่นั้น และใน Tape 2 จะเหลือที่ไม่ได้ Merge อีก 8 Run ดังนี้

ใน Pass ที่ 3 เรา rewind Tape 1 กลับไปที่จุดเริ่มต้นและ Merge 8 Run ที่เหลือใน Tape 2 กับ 8 Run แรกใน Tape 1 จะได้ผลลัพธ์ดังนี้

เราทำอย่างนี้ไปเรื่อยๆจนสุดท้าย Merge กันจนหมดจะได้ตารางสรุป Pass ออกมาดังนี้

เราใช้จำนวน Pass ไปทั้งหมด 8 Pass จะ Merge รวม Run ทั้งหมดเข้าด้วยกันได้และวางไว้ที่ Tape 1

สังเกตว่าตัวเลขจำนวน Run สูงสุดของ Pass ที่ 1 คือ 21 ซึ่ง 21 ได้มาจาก 13 + 8 ส่วนเลขจำนวน Run สูงสุดใน Pass ที่  2 คือ 13 และ 13 ได้มาจาก 5 + 8 ลำดับของเลขนี้เป็นลักษณะ Fibonacci Number ตามสูตรที่บอกว่า

F(n) = F(n – 1) + F(n – 2)     โดยให้ F(1) และ F(2) = 1

ดังนั้นเราสามารถคำนวณจำนวน Pass ในกรณีที่ครั้งแรกแบ่งออกมาได้ 34 Run โดยใช้ Fibonacci ดังนี้

           F(1)                                                       = 1

           F(2)                                                       = 1 + 1                 = 2

           F(3)                          = F(2) + F(1)        = 2 + 1                 = 3

           F(4)                          = F(3) + F(2)        = 3 + 2                 = 5

           F(5)                          = F(4) + F(3)        = 5 + 3                 = 8

           F(6)                          = F(5) + F(4)        = 8 + 5                 = 13

           F(7)                          = F(6) + F(5)        = 13 + 8               = 21

           F(8)                          = F(7) + F(6)        = 21 + 13             = 34

จะเห็นว่าเมื่อจบที่ F(8) เราได้ค่าเป็น 34 เท่ากับจำนวน Run ที่แตกออกมาได้พอดี นั่นแสดงว่า ถ้าเรามีจำนวน Run เป็น 34 เราจะต้องใช้ทั้งหมด 8 Pass ในการ Merge เข้าด้วยกันจนหมด

Replacement Selection

วิธีการใช้แนวคิดว่า ขณะที่อ่านข้อมูลมาจากเทปมีความเป็นไปได้ว่า Run ที่อ่านเข้ามาอาจจะมีค่าสูงกว่า Run ที่

ทุกครั้งที่อ่านเข้ามาเราจะนำข้อมูลมาสร้างเป็น Heap และอ่านค่า Root ของ Heap ที่เป็นค่าน้อยที่สุด เขียนออกไปที่เทป ตัวอย่างเช่น

อ่านข้อมูลมาและเก็บไว้ใน Heap เลขน้อยสุดจะอยู่ที่ Root ของ Heap เสมอ เสร็จแล้วให้ deleteMin ที่ Root ของ Heap นำไปเขียนลงใน Tape 2 ดังนี้

ถัดมา deleteMin ได้ค่าเป็น 81 เอาไปใส่ Tape 2 แล้วอ่านค่า 12 เข้ามา เนื่องจาก 12 น้อยกว่า 81 ดังนั้นเราจะนำ 12 ใส่เข้าไปใน Heap ไม่ได้ เราจะลดขนาด Heap ลงจาก 3 ช่อง เหลือ 2 ช่อง และเอาค่า 12 ใส่ไปที่ Dead Zone

รอบถัดไปให้ deleteMin นำค่า 94 เขียนไปที่ Tape 2 และอ่านค่า 35 เข้ามา เนื่องจาก 35 < 94 ดังนั้นเราจะใส่เข้าไปใน Heap ไม่ได้และต้องไปวางไว้ที่ Dead Zone แทน ดังนี้

รอบถัดไปเรา deleteMin และนำค่า 96 ไปไว้ที่ Tape 2 และอ่านค่า 17 เข้ามา แต่เนื่องจากค่า 17 < 96 ดังนั้นเราไม่สามารถนำค่า 17 ใส่เข้าไปใน Heap ได้ เมื่อเราลดขนาด Heap ลงอีก 1 แล้ว เราจึงนำค่า 17 ใส่ไว้ที่ Dead Zone จะได้ภาพดังต่อไปนี้

เมื่อทำมาถึงขั้นนี้จะพบว่า Heap เราเหลือขนาดเป็น 0 และมีแต่พื้นที่ Dead Zone เต็มทั้ง Heap ถือว่าเสร็จสิ้นการสร้าง Run ที่ 1 และปรับ Dead Zone ให้กลายเป็น Heap ตัวใหม่ ดังนี้

เริ่มต้นรอบถัดมา เราจะ deleteMin ได้ค่า 12 ใส่เข้าไปที่ Tape 3 และอ่านค่า 99 เข้ามา เนื่องจาก 99 > 12 ดังนั้น ค่า 99

สามารถใส่เข้าไปใน Heap ได้ เมื่อปรับ Heap แล้วจะได้ผลลัพธ์เป็นดังนี้

รอบถัดมาเรา deleteMin ได้ค่าเป็น 17 นำไปใส่ไว้ที่ Tape 3 และอ่านค่า 28 เข้ามา เนื่องจาก 28 > 17 ดังนั้นสามารถใส่เข้ามาใน Heap ได้ และจะได้ผลลัพธ์ดังนี้

รอบถัดมาเรา deleteMin ได้ค่า 35 ออกมาและเขียนไปที่ Tape 3 หลังจากนั้นอ่านค่า 28 เค้ามา เนื่องจาก 28 < 35 ดังนั้นเราใส่เข้าไปใน Heap จะได้ภาพดังนี้

รอบถัดมาเรา deleteMin ได้ค่า 35 และนำไปเขียนใส่ Tape 3 และอ่านค่า 41 เข้ามาเนื่องจาก 41 > 35 ดังนั้น เราสามารถใส่เข้าไปใน Heap ได้ จะได้ภาพดังนี้

รอบถัดมาเรา deleteMin ได้ค่า 41 และนำไปเขียนใส่ Tape 3 และอ่านค่า 75 เข้ามา เนื่องจาก 75 > 41 ดังนั้น เราสามารถใส่เข้าไปใน Heap ได้ จะได้ภาพดังนี้

รอบถัดมาเรา deleteMin ได้ค่า 58 และนำไปเขียนใส่ Tape 3 และอ่านค่า 15 เข้ามา เนื่องจาก 15 < 58 ดังนั้นเราไม่สามารถใส่ค่า 15 เข้าไปใน Heap ได้ เราต้องลดขนาด Heap ลง 1ช่อง และนำค่า 15 ไปใส่ที่ Dead Zone จะได้ผลลัพธ์ดังนี้

เมื่อเสร็จรอบนี้แล้วเราถือว่าได้อ่านอินพุตมาจนครบหมดทุกรายการแล้ว ดังนั้นที่ทำต่อเพียงแค่ deleteMin ออกจาก Heap และเขียนใส่ไปที่ Tape 3 ทีละตัวจนหมด Heap ดังนี้

เสร็จแล้วเราจะได้ Run ที่ 2 ดังนี้

สำหรับ 15 ที่เหลืออยู่ที่ Dead Zone เราทำแบบเดียวกันคือ นำมาสร้าง Heap ใหม่ และใส่เข้าไปที่ Tape 2 เป็น Run ที่ 3 ดังนี้

ด้วยวิธีการนี้ ถ้าเราสร้าง Run ครั้งแรกด้วยวิธีการ Replacement Selection จะทำให้เราได้ Run 3 รัน แต่ถ้าสร้างด้วยวิธี Simple เราจะได้ Run ถึง 5 Run ซึ่งทำให้เราต้อง Merge ด้วยจำนวนครั้งมากกว่า

จากภาพที่เห็นถ้าเราใช้วิธีการ Polyphase Merge เราจะใช้อีก 2 Pass ดังนี้

เปรียบเทียบกับวิธีการแบ่งแบบ Internal Sort ธรรมดา การใช้ Replacement Selection ทำให้ลดจำนวน Pass จาก 4 เหลือเพียงแค่ 3 Pass ก็สามารถจัดเรียงได้