Google         youtube            psv            สพม.11

การเรียงลำดับและผสานแฟ้มข้อมูล

การ เรียงลำดับแบ่งออกเป็นการจัดเรียงภายในดังที่ได้กล่าวผ่านมาเป็นการจัดเรียง ภายในหน่วยความจำหลัก และการจัดเรียงภายนอกซึ่งกล่าวถึงในที่นี้เป็นการจัดเรียงที่ใช้หน่วยความจำ สำรองเพื่อจัดเรียงลำดับแฟ้มข้อมูลแบบลำดับ (Sequential File) แฟ้มรายงาน และนำไปใช้ในการปรับปรุงแฟ้มข้อมูล เพื่อพิจารณาจากแฟ้มข้อมูลมี 2,000 เรคคอร์ด เพื่อทำการจัดเรียงลำดับและมีเพียง 1,000 เรคคอร์ดที่สามารถใช้งานในหน่วยความจำแต่ละช่วงเวลา จึงไม่สามารถจัดเรียงลำดับพร้อมกันหมด แนวทางการแก้ปัญหาโดยใช้การจัดเรียงลำดับภายในทำการเรียงลำดับ 2 รายการย่อย (Sublist) ที่คัดลอกมาจากแฟ้มข้อมูล คือ เรคคอร์ด 1-1,000 กับ 1,000-2,000 ผลที่ได้คือ แฟ้มข้อมูลที่เก็บรายการย่อย 2 แฟ้ม และนำมาผสาน (Merge) รวมเป็นแฟ้มเดียวที่จัดเรียงลำดับเรคคอร์ดทั้งหมด ดังในรูปที่ 11.19 การผสานจะทำการเปรียบเทียบระหว่างค่าของคีย์ใน 2 รายการย่อย ถ้าค่าใดน้อยกว่าก็เขียนเก็บไว้ในแฟ้มข้อมูลผสาน (Merge File)

รายการย่อย 1
(เรคคอร์ด 1-1000)
กล่องข้อความ: ผสาน

                                  รายการผสาน
(เรคคอร์ด 1-2000)                                                                      รายการย่อย 1
(เรคคอร์ด 1-1000)

รูปที่ 11.19  การผสานรายการย่อยได้เป็นแฟ้มข้อมูลที่มีการจัดเรียงลำดับข้อมูล

ตรรกะ พื้นฐานการผสานจะมี key , key2 และ keyM ใช้อ้างถึงค่าของคีย์ในรายการย่อย 1  รายการย่อย 2  ที่เป็นแฟ้มอินพุต และแฟ้มข้อมูลผสานที่เป็นแฟ้มเอ้าท์พุตตามลำดับรายการย่อยจะถูกจัดเรียง ลำดับตามค่าของคีย์เพื่อใช้ในการผสานและอาจมีความยาวไม่เท่ากัน เมื่อรายการย่อยใดถึงจุดสิ้นสุดแฟ้ม รายการย่อยอื่นที่ยังมีเรคคอร์ดเหลืออยู่ที่จะถูก

ตารางที่ 11.20  อัลกอริทึมการผสานแฟ้มข้อมูล

  1. เปิดแฟ้มข้อมูล File1 กับ File2  เป็นแฟ้มอินพุต และเปิดแฟ้มข้อมูล File3 เป็นแฟ้มเอ้าท์พุต
  2. ให้ตัวแปร X อ่านค่าแรกในแฟ้มข้อมูล File1 และตัวแปร Y อ่านค่าแรกในแฟ้มข้อมูล File2
  3. ทำซ้ำแบบเดิมจนกว่าถึงท้ายแฟ้มข้อมูล File1 หรือ File2
    1. ถ้าค่า X-Y ให้ทำ

a.1  เขียนค่า X เก็บไว้ที่แฟ้มข้อมูล File3
a.2  ให้ตัวแปร X อ่านค่าตัวถัดไปในแฟ้มข้อมูล File1
ไม่เช่นนั้น
b.1  เขียนค่า Y เก็บไว้ที่แฟ้มข้อมูล File3
b.2  ให้ตัวแปร Y อ่านค่าตัวถัดไปในแฟ้มข้อมูล File2

  1. ถ้า พบท้ายแฟ้มข้อมูล File1 คัดลอกค่าที่เหลือทั้งหมดจากแฟ้มข้อมูล File2 ให้กับแฟ้มข้อมูล File3 แต่ถ้าพบท้ายแฟ้มข้อมูล File2 คัดลอกค่าที่เหลือทั้งหมดจากแฟ้มข้อมูล File1 ให้กับแฟ้มข้อมูล File3

การจัดเรียงลำดับและผสานแฟ้มข้อมูลแบ่งออกเป็น 3 ขั้นตอน คือ

  1. ขั้น ตอนการจัดเรียงลำดับภายใน เป็นการจัดเรียงลำดับค่าของเรคคอร์ดที่เก็บไว้ในแต่ละแฟ้มอินพุตที่ถูกแบ่ง ออกเป็นกลุ่มและมีจำนวนเรคคอร์ดเท่ากับเรียกว่ารัน (Run) ซึ่งจะกระจายรันเหล่านี้เก็บไว้ในแฟ้มอินพุตบนอุปกรณ์จัดเก็บข้อมูลตั้งแต่ สองตัวขึ้นไป เช่น เทปแม่เหล็กหรือฮาร์ดดิสก์
  2. ขั้นตอนการผสาน เป็นการรวมค่าที่อยู่ในแต่ละรันจากหลายๆ แฟ้มอินพุตให้จัดเรียงตามลำดับ และนำมารวมไว้ด้วยกันได้เป็นหนึ่งรันในแฟ้มเอาท์พุตสำหรับใช้งานในรอบ (Phase) ถัดไป
  3. ขั้นตอนผลลัพธ์ที่ได้  เป็นการคัดลอกแฟ้มข้อมูลที่จัดเรียงลำดับเสร็จแล้วเก็บไว้บนสื่อจัดเก็บข้อมูลตามที่ต้องการ

โดย ทั่วไป การนำอัลกอลิทึมมาใช้สำหรับขั้นตอนการจัดเรียงลำดับภายในคือการจัดเรียงแบบ ทัวร์นาเม้นต์ (Tourmament Sort) เนื่องจากใช้กับรันที่มีความยาวมากกว่าหน่วยความจำหลักที่ไม่สามารถเก็บได้ หมด สำหรับเทคนิคการจัดเรียงลำดับแฟ้มข้อมูลหรือการจัดเรียงลำดับภายนอกเกือบ ทั้งหมดใช้วิธีตามขั้นตอนดังกล่าว จึงเรียกว่า การจัดเรียงลำดับและผสาน (Sort/Merges) และมีขั้นตอนการผสานหลายวิธีในการจัดเรียงลำดับและผสาน
ในการผสานแฟ้มข้อมูลที่เป็นอินพุตเข้ามา 2 แฟ้มในแต่ละครั้งเรียกว่าการผสาน2-ทาง (2-way Merge) ดังนั้น ถ้ามีแฟ้มอินพุต M แฟ้มจะเรียกว่าการผสาน M-ทาง (M-way Merge) โดยการผสานธรรมดา M-ทาง (M-way Merge) จะเป็นการผสานที่มีแฟ้มอินพุต M แฟ้มกับแฟ้มเอ้าท์พุตเพียง 1 แฟ้ม มีลักษณะเช่นเดียวกับการเรียงลำดับ แบบผสานที่ผ่านมาแทนที่ใช้อาร์เรย์เก็บค่าแต่จะใช้แฟ้มข้อมูลเก็บค่าแทน แต่การผสานธรรมดา ต้องใช้การทำงานของ I/O เกือบครึ่งหนึ่งของทั้งหมดในการกระจายรันที่ได้จากการผสานในแต่ละรอบให้กับ หลายแฟ้มข้อมูลเพื่อเตรียมเป็นแฟ้มอินพุตในรอบถัดไป ความต้องการคัดลอกข้อมูลกลับไปกลับมา โดยกระจายผลลัพธ์ที่ได้จากการผสานส่งตรงไปให้แฟ้มข้อมูลที่จะเป็นแฟ้มอินพุต ในรอบถัดไป ดังนั้น การผสานสมดุล M-ทางจะใช้ 2M แฟ้ม ในลักษณะการย้ายข้อมูลกลับไปกลับมาระหว่างแฟ้มอินพุตและเอ้าท์พุตที่มีจำนวน เท่ากัน

ตัวอย่างการเรียงลำดับและผสานสมดุล 
ตัวอย่างที่นำมาใช้จัดเรียงลำดับภายนอกจะใช้แฟ้มข้อมูลที่สมมุติให้มี 36 เรคคอร์ด โดยนำเฉพาะค่าของคีย์มาใช้แสดงและใช้วิธีการผสานสมดุล 2-ทาง โดยมีการจัดเรียงลำดับภายในได้ 3 เรคคอร์ดต่อหนึ่งรัน ดังนั้น ในการเรียงลำดับและผสานสมดุลจึงใช้เครื่องอ่านเทป 4 ตัว ซึ่งมีเทป 2 ม้วนเป็นแฟ้มอินพุตและอีก 2 ม้วนเป็นแฟ้มเอ้าท์พุต มีขั้นตอน ดังต่อไปนี้
1. ขั้นตอนการเรียงลำดับภายในเป็นการเรียงลำดับค่าในเทป 1 เก็บไว้ในแต่ละวันแบ่งเป็น 12 วัน ๆ ละ 3 เรคคอร์ดและกระจายเก็บไว้ในแฟ้มอินพุตคือเทป3, 4 สลับกันไป

2.  ขั้นตอนการผสานรอบที่ 1  โดยนำค่าในแต่ละรันจากแฟ้มอินพุต คือ เทป 3, 4 มาผสานรวมกันทีละคู่เก็บลงในแฟ้มเอ้าท์พุตคือ เทป 1, 2 สลับกัน จากเดิมที่มี 12 รันจะเหลือ 6 รัน ได้เป็นดังนี้

3.  ขั้นตอนการผสานรอบที่ 2  โดยนำค่าในแต่ละรันจากแฟ้มอินพุต คือ เทป 1, 2 มาผสานรวมกันทีละคู่เก็บลงในแฟ้มเอ้าท์พุต คือ เทป 3, 4 สลับกัน จากเดิมที่มี 6 รันจะเหลือ 3 รัน ได้เป็น ดังนี้

4.  ขั้นตอนการผสานรอบที่ 3 โดยนำค่าในแต่ละรันจากแฟ้มอินพุต คือ เทป 3, 4 มาผสานรวมกัน ซึ่งมีคู่เดียวเก็บลงในแฟ้มเอ้าท์พุต คือ เทป 1 จากเดิมที่มี 3 รันจะเหลือ 2 รัน โดยในเทป 1 มี 1 รัน และเทป 3 มี 1 รันที่ยังไม่ถูกผสาน ซึ่งเทป 2 ไม่ถูกนำมาใช้งาน ได้เป็นดังนี้

5.  ขั้นตอนการผสานรอบที่ 4 โดยนำค่าในแต่ละรันจากแฟ้มอินพุต คือ เทป 1, 3 มาผสานรวมกัน ซึ่งมีคู่เดียวเก็บลงในแฟ้มเอ้าท์พุต คือ เทป 4 จากเดิมที่มี 2 รันจะเหลือ 1 รัน โดยในเทป 1 มี 1 รัน เรียงตามลำดับค่าทั้งหมด โดยเทป 2 ยังคงไม่ถูกนำมาใช้งาน ได้เป็นดังนี้

ใน การผสานแต่ละรอบรันทั้งหมดจะถูกหารด้วยจำนวนแฟ้มอินพุตในการผสาน ทำให้แต่ละรันมีความยาวเป็นเท่าของจำนวนแฟ้มอินพุตและจำนวนรันน้อยลงครึ่ง หนึ่งของรัน ในเทปอินพุต ดังนั้น การผสานสมดุล M-ทาง ต้องใช้จำนวนรอบในการผสานเท่ากับ O([logM R/L]) เมื่อ R คือ จำนวนเรคคอร์ดและ L คือ ความยาวของรันในตอนเริ่มต้น เช่น ในตัวอย่างจำนวนรอบเท่ากับ élog2 36/3ù = 4 ถ้าให้ M หรือจำนวนแฟ้มอินพุตเท่ากับ 3 จะใช้จำนวนรอบเพียง élog3 36/3ù = 3 รอบ

แต่ เนื่องจากการทำงานของการผสานสมดุลทำให้แฟ้มเอ้าท์พุตบางแฟ้มอยู่เฉยๆ ไม่ถูกใช้งาน (เทป 2)  และเพื่อลดาจำนวนการคัดลอกค่าระหว่างแฟ้มอินพุตกับแฟ้มเอ้าท์พุต จึงใช้การผสานที่มี
มากกว่า M คือ ให้การอ่านแฟ้มข้อมูลมีมากกว่า M แฟ้มในช่วงเวลาหนึ่งก็จะได้ 2M-1 แฟ้มอินพุตและ 1 แฟ้มเอ้าท์พุต หรือนำแฟ้มเอ้าท์พุตของการผสานสมดุลที่ไม่ได้ใช้งานในการใช้มาเป็นแฟ้ม อินพุตแทน ซึ่งได้เป็นการผสานไม่สมดุล (Unbalanced Merge) เกิดประโยชน์สูงสุดในการใช้แฟ้มข้อมูล โดยรูปแบบหนึ่งของการผสานไม่สมดุลที่นำมาใช้ คือ การผสานหลายขั้นตอน (Polyphone Merge) ซึ่งใช้แฟ้มอินพุตจำนวนคงที่ และการผสานหลายเฟส M-ทาง ก็จะใช้ 2M – 1 แฟ้มอินพุต

ตัวอย่างการเรียงลำดับและผสานหลายขั้นตอน 
สำหรับตัวอย่างนี้เป็นการผสานหลายขั้นตอน 2 – ทาง จึงใช้เทป 3 ม้วนเป็นแฟ้มอินพุตและ 1 ม้วนเป็นแฟ้มเอ้าท์พุตในแต่ละรอบ โดยสมมุติให้แฟ้มข้อมูลมี 34 เรคคอร์ดและการจัดเรียงลำดับภายในได้ 2 เรคคอร์ดต่อหนึ่งรัน ก็จะได้ทั้งหมด 17 รันและกระจายไปยัง 3 แฟ้มอินพุต โดยแฟ้ม 1 ได้ 7 วัน แฟ้ม 2 ได้ 6 รัน แฟ้ม 3 ได้ 4 รัน ซึ่งวิธีการกระจายรันดังในรูปที่ 11.20

รูปที่ 11.20  วิธีการกระจายรันไปให้พร้อมอินพุตในการผสานหลายขั้นตอน

                1. ขั้นตอนการเรียงลำดับภายในเป็นการเรียงลำดับค่าในเทป 1 เก็บไว้ในแต่ละวันแบ่งเป็น 17 รันๆ ละ 2 เรคคอร์ดและกระจายรันตามวิธีที่กล่าวมาเก็บไว้ในแฟ้มอินพุต คือ เทป 2 ได้ 7 รัน เทป 3 ได้ 6 รัน และเทป 4 ได้ 4 วัน และเทป 4 ได้ 4 รัน ได้เป็น ดังนี้

2.  ขั้นตอนการผสานรอบที่ 1  โดยนำค่าในแต่ละรันจากแฟ้มอินพุต คือ เทป 2, 3, 4 มาผสานรวมกัน (การผสานที่มีแฟ้มอินพุตมากกว่า 2 ม้วน ในการรัดเรียงลำดับโดยใช้การเปรียบเทียบค่ากันอาจไม่เหมาะสม จึงเปล่ามาใช้คิวลำดับความสำคัญแทน และให้ค่าที่น้อยกว่ามีความสำคัญมากกว่า) และเก็บลงในแฟ้มเอ้าท์พุต คือ เทป 1 โดยเทป 2 เหลือ 3 รันและเทป 3 เหลือ 2 รัน จากเดิมที่มี 17 รันจะเหลือ 9 รันได้เป็นดังนี้

                3.  ขั้นตอนการผสานรอบที่ 2  โดยนำค่าในแต่ละรันจากแฟ้มอินพุต คือ เทป 1, 2, 3  มาผสานรวมกันและเก็บลงในแฟ้มเอ้าท์พุต คือ เทป 4 โดยเทป 1 เหลือ 2 รันและเทป 2 เหลือ 1 รัน จากเดิมที่มี 9 รันจะเหลือ 5 รันได้เป็นดังนี้

4.  ขั้นตอนการผสานรอบที่ 3 โดยนำค่าในแต่ละรันจากแฟ้มอินพุต คือ เทป 1, 2, 4  มาผสานรวมกันและเก็บลงในแฟ้มเอ้าท์พุต คือ เทป 3 โดยเทป 1, 3, 4 เหลือม้วนละ  1 รัน จากเดิมที่มี 5 รันจะเหลือ 3 รันได้เป็นดังนี้

5. ขั้นตอนการผสานรอบที่ 4 โดยนำค่าในแต่ละรันจากแฟ้มอินพุต คือ เทป 1, 3, 4 มาผสานรวมกันและเก็บลงในแฟ้มเอ้าท์พุต คือ เทป 2  จากเดิมที่มี 3 รันจะเหลือ 1 รันที่เรียงตามลำดับค่าทั้งหมด ได้เป็นดังนี้

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

เริ่มรอบ 1

จบรอบ 1

จบรอบ 2

จบรอบ 2

จบรอบ 3

วันเริ่มต้น

เทป 2+3+4

เทป 1+2+3

เทป 1+2+4

เทป 1+3+4

เทป 1

0

4

2

1

0

เทป 2

7

3

1

0

1

เทป 3

6

2

0

1

0

เทป 4

4

0

2

1

0

รวม

17

9

5

3

1

จาก ตัวอย่างมีลักษณะของขั้นตอนการผสานรวมกันในช่วงการผสานแต่ละรอบดังในรูปที่ 11.21 แสดงให้เห็นถึงลำดับการกระจายรันในช่วงขั้นตอนการจัดเรียงลำดับภายในให้กับ แฟ้มอินพุต ซึ่งผลรวมที่ได้ในรูปที่ 11.21 อยู่ในรูปแบบของตัวเลข Fibonacci และเป็นวิธีที่ดีที่สุดเพื่อใช้ในการกระจายรั

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s