Mengapa kita menggunakan array alih-alih struktur data lainnya?

Ketika saya sedang pemrograman, saya belum melihat contoh di mana array lebih baik untuk menyimpan informasi daripada bentuk lainnya. Saya memang menemukan "fitur" tambahan dalam bahasa pemrograman telah meningkat pada ini dan dengan itu menggantikannya. Saya melihat sekarang bahwa mereka tidak diganti tetapi lebih diberi kehidupan baru, sehingga untuk berbicara.

Jadi, pada dasarnya, apa gunanya menggunakan array?

Ini bukan alasan mengapa kita menggunakan array dari sudut pandang komputer, tetapi mengapa kita menggunakan array dari sudut pandang pemrograman (perbedaan yang halus). Apa yang dilakukan komputer dengan array bukanlah tujuan dari pertanyaan itu.

Saatnya kembali ke masa untuk pelajaran. Meskipun kita tidak terlalu memikirkan hal-hal ini dalam bahasa kita yang dikelola secara mewah saat ini, semuanya dibangun di atas fondasi yang sama, jadi mari kita lihat bagaimana memori dikelola dalam C.

Sebelum saya menyelam, penjelasan singkat tentang apa arti " penunjuk " artinya. Pointer hanyalah variabel yang "menunjuk" ke lokasi di memori. Itu tidak mengandung nilai aktual di area memori ini, itu berisi alamat memori itu. Pikirkan blok memori sebagai kotak surat. Pointer akan menjadi alamat ke kotak surat itu.

Dalam C, array hanyalah sebuah pointer dengan offset, offset menentukan seberapa jauh dalam memori terlihat. Ini memberikan O (1) waktu akses.

  MyArray   [5]
     ^       ^
  Pointer  Offset

Semua struktur data lainnya dibangun di atas ini, atau tidak menggunakan memori yang berdekatan untuk penyimpanan, yang mengakibatkan waktu akses acak yang buruk (Meskipun ada manfaat lain untuk tidak menggunakan memori berurutan).

Sebagai contoh, katakanlah kita memiliki array dengan 6 angka (6,4,2,3,1,5) di dalamnya, dalam memori akan terlihat seperti ini:

=====================================
|  6  |  4  |  2  |  3  |  1  |  5  |
=====================================

Dalam sebuah array, kita tahu bahwa setiap elemen bersebelahan dalam memori. Array AC (Dipanggil di MyArraysini) hanyalah sebuah penunjuk ke elemen pertama:

=====================================
|  6  |  4  |  2  |  3  |  1  |  5  |
=====================================
   ^
MyArray

Jika kami ingin melihat ke atas MyArray[4], secara internal itu akan diakses seperti ini:

   0     1     2     3     4 
=====================================
|  6  |  4  |  2  |  3  |  1  |  5  |
=====================================
                           ^
MyArray + 4 ---------------/
(Pointer + Offset)

Karena kita dapat secara langsung mengakses elemen apa pun dalam array dengan menambahkan offset ke pointer, kita dapat mencari elemen apa pun dalam jumlah waktu yang sama, terlepas dari ukuran array. Ini berarti bahwa mendapatkan MyArray[1000]akan memakan waktu yang sama dengan mendapatkan MyArray[5].

Struktur data alternatif adalah daftar yang ditautkan. Ini adalah daftar linear dari pointer, masing-masing menunjuk ke node berikutnya

========    ========    ========    ========    ========
| Data |    | Data |    | Data |    | Data |    | Data |
|      | -> |      | -> |      | -> |      | -> |      | 
|  P1  |    |  P2  |    |  P3  |    |  P4  |    |  P5  |        
========    ========    ========    ========    ========

P(X) stands for Pointer to next node.

Perhatikan bahwa saya membuat setiap "simpul" ke dalam bloknya sendiri. Ini karena mereka tidak dijamin (dan kemungkinan besar tidak akan) berdekatan dalam memori.

Jika saya ingin mengakses P3, saya tidak bisa langsung mengaksesnya, karena saya tidak tahu di mana itu di memori. Yang saya tahu adalah di mana root (P1) berada, jadi alih-alih saya harus mulai dari P1, dan ikuti setiap pointer ke node yang diinginkan.

Ini adalah O (N) look up time (Biaya pencarian meningkat ketika setiap elemen ditambahkan). Jauh lebih mahal untuk mencapai P1000 dibandingkan dengan mendapatkan ke P4.

Struktur data tingkat yang lebih tinggi, seperti hashtable, tumpukan dan antrian, semua dapat menggunakan array (atau beberapa array) secara internal, sedangkan Linked Linked dan Binary Trees biasanya menggunakan node dan pointer.

Anda mungkin bertanya-tanya mengapa ada orang yang menggunakan struktur data yang membutuhkan linear traversal untuk mencari nilai alih-alih hanya menggunakan array, tetapi mereka memiliki kegunaannya.

Ambil array kami lagi. Kali ini, saya ingin menemukan elemen array yang menyimpan nilai '5'.

=====================================
|  6  |  4  |  2  |  3  |  1  |  5  |
=====================================
   ^     ^     ^     ^     ^   FOUND!

Dalam situasi ini, saya tidak tahu offset apa yang harus ditambahkan ke pointer untuk menemukannya, jadi saya harus mulai dari 0, dan bekerja sampai saya menemukannya. Ini berarti saya harus melakukan 6 cek.

Karena itu, mencari nilai dalam array dianggap O (N). Biaya pencarian meningkat karena array semakin besar.

Ingat di atas di mana saya mengatakan bahwa kadang-kadang menggunakan struktur data non sekuensial dapat memiliki keuntungan? Mencari data adalah salah satu keunggulan ini dan salah satu contoh terbaik adalah Pohon Biner.

Binary Tree adalah struktur data yang mirip dengan daftar yang ditautkan, namun alih-alih menautkan ke satu simpul, setiap simpul dapat menautkan ke dua simpul anak.

         ==========
         |  Root  |         
         ==========
        /          \ 
  =========       =========
  | Child |       | Child |
  =========       =========
                  /       \
            =========    =========
            | Child |    | Child |
            =========    =========

 Assume that each connector is really a Pointer

Ketika data dimasukkan ke dalam pohon biner, ia menggunakan beberapa aturan untuk memutuskan di mana menempatkan node baru. Konsep dasarnya adalah bahwa jika nilai baru lebih besar daripada orang tua, itu memasukkannya ke kiri, jika lebih rendah, itu menyisipkannya ke kanan.

Ini berarti bahwa nilai-nilai dalam pohon biner bisa terlihat seperti ini:

         ==========
         |   100  |         
         ==========
        /          \ 
  =========       =========
  |  200  |       |   50  |
  =========       =========
                  /       \
            =========    =========
            |   75  |    |   25  |
            =========    =========

Ketika mencari pohon biner untuk nilai 75, kita hanya perlu mengunjungi 3 node (O (log N)) karena struktur ini:

• Apakah 75 kurang dari 100? Lihatlah Node Kanan
• Apakah 75 lebih besar dari 50? Lihatlah Left Node
• Ada 75!

Meskipun ada 5 simpul di pohon kami, kami tidak perlu melihat dua simpul yang tersisa, karena kami tahu bahwa mereka (dan anak-anak mereka) tidak mungkin mengandung nilai yang kami cari. Ini memberi kita waktu pencarian yang pada kasus terburuk berarti kita harus mengunjungi setiap node, tetapi dalam kasus terbaik kita hanya perlu mengunjungi sebagian kecil dari node.

Di situlah array dikalahkan, mereka menyediakan waktu pencarian O (N) linier, meskipun O (1) waktu akses.

Ini adalah ikhtisar tingkat sangat tinggi pada struktur data dalam memori, melompati banyak detail, tapi mudah-mudahan ini menggambarkan kekuatan dan kelemahan array dibandingkan dengan struktur data lainnya.

Untuk O (1) akses acak, yang tidak dapat dikalahkan.

Tidak semua program melakukan hal yang sama atau berjalan pada perangkat keras yang sama.

Ini biasanya merupakan jawaban mengapa berbagai fitur bahasa ada. Array adalah konsep inti ilmu komputer. Mengganti array dengan daftar / matriks / vektor / struktur data canggih apa pun akan sangat memengaruhi kinerja, dan benar-benar tidak praktis dalam sejumlah sistem. Ada sejumlah kasus di mana menggunakan salah satu dari objek pengumpulan data "canggih" ini harus digunakan karena program tersebut.

Dalam pemrograman bisnis (yang sebagian besar dari kita lakukan), kita dapat menargetkan perangkat keras yang relatif kuat. Menggunakan Daftar di C # atau Vektor di Jawa adalah pilihan yang tepat untuk membuat dalam situasi ini karena struktur ini memungkinkan pengembang untuk mencapai tujuan lebih cepat, yang pada gilirannya memungkinkan jenis perangkat lunak ini menjadi lebih banyak fitur.

Saat menulis perangkat lunak tertanam atau sistem operasi, array mungkin sering menjadi pilihan yang lebih baik. Sementara array menawarkan lebih sedikit fungsionalitas, ia membutuhkan lebih sedikit RAM, dan kompiler dapat mengoptimalkan kode lebih efisien untuk mencari ke dalam array.

Saya yakin saya meninggalkan sejumlah manfaat untuk kasus-kasus ini, tetapi saya harap Anda mengerti maksudnya.

Cara untuk melihat kelebihan array adalah untuk melihat di mana O (1) kemampuan akses array diperlukan dan karenanya dikapitalisasi:

1. Di tabel Cari aplikasi Anda (array statis untuk mengakses respons kategori tertentu)

2. Memoisasi (hasil fungsi kompleks yang sudah dihitung, sehingga Anda tidak menghitung nilai fungsi lagi, katakan log x)

3. Aplikasi visi komputer berkecepatan tinggi yang membutuhkan pemrosesan gambar ( https://en.wikipedia.org/wiki/Lookup_table#Lookup_tables_in_image_processing )