Konsep Pemetaan Array Ke Storage

Pemetaan Array Ke Storage

Pemetaan Array Ke Storage - Sama juga seperti halnya struktur data yang lain, dimana ada beberapa cara dalam menyampaikan array di dalam memori (storage). Untuk itu mari simak  penyajian yang dievaluasi berdasarkan 4 kategori, yaitu :

1. kesederhanaan dari akses elemen itu sendiri
2. mudah dalam menelusuri dan mencari
3. efisiensi dari utilitasi storage
4. mudah untuk di sebarluaskan

Diperlukan sebuah Keterampilan

Ketika bahasa yang primitif bagi programmer yang paling tahu tentang array di dalam storage terdengar dengan Fungsi Pemetaan akademis atau disebut juga dengan SMFs.

Fungsi pemetaan array ke srorage hanyalah sebuah fungsi yang memberikan lokasi dimana memori disimpan. Maka SMF merupakan F fungsi yang mengambil kunci yaitu sesuatu data yang menentukan dimana yang Anda inginkan dan juga mengembalikan lokasi data:

locationOfData = F (kunci);

Sifat dari fungsi pemetaan array ke storage dapat berubah sesuai dengan jenis kunci yang digunakan. Tentu saja dengan jenis penyimpanan yang digunakan itu sendiri.

Fungsi pemetaan array ke storage diciptakan ketika programmer yang pertama itu diperlukan untuk melaksanakan array satu dimensi.

Untuk contohnya, sebuah array dari dua bilangan bulat byte dapat diimplementasikan dengan menggunakan SMF sederhana:

Lokasi = dasar + 2 * Indeks

di mana dasarnya adalah alamat pertama dari sebuah array.
Hal ini bertugas hanya karena elemen pertama array disimpan di dasar, berikutnya adalah di dasar + 2, dan selanjutnya di dasar + 4 lalu secara umum dapat di simpulkan elemen-i disimpan di dasar + 2 * i.

Secara umum array satu dimensi yang terdiri dari unsur-unsur yang masing-masing menempati b byte dapat diimplementasikan menggunakan SMF:

Lokasi = dasar + b * Indeks

Nah, untuk menemukan lokasi dari [i], yaitu dengan memanggil array, yang harus Anda lakukan adalah bekerja di luar basis + b * i dan kemudian mengambil atau menyimpan nilai yang terkait dengan [i] yang ada.

Apabila elemen pertama array dianggap sebuah [0] maka harus di proses dengan i-1.

Lokasi = dasar + b * (indeks 1)

Array mulai dari indeks nol karena ia menghindari kurangi berantakan dari 1.

Jika bahasa C Anda mungkin hanya mengenali cara aritmetik pointer dimana yang bekerja dengan array hanya sebagai formalisasi array SMF.
(Baca : Queue serta contoh programnya)

2D

SMFs untuk array satu dimensi yang terlalu sederhana untuk dijadikan menarik tapi setidaknya mereka membuat contoh yang baik.
(Baca juga: Pengertian record dan contoh programnya)

Prinsip yang sama berlaku untuk array dua dimensi.

Sebuah array dua dimensi a [i, j] elemen b byte dengan dimensi n oleh m dapat diimplementasikan dengan menggunakan SMF yang:

Lokasi = dasar + b * i + b * n * j

Hal ini juga diasumsikan bahwa indeks array semua mulai dari 0, jika tidak maka hanya mengubah i ke i-1, dan j untuk-j 1.

Ide yang sama dapat diperluas di 2 dimensi. Akan tetapi ketika Anda mendapatkan ke array 2D bahwa makna dari SMF mulai menjadi jelas. Apa yang di lakukan untuk menemukan fungsi yang memetakan struktur data ke sistem penyimpanan linear. Dalam contoh array 2D Anda memiliki meja dan baris yang dipetakan ke storage linear satu demi satu:

Bitmap Dan Stride

Bitmap dan stride juga merupakan SMF dimana digunakan untuk memetakan data pixel ke dalam storage linear baik memori atau pun file. Jika bitmap disimpan dalam array dengab byte piksel nxm dan setiap pixel membutuhkan bytes bpp agar menyimpan pixel di x, y disimpan:

pixel = x * bpp + m * y * bpp

     = (x + m * y) * bpp


Komplikasi dalam kasus gambar bitmap tersebut ialah panjang berturut-turut dimana harus kelipatan empat atau beberapa nilai lainnya. Dalam hal ini panjang berturut-turut bukan hanya ukuran yang diberikan oleh dimensi bitmap. Ukuran penyimpanan fisik dari deretan gambar bitmap biasanya disebut sebagai "langkah". Membuat SMF berikut ini:

pixel = (x + langkahnya * y) * bpp

Terdapat banyak sekali kasus lain untuk memetakan struktur 2d ke garis dan SMF yang sama dimana digunakan dengan sedikit perubahan saja. Misalnya Anda memiliki sebuah kubus data n untuk m untuk p. Kemudian Anda akan menyimpan data tersebut dalam rangka baris dan menambahkan jumlah kolom dan juga jumlah halaman. Jadi, C [i, j, k] SMF adalah:

Lokasi = i + n * j + n * m * k

Jika dibutuhkan b bytes untuk menyimpan elemen maka di kalikan SMF oleh b.

N ini berarti jumlah elemen dalam satu baris sedangkan n * m adalah jumlah elemen dalam halaman.
(Baca juga: Stack pada struktur data)

Pemetaan kunci dan Pohon

Array dua dimensi dengan SMF sedikit lebih menarik karena menggunakan fungsi f (key) untuk mencari kunci data.

Dalam kasus array satu dimensi kunci data adalah indeks i dan lokasi dari [i] diberikan oleh f (i) dan dalam kasus dua dimensi kunci i dan j dan lokasi dari [ i, j] diberikan untuk f (i, j).

Nah untuk itu mari kita coba implementasi pohon biner sederhana.

Pohon biner adalah struktur pohon dimana adanya setiap node, terlepas dari node akhir atau pun terminal, memiliki dua anak maka disebutlah pohon biner.

Setiap node dikaitkan dengan nilai yang mengambil n byte untuk menyimpan, maka dari itu SMF yang sesuai itu adalah:

Lokasi = dasar + n * i + n * (2 ^-j 1)
 

Memberikan lokasi nilai yang disimpan tidak dengan simpul pada tingkat j. Itulah kita menggunakan i dan j untuk "index" pohon dengan simpul nomor i pada tingkat j.

contoh kecil dari pohon biner:

Perhatikan bahwa dari satu tingkat ke yang berikutnya yaitu menggandakan jumlah node dan Anda harus dapat membedakan bahwa jumlah node pada tingkat j hanya 2 ^ j.

Dengan ini, sekarang juga dapat melihat bagaimana SMF bekerja. Pohon ini disimpan sebagai garis node satu tingkat pada suatu waktu. Sebagai berikut :

Lokasi 0 1 2 3 4 5 6

node 0 | 0 1 | 0 1 2 3

level 0 | 1 | 2

Dalam memanfaatkan SMF ini untuk bahasa tingkat tinggi yang harus Anda lakukan adalah mendeklarasikan array dari elemen yang akan memegang nilai-nilai node lalu menggunakan SMF dengan n = 1 dimana bertujuana untuk menentukan elemen simpul i pada tingkat .

Sebagai contoh, jika array adalah [N] kemudian simpul i pada tingkat j disimpan dalam bentuk [i + 2 ^ j-1].

Jika Anda memiliki struktur data yang memiliki pola yang teratur maka Anda perlu dalam menemukan fungsi untuk memetakan pola teratur dalam urutan linear dari lokasi penyimpanan.
(Baca juga : Contoh program sederhana dari Array) 

Itulah pembahasan dari Konsep Pemetaan Array ke dalam Storage. Semoga bermanfaat, terima kasih telah berkunjung.

Tweet

Subscribe to receive free email updates: