Struktur data .NET: ArrayList, List, HashTable, Kamus, SortedList, SortedDictionary - Kecepatan, memori, dan kapan harus menggunakan masing-masing?

.NET memiliki banyak struktur data yang kompleks. Sayangnya, beberapa di antaranya sangat mirip, dan saya tidak selalu yakin kapan harus menggunakannya dan kapan harus menggunakan yang lain. Sebagian besar buku C # dan Visual Basic saya berbicara tentang mereka sampai batas tertentu, tetapi mereka tidak pernah benar-benar masuk ke detail nyata.

Apa perbedaan antara Array, ArrayList, Daftar, Hashtable, Kamus, SortedList, dan SortedDictionary?

Mana yang dapat dihitung (IList - dapat melakukan loop 'foreach')? Yang mana yang menggunakan pasangan kunci / nilai (IDict)?

Bagaimana dengan jejak memori? Kecepatan penyisipan? Kecepatan pengambilan?

Apakah ada struktur data lain yang layak disebutkan?

Saya masih mencari detail lebih lanjut tentang penggunaan dan kecepatan memori (notasi Big-O).

Dari atas kepala saya:

• Array* - mewakili larik memori old-school - jenis seperti alias untuk type[]larik normal . Dapat menghitung. Tidak dapat tumbuh secara otomatis. Saya akan menganggap kecepatan memasukkan dan retrival sangat cepat.

• ArrayList- Array yang tumbuh secara otomatis. Menambahkan lebih banyak overhead. Bisa enum., Mungkin lebih lambat dari array normal tetapi masih cukup cepat. Ini banyak digunakan dalam .NET

• List- salah satu favorit saya - dapat digunakan dengan obat generik, sehingga Anda dapat memiliki larik yang sangat diketik, misalnya List<string>. Selain itu, bertindak sangat miripArrayList

• Hashtable- hashtable lama polos. O (1) hingga O (n) kasus terburuk. Dapat menyebutkan nilai dan properti kunci, dan melakukan pasangan kunci / val

• Dictionary - sama seperti di atas hanya diketik melalui generik, seperti Dictionary<string, string>

• SortedList- daftar umum yang diurutkan. Memperlambat penyisipan karena harus mencari tahu di mana harus meletakkan barang-barang. Bisa enum., Mungkin sama pada pengambilan karena tidak harus resor, tetapi penghapusan akan lebih lambat dari daftar lama.

Saya cenderung menggunakan Listdan Dictionarysepanjang waktu - setelah Anda mulai menggunakannya sangat diketik dengan obat generik, sangat sulit untuk kembali ke yang non-generik standar.

Ada banyak struktur data lain juga - ada KeyValuePairyang dapat Anda gunakan untuk melakukan beberapa hal menarik, ada SortedDictionaryyang bisa berguna juga.

Jika memungkinkan, gunakan obat generik. Ini termasuk:

• Daftar bukan ArrayList
• Kamus bukan HashTable

Pertama, semua koleksi di .NET mengimplementasikan IEnumerable.

Kedua, banyak koleksi adalah duplikat karena obat generik ditambahkan dalam versi 2.0 dari framework.

Jadi, meskipun koleksi generik cenderung menambahkan fitur, sebagian besar:

• Daftar adalah implementasi generik dari ArrayList.
• Kamus adalah implementasi generik dari Hashtable

Array adalah koleksi ukuran tetap yang Anda dapat mengubah nilai yang disimpan pada indeks yang diberikan.

SortedDictionary adalah IDictionary yang disortir berdasarkan kunci. SortedList adalah IDictionary yang diurutkan berdasarkan IComparer yang diperlukan.

Jadi, implementasi IDictionary (yang mendukung KeyValuePairs) adalah: * Hashtable * Kamus * SortedList * SortedDictionary

Koleksi lain yang ditambahkan di .NET 3.5 adalah Hashset. Ini adalah koleksi yang mendukung operasi yang ditetapkan.

Juga, LinkedList adalah implementasi standar daftar tertaut (Daftar adalah daftar-array untuk pengambilan lebih cepat).

Berikut beberapa tip umum untuk Anda:

• Anda dapat menggunakan foreachtipe yang menerapkan IEnumerable. IListpada dasarnya adalah properti IEnumberabledengan Countdan Item(mengakses item menggunakan indeks berbasis nol). IDictionarydi sisi lain berarti Anda dapat mengakses item dengan indeks hashable apa pun.

• Array, ArrayListdan Listsemua implementasi IList. Dictionary,, SortedDictionarydan Hashtablemengimplementasikan IDictionary.

• Jika Anda menggunakan .NET 2.0 atau lebih tinggi, Anda disarankan untuk menggunakan rekan generik dari jenis yang disebutkan.

• Untuk kompleksitas ruang dan waktu dari berbagai operasi pada jenis ini, Anda harus membaca dokumentasinya.

• Struktur data .NET berada di System.Collectionsnamespace. Ada jenis perpustakaan seperti PowerCollections yang menawarkan struktur data tambahan.

• Untuk mendapatkan pemahaman menyeluruh tentang struktur data, konsultasikan dengan sumber daya seperti CLRS .

Struktur data .NET:

Lebih ke percakapan tentang mengapa ArrayList dan Daftar sebenarnya berbeda

Array

Seperti yang dinyatakan oleh satu pengguna, Array adalah koleksi "old school" (ya, array dianggap sebagai koleksi meskipun bukan bagian dari System.Collections). Tapi, apa "old school" tentang array dibandingkan dengan koleksi lain, yaitu yang sudah Anda daftarkan dalam judul Anda (di sini, ArrayList dan Daftar (Dari T))? Mari kita mulai dengan dasar-dasarnya dengan melihat Array.

Untuk memulai, Array dalam Microsoft .NET adalah, "mekanisme yang memungkinkan Anda untuk memperlakukan beberapa item [terkait secara logis] sebagai satu koleksi," (lihat artikel yang ditautkan). Apa artinya? Array menyimpan anggota individu (elemen) secara berurutan, satu demi satu dalam memori dengan alamat awal. Dengan menggunakan array, kita dapat dengan mudah mengakses elemen yang disimpan secara berurutan yang dimulai dari alamat itu.

Di luar itu dan bertentangan dengan pemrograman 101 konsepsi umum, Array benar-benar bisa sangat kompleks:

Array dapat berupa dimensi tunggal, multidimensi, atau jadded (array bergerigi layak dibaca). Array sendiri tidak dinamis: sekali diinisialisasi, sebuah array n cadangan ukuran cukup ruang untuk terus n jumlah objek. Jumlah elemen dalam array tidak dapat tumbuh atau menyusut. Dim _array As Int32() = New Int32(100)cadangan cukup ruang pada blok memori untuk array mengandung 100 objek tipe primitif Int32 (dalam hal ini, array diinisialisasi untuk mengandung 0s). Alamat blok ini dikembalikan ke _array.

Menurut artikel tersebut, Spesifikasi Bahasa Umum (CLS) mensyaratkan bahwa semua array berbasiskan nol. Array dalam .NET mendukung array berbasis tidak nol; Namun, ini jarang terjadi. Sebagai hasil dari "common-ness" dari array berbasis nol, Microsoft telah menghabiskan banyak waktu untuk mengoptimalkan kinerja mereka ; Oleh karena itu, array berdimensi tunggal, berbasis nol (SZ) adalah "spesial" - dan benar-benar implementasi terbaik dari array (bukan multidimensi, dll.) - karena SZ memiliki instruksi bahasa perantara khusus untuk memanipulasi mereka.

Array selalu dilewati oleh referensi (sebagai alamat memori) - bagian penting dari teka-teki Array untuk diketahui. Sementara mereka melakukan pemeriksaan batas (akan menimbulkan kesalahan), pemeriksaan batas juga dapat dinonaktifkan pada array.

Sekali lagi, halangan terbesar bagi array adalah bahwa mereka tidak berukuran besar. Mereka memiliki kapasitas "tetap". Memperkenalkan ArrayList dan Daftar (T) ke riwayat kami:

ArrayList - daftar non-generik

The ArrayList (bersama dengan List(Of T)- meskipun ada beberapa perbedaan penting, di sini, dijelaskan nanti) - mungkin yang terbaik dianggap sebagai penambahan samping koleksi (dalam arti luas). ArrayList mewarisi dari antarmuka IList (turunan dari 'ICollection'). ArrayLists, sendiri, lebih besar - membutuhkan lebih banyak overhead - daripada Daftar.

IListtidak memungkinkan implementasi untuk memperlakukan ArrayLists sebagai daftar berukuran tetap (seperti Array); Namun, di luar fungsi tambahan yang ditambahkan oleh ArrayLists, tidak ada keuntungan nyata untuk menggunakan ArrayLists yang ukurannya tetap karena ArrayLists (lebih dari Array) dalam hal ini sangat lambat.

Dari bacaan saya, ArrayLists tidak dapat digerigi: "Menggunakan array multidimensi sebagai elemen ... tidak didukung". Sekali lagi, paku lain di peti mati ArrayLists. ArrayLists juga tidak "diketik" - yang berarti bahwa, di bawah semuanya, ArrayList hanyalah sebuah Array dinamis Objects: Object[]. Ini membutuhkan banyak tinju (implisit) dan unboxing (eksplisit) ketika mengimplementasikan ArrayLists, sekali lagi menambah overhead mereka.

Pemikiran yang tidak berdasar: Saya pikir saya ingat pernah membaca atau pernah mendengar dari salah satu profesor saya bahwa ArrayLists adalah semacam anak konseptual bajingan dari upaya untuk berpindah dari Array ke Koleksi Jenis-daftar, yaitu ketika pernah mengalami peningkatan besar ke Array, mereka bukan lagi pilihan terbaik karena pengembangan lebih lanjut telah dilakukan sehubungan dengan koleksi

List (Of T): Apa yang menjadi ArrayList (dan berharap menjadi)

Perbedaan dalam penggunaan memori cukup signifikan di mana Daftar (Dari Int32) mengkonsumsi 56% lebih sedikit memori daripada ArrayList yang mengandung tipe primitif yang sama (8 MB vs 19 MB dalam demonstrasi terkait pria di atas: sekali lagi, ditautkan di sini ) - meskipun ini adalah hasil yang diperparah oleh mesin 64-bit. Perbedaan ini benar-benar menunjukkan dua hal: pertama (1), sebuah kotak "objek" tipe Int32 (ArrayList) jauh lebih besar daripada tipe primitif Int32 murni (Daftar); kedua (2), perbedaannya eksponensial sebagai hasil dari pengerjaan mesin 64-bit.

Jadi, apa bedanya dan apa itu List (Of T) ? MSDN mendefinisikan List(Of T)sebagai, "... daftar objek yang diketik dengan sangat kuat yang dapat diakses oleh indeks." Pentingnya di sini adalah bit "sangat diketik": daftar (Dari T) 'mengenali' jenis dan menyimpan objek sebagai tipenya. Jadi, sebuah Int32disimpan sebagai Int32dan bukan Objecttipe. Ini menghilangkan masalah yang disebabkan oleh tinju dan unboxing.

MSDN menentukan perbedaan ini hanya berlaku ketika menyimpan tipe primitif dan bukan tipe referensi. Juga, perbedaannya benar-benar terjadi dalam skala besar: lebih dari 500 elemen. Yang lebih menarik adalah bahwa dokumentasi MSDN berbunyi, "Adalah keuntungan bagi Anda untuk menggunakan implementasi tipe-spesifik dari kelas List (Of T) daripada menggunakan kelas ArrayList ...."

Pada dasarnya, List (Of T) adalah ArrayList, tetapi lebih baik. Ini adalah "setara generik" dari ArrayList. Seperti ArrayList, itu tidak dijamin untuk diurutkan sampai disortir (gambar). Daftar (Of T) juga memiliki beberapa fungsi tambahan.

Saya bersimpati dengan pertanyaan - saya juga menemukan (menemukan?) Pilihan yang membingungkan, jadi saya menetapkan secara ilmiah untuk melihat struktur data mana yang tercepat (saya melakukan tes menggunakan VB, tapi saya membayangkan C # akan sama, karena kedua bahasa lakukan hal yang sama di level CLR). Anda dapat melihat beberapa hasil pembandingan yang dilakukan oleh saya di sini (ada juga beberapa diskusi tentang tipe data mana yang terbaik untuk digunakan dalam keadaan apa).

Mereka dieja dengan sangat baik dalam intellisense. Cukup ketik System.Collections. atau System.Collections.Generics (lebih disukai) dan Anda akan mendapatkan daftar dan deskripsi singkat tentang apa yang tersedia.

Hashtables / Dictionaries adalah O (1) kinerja, artinya kinerja bukan fungsi ukuran. Itu penting untuk diketahui.

EDIT: Dalam prakteknya, kompleksitas waktu rata-rata untuk pencarian Hashtable / Kamus <> adalah O (1).

Koleksi generik akan berkinerja lebih baik daripada rekan non-generiknya, terutama ketika melakukan iterasi melalui banyak item. Ini karena tinju dan unboxing tidak lagi terjadi.

Catatan penting tentang Hashtable vs Kamus untuk teknik perdagangan sistematis frekuensi tinggi: Masalah Keamanan Thread

Hashtable aman untuk digunakan oleh banyak utas. Kamus anggota statis publik aman untuk thread, tetapi anggota instance apa pun tidak dijamin akan melakukannya.

Jadi Hashtable tetap menjadi pilihan 'standar' dalam hal ini.

Ada perbedaan halus dan tidak begitu halus antara koleksi generik dan non-generik. Mereka hanya menggunakan struktur data dasar yang berbeda. Misalnya, Hashtable menjamin satu-penulis-banyak-pembaca tanpa sinkronisasi. Kamus tidak.

Struktur dan Koleksi Data C # paling populer

• Himpunan
• ArrayList
• Daftar
• LinkedList
• Kamus
• HashSet
• Tumpukan
• Antre
• DiurutkanDaftar

C # .NET memiliki banyak struktur data yang berbeda, misalnya, salah satu yang paling umum adalah Array. Namun C # hadir dengan lebih banyak struktur data dasar. Memilih struktur data yang tepat untuk digunakan adalah bagian dari penulisan program yang terstruktur dengan baik dan efisien.

Dalam artikel ini saya akan membahas struktur data C # bawaan, termasuk yang baru diperkenalkan di C # .NET 3.5. Perhatikan bahwa banyak dari struktur data ini berlaku untuk bahasa pemrograman lain.

Himpunan

Struktur data yang mungkin paling sederhana dan paling umum adalah array. AC # array pada dasarnya adalah daftar objek. Sifat-sifat yang menentukan adalah bahwa semua objek adalah tipe yang sama (dalam kebanyakan kasus) dan ada jumlah tertentu dari mereka. Sifat array memungkinkan akses yang sangat cepat ke elemen berdasarkan posisi mereka dalam daftar (atau dikenal sebagai indeks). AC # array didefinisikan seperti ini:

[object type][] myArray = new [object type][number of elements]

Beberapa contoh:

 int[] myIntArray = new int[5];
 int[] myIntArray2 = { 0, 1, 2, 3, 4 };

Seperti yang Anda lihat dari contoh di atas, sebuah array dapat diinternalisasi tanpa elemen atau dari sekumpulan nilai yang ada. Memasukkan nilai ke dalam array adalah hal yang sederhana asalkan sesuai. Operasi menjadi mahal ketika ada lebih banyak elemen daripada ukuran array, di mana titik array perlu diperluas. Ini membutuhkan waktu lebih lama karena semua elemen yang ada harus disalin ke array baru yang lebih besar.

ArrayList

Struktur data C #, ArrayList, adalah array dinamis. Apa itu artinya ArrayList dapat memiliki jumlah objek dan jenis apa pun. Struktur data ini dirancang untuk menyederhanakan proses penambahan elemen baru ke dalam array. Di bawah tenda, ArrayList adalah array yang ukurannya berlipat ganda setiap kali kehabisan ruang. Menggandakan ukuran array internal adalah strategi yang sangat efektif yang mengurangi jumlah penyalinan elemen dalam jangka panjang. Kami tidak akan mendapatkan bukti itu di sini. Struktur data sangat mudah digunakan:

    ArrayList myArrayList = new ArrayList();
    myArrayList.Add(56);
    myArrayList.Add("String");
    myArrayList.Add(new Form());

Kerugian dari struktur data ArrayList adalah seseorang harus mengembalikan nilai yang diambil kembali ke tipe aslinya:

int arrayListValue = (int)myArrayList[0]

Sumber dan info lebih lanjut dapat Anda temukan di sini :

• C # Struktur Data
• Koleksi dan Struktur Data
• Daftar vs IEnumerable vs IQueryable vs ICollection vs IDictionary
• System.Collections.Namespace Umum
• System.Collections Namespace

Saya menemukan bagian "Pilih Koleksi" dari Microsoft Documents pada halaman Kumpulan dan Struktur Data benar-benar bermanfaat

C # Koleksi dan Struktur Data: Pilih koleksi

Dan juga matriks berikut untuk membandingkan beberapa fitur lainnya