Temel Bilgiler
Günümüz programlama dilleri birçok farklı veri yapısına sahiptir. Bu veri yapılarını sıfırdan tasarlamak yerine doğru bir şekilde kullanmak uygulamalarımıza büyük hız kazandırabilir. Bu yazı 6 farklı veri yapısına ait kısa incelemeler ve performans karşılaştırmaları üzerinedir.
Bu yazıda 6 farklı veri yapısını inceleyeceğiz.
- Dizi
- List
- ArrayList
- LinkedList
- Dictionary
- Hashtable
Dizi en temel veri yapısıdır. Pointer konusu üzerinden bu konuyu hatırlayalım. Aşağıda integer veri içeren bir dizinin bellekte tutulma şeklini görmektesiniz.
Başlangıç adresinden başlayıp 2 byte 2 byte arttırıp tüm kayıtlara rahatlıkla ulaşabiliriz. *p++ ile C dilinde bu işlemi yapabiliyorduk. Ancak daha sonradan bu yapıyı yönetmenin zor olmasından dolayı dizi veri yapısı geliştirilmiştir. Bu veri yapısı sayesinde a[4] gibi bir tanımla ile veriye ulaşmak son derece kolay hale gelmiştir. Fakat, ekleme ve silme işleminde ek dizi açmak ve bir döngü ile tüm verileri (silme işlemi ise silinecek veri hariç) ek diziye taşımak gerekmektedir. İşte bu noktada bu işlemleri kolaylaştırmak için modern programlama dillerindeki List ve ArrayList gibi dinamik diziler imdadımıza koşar. Bu veri yapılarında ekleme ve silme işlemleri metotlarla yapmak mümkün hale gelmiştir.
List Generic bir yapı iken ArrayList object türünde verileri tutabilen non-Generic bir yapıdır. Generic demek veri türünün belirlendiği yapı anlamına gelir. List tanımlanırken “<“,”>” işaretleri arasına veri yapısı yazılır. ArrayList veri yapısı object türünden olduğu için tüm veri türleri yüklenebilir. O zaman niye List var dediğinizi duyar gibiyim, bekleyin biraz bakalım. Aşağıda dizi, List ve ArrayList tanımlama için birer örnek görülmektedir. Boyut değişkeni döngülerde ve dizi yaratma işleminde kullanılacaktır. Boyut değişkeni değiştirilerek farklı veri boyutları için test imkanına kavuşmak için tanımlanmıştır.
1 2 3 4 |
Int64 boyut = 5000000; Int64[] a = new Int64[boyut]; List _list = new List<int64>(); ArrayList _alist = new ArrayList(); |
Diğer veri yapısı bağlı listelerdir. Dizi, List ve ArrayList gibi veri yapılarının en büyük sorunu silme ve ekleme işleminde karşımıza çıkar. Bir silme işlemi yapıldığında ek bir dizi açılıp silinen veri/ler hariç tüm veriler yeni diziye aktarılır. Bu aktarma işlemi büyük bir zaman kaybıdır. Hala ne gerek var diyenler var gibi. Harddisk veya bellek üzerinden bu işlemi açıklayalım. Hardiskimize dosya kopyalayıp sildiğimiz de fragmantasyonlar oluşur. Fragramtasyon arttığında defragmantasyon uygulamak zorunda kalırız. Aslında harddisk yönetiminde bağlı liste modeli kullanılır. Eğer dizi modeli kullanılsaydı aradan bir dosya sildiğimizde büyük bir kaydırma işlemi yapmak zorunda kalırdık ki bu sistemi çok yavaşlatırdı. Linked List kaydırma işlemi yapmadan basitçe silme işlemi yapmamızı sağlar. Konuya hakim olmayanların kafası daha da karışmış olabilir. Bir örnek üzerinden açıklayalım.
Örnekte verinin yanı sıra bir sonraki veriyi gösteren adres bilgisi de tutulmaktadır. Örneğin 1002 adresinde 61 sayısı 1008 adresini işaret etmektedir. Tabii ki bu ek değişken kullanılan bellek miktarını arttırmıştır ama diğer bir taraftan silme işlemi çok kısaltmıştır. Mesela 6 adet elemandan oluşan dizi içinden bir silme işleminde 5’lik bir dizi açıp 5 veriyi taşımalıyız. Fakat bağlı listede bir silme yaptığımızda sadece önceki adres bilgisi güncellenir. Örneğin yukarıdaki bağlı listeden 23 sayısını sildiğimizde Point Adresi->1008 yerine 1018 gelir ve 23 verisi ile birlikte 1018 bilgisi silinir. Yani 3 adet değişiklikle silme işlemi bitirilmiştir. Hardisk, bellek gibi büyük veri kaynaklarının yönetimde bu işlem büyük zaman kazancı sağlamaktadır. .Net/Java gibi dillerde bu veri yapısı için LinkedList sınıfı bulunmaktadır.
1 |
LinkedList link = new LinkedList<Int64>(); |
Ancak bu yöntemde de veriyi aramak için teker teker tüm elemanlar dolaşılmalıdır. Şimdi de aramanın önemli olduğu Dictionary ve Hashtable yapılarına gelelim.
Arama hızının önemli olduğu uygulamalarda hash fonksiyonkları çok iyi bir çözüm olabilir. Hash fonksiyonu üretmek ve organize etmek zor bir süreçtir. .Net/Java gibi ortamlar Dictionary ve Hashtable gibi hazır sınıflar sunmaktadırlar. Dictionary Generic türünden iken Hashtable non-Generic başka bir deyişle Object türündendir. Öncelikle biraz teorik bilgi verelim sonra kod örneklerine geçelim.
Hash fonksiyonlarının amacı en kısa sürede veriye ulaşmaktır. Bu çerçevede belirli bir bellek bölgesine bir fonksiyon üzerinden bellek belgesinde yeri belirlenir ve veri o bölgeye yerleştirilir. Bu tanımı bir örnek üzerinden anlatalım. Bellek bölgesi 10 adet 2 byte’lık bilgiden fonksiyonumuzda gelen sayının modunu almak olsun. Örneğin 23 sayısı geldiğinde 3 nolu bellek bölgesine yerleştirilecek.Bu yöntem sayesinde aradığımız veriye sadece 1 adımda ulaşma şansına sahip olduk.
Örneğimiz çok basit fonksiyonumuzda çok basit oldu. Tabii hash fonksiyonu üretmek bilgisayar biliminin birçok alanında büyük bir problemdir. Büyük dosyalarda aynı veya benzer veriyi bulmak, karşılaştırma işlemlerini hızlandırmak, DNA üzerindeki benzer dizinleri bulmak gibi birçok konuda hash fonksiyonları üzerine çok fazla çalışma yapılmıştır. Hash fonksiyonlar hakkında daha geniş bilgiye ders notlarından ulaşabilirsiniz. Şimdi gelelim kodumuza:
1 2 |
Dictionary _d = new Dictionary<Int64>(); HashTable _ht = new HashTable(); |
Veri Ekleme
Yukarıdaki tanımları kodlarımızı yazacağımız sınıf içine genel değişken olarak yazabilirsiniz. Bu genel değişkenleri aşağıdaki fonksiyonlarda kullanacağız. Öncelikle en temel veri yapımız dizi ile başlayalım.
1 2 3 4 5 6 7 8 9 |
private int Dizi_Yarat() { System.Diagnostics.Stopwatch sw = System.Diagnostics.Stopwatch.StartNew(); a = new int[boyut]; for (int i = 0; i < boyut - 1; i++) a[i] = i; sw.Stop(); return sw.Elapsed.Milliseconds; } |
Yukarıda tanımladığımız a adlı diziden tekrar boyut yer ayırdık ve 0’dan boyut-1 kadar sayıları veri olarak diziye atadık. Ölçümlerde daha hassas sonuçlar verdiği söylendiği için Stopwatch sınıfı kullandık. StopWatch hakkında daha geniş bilgiye Veri Yapıları 3. hafta ders notlarından ulaşabilirsiniz. Aynı verileri diğer veri tiplerine de ekleyelim.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 |
private int List_Yarat() { System.Diagnostics.Stopwatch sw = System.Diagnostics.Stopwatch.StartNew(); l = new List(); for (int i = 0; i < boyut - 1; i++) l.Add(i); sw.Stop(); return sw.Elapsed.Milliseconds; } private int ArrayList_Yarat() { System.Diagnostics.Stopwatch sw = System.Diagnostics.Stopwatch.StartNew(); al = new ArrayList(); for (int i = 0; i < boyut - 1; i++) al.Add(i); sw.Stop(); return sw.Elapsed.Milliseconds; } private int Link_Yarat() { System.Diagnostics.Stopwatch sw = System.Diagnostics.Stopwatch.StartNew(); link = new LinkedList<int>(); for (int i = 0; i < boyut - 1; i++) link.AddLast(i); sw.Stop(); return sw.Elapsed.Milliseconds; } private int Dictionary_Yarat() { System.Diagnostics.Stopwatch sw = System.Diagnostics.Stopwatch.StartNew(); d = new Dictionary<int, int="">(); for (int i = 0; i < boyut - 1; i++) d.Add(i, i); sw.Stop(); return sw.Elapsed.Milliseconds; } private int HashTable_Yarat() { System.Diagnostics.Stopwatch sw = System.Diagnostics.Stopwatch.StartNew(); ht = new Hashtable(); for (int i = 0; i < boyut - 1; i++) ht.Add(i, i); sw.Stop(); return sw.Elapsed.Milliseconds; } |
İncelediğimiz diğer veri yapıları dinamik olarak boyutu değiştirebildikleri için boyut vermeye gerek yoktur. List ve ArrayList tek parametre alan Add komutu ile veri alır. ArrayList Object türünden olmasına rağmen bir dönüşüm yapılmadan int bir veriyi alabilir. LinkedList veri yapısında listenin sonuna ekleme yapan AddLast komutunu kullandık. Bu veri yapısının en güzel yanı başa, araya ve sona ekleme yapmamızı kolaylaştırmasıdır. Dictionary ve Hashtable yine Add komutunu kullanır ancak 2 parametrelidir. Birinci parametre “key” ve ikinci parametre “value” idir. Key seçimi benzersiz olmalıdır ve arama işlemi bu anahtar üzerinden yapılacaktır.
Veri Arama
Veri arama işlemi dizi, List, ArrayList ve LinkedList üzerinde benzer şekilde olur. Bir döngü açılır ve istenen kayıt bulununca kadar veya son kayda tüm verilerle karşılaştırma yapılır. ArrayList ve Hashtable gibi object veri yapılarında “(int)veri” türünden bir dönüşüm işlemi uygulanır. Bu işleme unboxing dendiğini derslerde anlatmıştık. Bu dönüşüm işleminin aramayı yavaşlatması kaçınılmazdır. Aşağıdaki tüm aramalarda veri bulunduktan sonra break komutu ile döngüden çıkılmıştır. Benzer çok veri varsa break komutu ile çıkma anlamsızdır. Derslerimizde Arama konusunda üzeride bu konuyu anlatacağız. Dictionary ve Hashtable veri yapılarında arama işleminde bool değer döndüren “ContainsKey” adlı metod ile anahtarın olup olmadığı hızlı bir şekilde bulunabilir. Bir döngüye ihtiyaç yoktur.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 |
private int Dizi_Arama() { System.Diagnostics.Stopwatch sw = System.Diagnostics.Stopwatch.StartNew(); for (int i = 0; i < boyut - 1; i++) if (aranan == a[i]) break; sw.Stop(); return sw.Elapsed.Milliseconds; } private int List_Arama() { System.Diagnostics.Stopwatch sw = System.Diagnostics.Stopwatch.StartNew(); for (int i = 0; i < boyut - 1; i++) if (aranan == l[i]) break; sw.Stop(); return sw.Elapsed.Milliseconds; } private int ArrayList_Arama() { System.Diagnostics.Stopwatch sw = System.Diagnostics.Stopwatch.StartNew(); for (int i = 0; i < boyut - 1; i++) if (aranan == (int)al[i]) break; sw.Stop(); return sw.Elapsed.Milliseconds; } private int Link_Arama() { System.Diagnostics.Stopwatch sw = System.Diagnostics.Stopwatch.StartNew(); foreach (int _i in link) { if (aranan == _i) break; } sw.Stop(); return sw.Elapsed.Milliseconds; } private int HashTable_Arama() { System.Diagnostics.Stopwatch sw = System.Diagnostics.Stopwatch.StartNew(); bool sonuc = ht.ContainsKey(aranan);//Arama İşlemi sw.Stop(); return sw.Elapsed.Milliseconds; } private int Dictionary_Arama() { System.Diagnostics.Stopwatch sw = System.Diagnostics.Stopwatch.StartNew(); bool sonuc = d.ContainsKey(aranan);//Arama İşlemi sw.Stop(); return sw.Elapsed.Milliseconds; } |
Veri Silme
Dizide silme yapmak için bir eksik dizi oluşturulur ve silinecek veri hariç tüm veriler yeni diziye aktarılır. Diğer veri yapılarında void bir metod olan”remove” metodu ile silme yapmak son derece kolaydır.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 |
private int Dizi_Sil() { System.Diagnostics.Stopwatch sw = System.Diagnostics.Stopwatch.StartNew(); int[] newIndicesArray = new int[a.Length - 1]; int i = 0; int j = 0; while (i < a.Length) { if (i != aranan) { newIndicesArray[j] = a[i]; j++; } i++; } a = newIndicesArray; sw.Stop(); return sw.Elapsed.Milliseconds; } private int List_Sil() { System.Diagnostics.Stopwatch sw = System.Diagnostics.Stopwatch.StartNew(); l.Remove(aranan); sw.Stop(); return sw.Elapsed.Milliseconds; } private int ArrayList_Sil() { System.Diagnostics.Stopwatch sw = System.Diagnostics.Stopwatch.StartNew(); al.Remove((int)aranan); sw.Stop(); return sw.Elapsed.Milliseconds; } private int Link_Sil() { System.Diagnostics.Stopwatch sw = System.Diagnostics.Stopwatch.StartNew(); link.Remove(aranan); sw.Stop(); return sw.Elapsed.Milliseconds; } private int Dictionary_Sil() { System.Diagnostics.Stopwatch sw = System.Diagnostics.Stopwatch.StartNew(); d.Remove(aranan); sw.Stop(); return sw.Elapsed.Milliseconds; } private int HashTable_Sil() { System.Diagnostics.Stopwatch sw = System.Diagnostics.Stopwatch.StartNew(); ht.Remove((int)aranan); sw.Stop(); return sw.Elapsed.Milliseconds; } |
Karşılaştırma
6 veri yapısını karşılaştırırken yaratma, arama ve silme açısından ms bazında karşılaştırma yapılmıştır. Her veri yapısı için 5,000,000 adet veri yaratılmış, tüm kayıtlarda aynı veri aranmış ve aynı veri silinip süreler karşılaştırılmıştır. Test Sonuçlar:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
Dizi yaratma: 31 ms Dizi içinde arama: 12 ms Dizi içinden silme: 97 ms ArrayList yaratma: 388 ms ArrayList içinde arama: 52 ms ArrayList içinden silme: 53 ms List yaratma: 190 ms List içinde arama: 47 ms List içinden silme: 7 ms LinkedList yaratma: 298 ms LinkedList içinde arama: 60 ms LinkedList içinden silme: 17 ms HashTable yaratma: 722 ms HashTable içinde arama: 0 ms HashTable içinden silme: 0 ms Dictionary yaratma: 464 ms Dictionary içinde arama: 0 ms Dictionary içinden silme: 0 ms |
Sonuçların yorumlanması:
Veri yaratma süreleri
- Dizi yaratmak ve verileri aktarmak en hızlı dizi veri yapısında olmuştur. Bellekte daha önceden açılmış bir alan üzerinde işlem yapmak diğer yapılara göre büyük avantaj sağlar.
- ArrayList Object türünden olduğu için boxing / unboxing işlemi başka bir deyişle veri tipinden object’e, objectten veri tipine dönüşüm işlemleri yaratma işlemine zaman kaybı olarak yansımıştır. List veri yapısı generic türünden olmasının bir avantaj olduğu görülmektedir.
- LinkedList’e bağlantının yapılması ve verinin eklenmesi zaman kaybı oluşturmaktadır.
- Hashtable ve Dictionary için hash fonksiyon hesabı zaman almakta ve en yavaş yaratma bu veri tipinde olmaktadır. Object türünden olan Hashtable’ın yaratması 2. bölümde belirtilen sebep yüzünden yavaş kaldığı görülmektedir.
Arama/Silme Süreleri
- En hızlı arama/silme Hashtable ve Dictionary üzerindedir. Bu veri tiplerinde o kadar hızlı arama/silme olmuştur ki süre ölçülememiştir. Ölçmek için kod üzerinde uzun bir döngü açıp test yapabilirsiniz. Dictionary, Hashtable göre çok daha hızlı çıkacaktır.
- Boxing / Unboxing işlemleri arama da zaman kaybı yaratmaktadır. Bu sebepten dolayı Object türünden yapılardan kaçınılması gerekmektedir.
- Diğer yöntemlerde arama/silme yavaş olduğu, dizinin yapısı sebebiyle en hızlı aramaya sahip olduğu görülmektedir. Silme işlemi konusunda ise en yavaş dizi veri yapısının olduğu görülmektedir.
- Silme işleminde linked list’e verinin aranması zaman kaybı yaratmaktadır. Aslında veri bulunduktan sonra en hızlı silme özelliğine sahip yapı linked list veri yapısıdır.
Bu çalışmada 6 hazır veri yapısından hangi durumda hangi veri yapısının iyi olacağı test edilmiştir. .Net/Java gibi ortamlarda bu veri yapıların yanı sıra stack, queue, sortedlist gibi birçok veri yapısını sunulmaktadır. Uygulamanın türüne göre doğru veri yapısının seçilmesi çok önemlidir. Arama ve silmenin önemli olmadığı yapılarda dizi tercih edilebilir. Boyutu bilinmeyen yapılar için list çok kullanışlıdır. Verinin pozisyonu bilindiğinde en hızlı silme işlemi linked list veri yapısında olmaktadır. İşin içine arama girdiğinde Dictionary veri yapısı tercih edilebilir. Özellikle generic (veri türü belli) türde veri yapılarının seçilmesi işlemlerimizi hızlandıracağı unutulmamalıdır. Veri yapıları dersinde bir çok veri yapısını inceleyeceğiz. ADYS – Veri Yapıları 3. hafta ders notu üzerinden uygulamayı indirebilirsiniz. İyi çalışmalar…
Teşekkürler
Bu çalışmada, yakın arkadaşım Dr. Yaşar Küçükefe’nin önerdiği SVG dilini kullandım. Önerisi için çok teşekkür ederim, görsellikleri bile kod ile oluşturmak çok zevkli idi. Dr. Yaşar Küçükefe dersbu.net sitesi tamamen SVG ile yapılmıştır. Animasyon olayı sadece Chrome destek verdiği için bu siteye Chrome üzerinden incelemenizi öneririm. Bu çalışmam da Chrome hariç diğer tarayıcıların SVG’nin animasyon özelliği desteklenmedikleri için sade SVG kodları kullandım. Gördüğünüz grafikler jpeg veya resim formatında değildir. HTML kodu gibi SVG kodları ile oluşturulmaktadır. SVG, w3.org tarafından desteklenmektedir.