Google         youtube            psv            สพม.11

อาร์เรย์ในหน่วยความจำ

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

  1. การเข้าถึงเรียกใช้สมาชิกต้องมีความเรียบง่าย
  2. ง่ายต่อการเข้าไปหาแต่ละสมาชิกที่มีหลายเส้นทาง
  3. ประสิทธิภาพของการจัดเก็บที่ง่ายต่อการเข้าถึงแต่ละสมาชิก
  4. ง่ายต่อการเพิ่มขนาดอาร์เรย์ให้มากขึ้น

การเก็บอาร์เรย์หนึ่งมิติในหน่วยความจำ

เมื่อ พิจารณาพื้นที่ในหน่วยความจำที่จะเก็บอาร์เรย์หนึ่งมิติ เช่น อาร์เรย์ A ในรูปที่ 2.1 ซึ่งมีดัชนีที่ขอบเขตล่างเท่ากับ 1 ส่วนขอบเขตบนเท่ากับ N วิธีที่จะเก็บอาร์เรย์หนึ่งมิติในหน่วยความจำก็คือ ลำดับของสมาชิกในทางกายภาพ เรียงเป็นแบบเดียวกับลำดับของสมาชิกในทางตรรกะ ดังนั้น พื้นที่จัดเก็บสมาชิก A(I+1) จะอยู่ต่อเนื่องจากพื้นที่ จัดเก็บสมาชิก A(I) สำหรับ

I = 1,…,N-1 ในการคำนวณหาแอดเดรสเริ่มต้นของสมาชิกA(I) จำเป็นต้องทราบในเรื่องต่อไปนี้

1. ตำแหน่งแอดเดรสเริ่มต้นของพื้นที่หน่วยความจำที่จะเก็บอาร์เรย์ เรียกว่าตำแหน่งเริ่มต้น (Base Location)

2. ขนาดพื้นที่เก็บแต่ละสมาชิกของอาร์เรย์ กำหนดให้มีขนาด S ไบต์

การหาตำแหน่งแอดเดรสของสมาชิกอาร์เรย์ A ตัวที่ I จะได้ ดังนี้

B + (I – 1)*S

หรือกรณีที่ใช้ขอบเขตล่าง L เป็นดังนี้

B + (I – L)*S

เช่น มีอาร์เรย์A(4:10) และต้องการหาตำแหน่งแอดเดรสของสมาชิก Ves(6) โดยตำแหน่งเริ่มต้นอยู่ที่แอดเดรส 2500 และแต่ละสมาชิกมีขนาด 80 ไบต์ ก็จะได้ตำแหน่งแอดเดรสอยู่ที่ 250 + (6 – 4) * 80 = 2660

การเก็บอาร์เรย์หลายมิติในหน่วยความจำ

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

ลำดับแถวสำคัญ   (Row-Major Order) ทางเลือกหนึ่งที่นำมาใช้คือเก็บสมาชิกทุกตัวของแถวแรกก่อน จากนั้นเก็บแถวที่สอง และสามไปเรื่อย ๆ ดังในรูปที่ 2.4 คือ อาร์เรย์ Mem(1:4,1:6) ซึ่งมีลักษณะรูปแบบตารางในทางตรรกะ

1

2

3

4

5

6

1

1,1

1,2

1,3

1,4

1,5

1,6

2

2,1

2,2

2,3

2,4

2,5

2,6

3

3,1

3,2

3,3

3,4

3,5

3,6

4

4,1

4,2

4,3

4,4

4,5

4,6

รูปที่ 2.4 อาร์เรย์ Mem (4,6) แสดงเป็นตารางในทางตรรกะ

เมื่อนำไปเก็บไว้ในหน่วยความจำซึ่งมีลักษณะเชิงเส้น ลักษณะอาร์เรย์ทางกายภาพก็จะเป็นเชิงเส้นเหมือนกัน ดังในรูปที่ 2.5

แถว ที่ 1                                        แถวที่ 2                                          แถวที่ 3                                   แถวที่ 4

1,1 1,2 1,3 1,4 1,4 1,6 2,1 2,2 2,3 2,4 2,5 2,6 3,1 3,2 3,3 3,4 3,5 3,6 4,1 4,2 4,3 4,4 4,5 4,6

รูปที่ 2.5 ลักษณะอาร์เรย์ Mem (1:4,1:6) ในลักษณะแบบลำดับแถวสำคัญ

แบบ แผนการจัดเก็บแบบลำดับแถวสำคัญนำมาใช้กับอาร์เรย์ในภาษาเขียนโปรแกรมหลาย ภาษา เช่น ภาษาโคบอล  ภาษาปาสคาล และภาษาซี ถ้าต้องการทราบแอดเดรสเริ่มต้นของแต่ละสมาชิกในอาร์เรย์สองมิติจะมีวิธีการ คำนวณ เช่นหาแอดเดรสเริ่มต้นของสมาชิก Mem(I,J) ในอาร์เรย์ Mem(L1:U1,L2:U2) จะได้ดังนี้

B + (I – L1) * (U2 – L2 + 1) *S + (J – L2) *S

สมมุติ ต้องการทราบแอดเดรสสมาชิก Mem(2,5) โดยตำแหน่งเริ่มต้นอาร์เรย์คือแอดเดรส 1000 และแต่ละสมาชิกในอาร์เรย์มีขนาด 8 ไบต์ ก็จะได้ 1000+(2-1)*(6-1+1)*8+(5-1)*8 = 1080

ลำดับคอลัมน์สำคัญ (Column – Major Order) เป็นอีกทางเลือกหนึ่งที่เก็บสมาชิกอาร์เรย์ในแนวเชิงเส้นโดยเก็บสมาชิกทุก ตัวของคอลัมน์แรกก่อน จากนั้นเก็บคอลัมน์ที่สองและสามไปเรื่อย ๆ อาร์เรย์ Mem ในรูปที่ 2.4 เมื่อเก็บไว้ในหน่วยความจำแบบเชิงเส้นได้เป็นในรูปที่ 2.6

คอลัมน์ ที่ 1                                 คอลัมน์ที่2                                 คอลัมน์ที่ 3                                     คอลัมน์ที่ 4

1,1 1,2 1,3 1,4 1,5 1,6 2,1 2,2 2,3 2,4 2,5 2,6 3,1 3,2 3,3 3,4 3,5 3,6 4,1 4,2 4,3 4,4 4,5 4,6

รูปที่ 2.6 ลักษณะอาร์เรย์ Men(4,6) ในลักษณะแบบลำดับคอลัมน์สำคัญ

แบบแผนการจัดเก็บแบบลำดับคอลัมน์สำคัญมีการใช้ภาษาเขียนโปรแกรม  เช่น

ภาษาฟอร์แทรน ถ้าต้องการทราบแอดเดรสเริ่มต้นของแต่ละสมาชิกในอาร์เรย์สองมอตอจะมีวิธี การคำนวณหาของสมาชิก Men(I,J) จะได้ดังนี้

B + (J – L2) * (U1 – L1 + 1) *S + (I – L1) *S

ถ้าต้องการทราบแอดเดรสสมาชิก Men(2,5) แบบลำดับคอลัมน์ก็จะได้ 1000+(5-1)*(4-1+1)*8+(2-1)*8 = 1136

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