Pemetaan Array Ke Storage
PEMETAAN ARRAY DIMENSI SATU KE STORAGE
Seperti halnya struktur data yang lain, ada beberapa cara untuk menyajikan array di dalam memori. Skema penyajian dapat dievaluasi berdasarkan 4 karakteristik, yakni :
1. kesederhanaan dari akses elemen
2. mudah untuk ditelusuri
3. efisiensi dari utilitasi storage
4. mudah dikembangkan
2. mudah untuk ditelusuri
3. efisiensi dari utilitasi storage
4. mudah dikembangkan
Umumnya tidaklah mungkin untuk mengoptimalkan keempat faktor tersebut sekaligus. Pandang array satu dimensi NOPEG dengan batas bawah subscript 1, dan batas atas subscript = N. Salah satu cara untuk menyimpan array ini adalah
sedemikian sehingga urutan fisik dari elemen sama dengan urutan logik
dari elemen. Storage untuk elemen NOPEG(I+1) adalah berdampingan dengan
storage untuk elemen NOPEG(I), untuk setiap I = 1, 2, 3,…, N-1. Untuk
menghitung alamat (address) awal dari elemen NOPEG(I), diperlukan untuk
mengetahui 2 hal yakni :
1. address awal dari ruang storage yang dialokasikan bagi array tersebut.
2. ukuran dari masing-masing elemen array.
1. address awal dari ruang storage yang dialokasikan bagi array tersebut.
2. ukuran dari masing-masing elemen array.
Address awal dari array, kita nyatakan dengan B, disebut juga base-location. Misalkan bahwa masing-masing elemen dari array menduduki S byte.
Maka, address awal dari elemen ke-I adalah :
B + (I-1) * S
B + (I-1) * S
Sekarang kita perluas persamaan di atas untuk mendapat address dari elemen ke-I dari array yang mempunyai batas bawah subscript tidak sama dengan 1. Perhatikan array Z(4:10), maka address awal dari Z(6) adalah :
B + (64) * S
Untuk array Z2 (-2:2) misalnya, address awal dari Z2(l) adalah :
B + (I -(-2)) * S
B + (I -(-2)) * S
Maka secara umum, untuk array :
ARRAY(L:U), elemen ARRAY(I) mempunyai address awal B + (U-L) * S
ARRAY(L:U), elemen ARRAY(I) mempunyai address awal B + (U-L) * S
PEMETAAN KE STORAGE TERHADAP ARRAY DIMENSI BANYAK
Karena memori komputer adalah linear, maka array dimensi banyak harus dilinearkan apabila akan dipetakan ke dalam storage. Salah satu alternatif untuk
pelinearan tersebut adalah menyimpan pertama kali baris pertama dari
array, kemudian baris ke-2, baris ke-3 dan seterusnya. Ini disebut row
major order.
Misalkan B adalah base-location dari array RATE tersebut, dan masing-masing elemen dari array berukuran S. Address awal dari elemen RATE(I,J) adalah :
B + (I-1) * 6 * S + (J-1) * S
karena ada I-1 baris, masing-masing dengan panjang 6 * S, sebelum baris elemen RATE(I,J) terletak, dan terdapat J- 1 elemen, masing-masing dengan panjang S sebelum elemen RATE(I,J) pada baris ke-I. Jadi, pada contoh di atas RATE(2,4) mempunyai address awal :
B+ (2-1) * 6 * S + (4-1) * S = B + 9 * S
Secara umum elemen ARRAY(I,J) dari array yang didefinisikan sebagai ARRAY(L1:U1, L2 : U2) mempunyai address awal :
B + (I-L1) * (U2 -L2+ 1) * S + (J-L2) * S
Terdapat 2 baris (I-L1, 0 – (-2)) sebelum baris nol, yang masing-masing panjangnya 3*S(U2-L2+1 = 6-4+1) dan terdapat 2 elemen (J-L2 = 6-4) pada baris ke nol
sebelum elemen Z (0,6). Jadi address awal dari Z(0,6) adalah :
B + 2 * 3 * S + 2 * S = B + 8 * S
Alternatif lain untuk melinearkan array dimensi dua adalah dengan menyimpan elemen dalam column major order, yakni pertama kali menyimpan kolom pertama, lalu kolom kedua, kolom ketiga dan seterusnya. Dengan mudah dapat diterangkan bahwa pada array RATE di atas, elemen RATE(I,J) mempunyai address awal B + (J – 1) * 4 * S + (I – 1) * S, sehingga RATE(2,4) akan mempunyai address awal B + (4-1) * 4 * S + (2-1) * S = B + 13 * S. Jadi kita harus waspada andaikata kita mempunyai array yang ditulis dalam rutin FORTRAN, kemudian
akan kita tulis dalam bahasa lain (COBOL, PL/1 atau Pascal). Secara umum, elemen ARRAY(I,J) dari array yang didefinisikan sebagai ARRAY(L1:U1,L2 :U2), menggunakan
address awal :
akan kita tulis dalam bahasa lain (COBOL, PL/1 atau Pascal). Secara umum, elemen ARRAY(I,J) dari array yang didefinisikan sebagai ARRAY(L1:U1,L2 :U2), menggunakan
address awal :
B + (J-L2) * (U1-L1 +1) * S + (I-L1) * S
Misalkan array A berorder 50 x 225. Hendak dihitung jumlah / total elemennya. Kalau dipergunakan column-major storage, dapat kita buat, dalam COBOL.
COMPUTE TOTAL = 0.
PERFORM SUM-UP VARYING J
FROM 1 BY 1 UNTIL J > 225
AFTER 1 FROM 1 BY 1 UNTIL I > 50.
COMPUTE TOTAL = 0.
PERFORM SUM-UP VARYING J
FROM 1 BY 1 UNTIL J > 225
AFTER 1 FROM 1 BY 1 UNTIL I > 50.
dalam hal ini
SUM-UP.
TOTAL = TOTAL + A(I,J).
SUM-UP.
TOTAL = TOTAL + A(I,J).
Dalam Pascal dapat kita tulis :
Total := 0;
for j = 1 to 225 do
for i = 1 to 50 do
total := total + a[I,j];
Total := 0;
for j = 1 to 225 do
for i = 1 to 50 do
total := total + a[I,j];
Kalau dipergunakan row-major storage, kita dapat tulis dalam COBOL sebagai berikut :
COMPUTE TOTAL = 0.
PERFORM SUM-UP VARYING 1
FROM 1 BY 1 UNTIL I > 50
AFTER J FROM 1 BY 1 UNTIL J > 225
COMPUTE TOTAL = 0.
PERFORM SUM-UP VARYING 1
FROM 1 BY 1 UNTIL I > 50
AFTER J FROM 1 BY 1 UNTIL J > 225
dalam hal ini
SUM-UP.
TOTAL = TOTAL + A(I,J).
SUM-UP.
TOTAL = TOTAL + A(I,J).
dan dalam Pascal dapat ditulis
total:=0;
for i := 1 to 50 do
for j := 1 to 225 do
total := total + a[i,j];
total:=0;
for i := 1 to 50 do
for j := 1 to 225 do
total := total + a[i,j];
Posting Komentar