Dizi mi? Liste mi? Hangisini kullanmalıyım?
Merhaba, bu yazı Grokking Algorithms kitabındaki bazı bölümlerin çevirisidir. Bu yazıyı yazmama izin veren kitabın yazarı Aditya Bhargava’ya teşekkür ederim. Ayrıca bir teşekkür de İbrahim Kürce ağabeye etmek istiyorum. Kendisinin Medium yazılarından bu kitabı keşfedip okumaya başladım.
Diziler (arrays) ve bağlı listeler (linked lists) için hangisini kullanmalıyım ya da nerede kullanmalıyım sorusunun cevabını bulmaya çalışacağız. İkisi de birçok veri yapısının temellerini oluşturuyor. Diziler çok önemli bir konudur. Kullanırken dikkatli olmamız gerekiyor. Bazen dizi yerine bağlı liste kullanmak daha iyi bir çözümdür. Bu yazı her ikisinin de artı ve eksilerini açıklar. Böylece probleminiz için hangisinin doğru olduğuna karar verebiliriz. Öncelikle Big O notasyonu nedir buna bakalım.
Big O notasyonu bir algoritmanın ne kadar hızlı olduğunu söyler. Algoritmanın ne kadar sürede çalışacağını söylemez.
Ör; Bir listedeki tüm öğeleri kontrol eden bir algoritma yazdığınızı ve bu algoritmaya Simple Search diye isim verdiğinizi farzedin. Simple Search algoritmanız n boyutundaki bir liste için n adet işlem yapacak demektir. Dolayısıyla algoritmanızın Big O gösterimi O(n) olacaktır.
Aşağıda, en hızlıdan en yavaşa doğru sıralanmış çok karşılaşılan Big O çalışma zamanlarını göreceksiniz.
- O(log n) Binary search algoritması
- O(n) Simple search algoritması
- O(n * log n) Quick sort algoritması
- O(n*n) Selection sort algoritması
- O(n!) Traveling salesperson algoritması
Bilgisayar hafızası nasıl çalışır?
Hafızada bir öğe saklamak istediğimizde bilgisayara gidip bana hafızadan bir slot verir misin deriz. Eğer birden fazla öğe saklamak istiyorsak bunu yapmanın iki temel yolu var. Ya dizi ya da liste kullanmamız gerekiyor.
Diziler ve Bağlı listeler
Bazen hafızada birden fazla öğe saklamak isteyebiliriz.
Yapılacak işlerinizi yönetmek için bir uygulama yazdığınızı varsayalım. Yapılacakları bellekte bir liste olarak saklamak isteyeceksiniz. Dizi mi yoksa bağlı liste mi kullanmalıyız? Önce dizi kullanmayı deneyelim. Dizi kullanmak bellekte saklayacağınız tüm öğelerin hafızada bitişik (yan yana) depolandığı anlamına gelir.
Şimdi dördüncü bir görev eklemek istediğinizi varsayalım. Ama bir sonraki slot başka bir işlem tarafından kullanılıyor.
Arkadaşlarınızla sinemaya gittiğinizde başka bir arkadaşınız da size katılmak istediğinde oturacak yerin olmaması gibi düşünebilirsiniz. Yapmanız gereken hepinizin sığdığı yeni bir yere taşınmak.
Bu durumda, bilgisayarınızdan dört görevi de sığdırabilecek farklı bir bellek yığını istemeniz gerekir.
Eğer başka bir arkadaşınız daha size katılsa yine farklı bir yere taşınmanız gerekecek. Bu istemediğiniz bir durum olacaktır. Benzer şekilde bir diziye yeni bir öğe eklemek çok masraflı bir işlemdir.
Bu duruma kolay bir çözüm uygularsak; görev listenizde 3 öğe olsa bile her ihtimale karşı hafızadan 10 öğelik yer isteyebilirsiniz. Böylece taşımak zorunda kalmadan listenize 10 öğe daha ekleyebilirsiniz. Bu iyi bir yol olabilir ama bilmemiz gereken birkaç kusurlu nokta var:
- Hafızadan istediğiniz ekstra slot lara ihtiyacınız olmayabilir. Dolayısıyla hafızayı boşa işgal etmiş olacaksınız.
- Listenize 10'dan fazla öğe eklediğinizde tekrar hafızadan tüm öğelerinizi sığdırabilecek farklı bir bellek yığını istemeniz gerekir.
Bu iyi bir çözüm olabilir ama mükemmel bir çözüm değildir. Bu sorunu Bağlı listeler ile çözmek kulağa daha iyi geliyor.
Bağlı listeler
Bağlı listeler ile öğelerinizi hafızada herhangi bir yerde saklayabilirsiniz.
Her öğe bir sonraki öğenin adresini saklar.
Hazine avı gibi bir şey. İlk adrese gidersiniz ve “Bir sonraki öğe 123 nolu adreste bulunuyor” der. Böylece 123 adresine gidersiniz ve “Bir sonraki öğe 847 nolu adreste bulunuyor” der vs. vs.
Bağlı listeye bir öğe eklemek kolaydır. Onu hafızada herhangi bir yere yerleştirebilirsiniz ve eklediğiniz öğenin adresini önceki öğe ile birlikte saklarsınız. Bağlı listelerle, öğelerinizi taşımak zorunda kalmazsınız.
Diyelim ki beş arkadaşınızla popüler bir filme gidiyorsunuz. Altı arkadaş oturacak bir yer bulmaya çalışıyorsunuz ama sinema salonu tıklım tıklım. Yan yana 6 tane boş koltuk bulamadınız. Yazılımda bu sorunla karşılaştığınızda dizi kullanıyor olsaydınız hafızadan yer alamazdınız. Bu durumu biraz karikatürize edelim. Eğer bu sorunla diziler karşılaşsaydı “Çocuklar maalesef yan yana 6 koltuk yok. Bu filmi daha sonra izlemek zorundayız.” derlerdi. Ya bağlı liste bu sorunla karşılaştığında ne derdi? “Ayrılalım ve filmin tadını çıkaralım”
Diziler
Bazı haber siteleri daha fazla görüntüleme almak için kötü bir teknik kullanırlar. Bir haber galerisindeki tüm resimleri tek sayfada göstermek yerine her sayfaya bir resim koyarlar. Bir sonraki resmi görmeniz için ileri butonuna tıklamanız şartdır. Ör; En iyi 10 Televizyon oyuncusu listesinin tamamını tek sayfada göstermez. Bunun yerine 10. sayfadan başlayıp ileri butonuna tıklaya tıklaya 1. sayfaya ancak ulaşırsınız. Tüm liste bir sayfada olsaydı ve daha fazla bilgi için her kişinin adını tıklayabilseydiniz çok daha iyi olurdu.
Benzer bir problem bağlı listeler için de geçerli. Bağlı listedeki son öğeye erişmek istediğinizi varsayalım. Erişemezsiniz çünkü hafıza hangi adreste tutulduğunu bilmiyorsunuz. Bunun yerine, 2. öğenin adresini almak için 1. öğeye gitmelisiniz. Daha sonra 3. öğenin adresini almak için 2. öğeye gitmelisiniz. Son öğeye ulaşmak için bu işlemleri tekrarlarsınız. Eğer tüm öğeleri teker teker okuyacaksanız, bağlı listeler kullanılabilir. Ama herhangi bir öğeye direkt erişmek istiyorsanız performansı oldukça düşüktür.
Diziler ise farklıdır. Dizideki her öğenin adresini biliyorsunuz. Örneğin, dizinizin beş öğe içerdiğini ve 00 adresinde başladığını bildiğinizi varsayalım. 5. öğenin adresi nedir?
Cevabı oldukça basittir. Matematik bize 5. öğenin 04 numaralı adreste olduğunu söyler. Dizideki herhangi bir öğeye anında erişebildiğimizden dolayı öğeleri okuma işlemi çok hızlıdır.
Bağlı listelerde ise öğeler hafızada yan yana saklanmak zorunda değildir. Bu nedenle 5. öğenin bellekte hangi adreste saklandığını anında hesaplayamazsınız. Bunun yerine, 2. öğenin adresini almak için 1. öğeye gitmelisiniz. Daha sonra 3. öğenin adresini almak için 2. öğeye gitmelisiniz. Ulaşmak istediğiniz öğeye erişinceye kadar bu işlemleri tekrarlarsınız.
Listenin arasına eleman ekleme
Daha önce oluşturduğumuz Yapılacaklar listesinin takvim gibi çalışmasını istediğinizi varsayalım. Daha önce bu listeye yeni bir öğe eklemek istediğimizde sona ekliyorduk. Şimdi ise yeni bir öğe eklemek istediğimizde yapılmaları gereken sıraya göre eklemek istiyoruz.
Araya bir öğe eklemek istediğinizde Dizi mi yoksa Liste mi kullanmak daha doğru olur? Liste kullanmak daha doğru bir yaklaşım olur. Çünkü önceki öğrenin işaret ettiği adresteki öğeyi değiştirmek daha kolaydır.
Diziler için ise araya eklenen elemandan sonraki tüm elemanların bir yan tarafa (sağa doğru) kaydırılması gerekiyor. Eğer yan tarafa kaydırılamıyor ise (yer yok ise) tüm öğelerin sığacağı yeni bir hafıza yığınına taşınmanız gerekiyor.
Silme işlemi
Ya bir öğeyi silmek isterseniz ne olur? Bu durumda listelerin performansı daha iyidir. Çünkü önceki öğrenin işaret ettiği adresteki öğeyi silmek daha kolaydır.
Diziden bir öğe sildiğinize ise tüm öğelerin bir yan tarafa (sola doğru) kaydırılması taşınması gerekir. Ekleme işleminin aksine, silme işlemleri her zaman çalışır. Hafızada yer kalmadığında ekleme işlemi başarısız olabilir. Ancak bir öğeyi her zaman silebilirsiniz.
Peki bu bilgilerden sonra hangisini kullanmalıyız? Dizi mi? Liste mi? Açıkçası, kullanım durumuna bağlıdır. Dizilerin çok fazla kullanılmasının nedeni rastgele erişime izin veriyor olmalarıdır.
İki farklı erişim türü vardır: rastgele (random) ve sıralı (sequential) erişim. Sıralı erişim, ilk öğeden başlayarak öğeleri tek tek okumak anlamına gelir.
Bağlı liste yalnızca sıralı erişim yapabilir. Bağlı listedeki 10. elemana erişmek istiyorsanız önce ilk 9 öğeye erişmelisiniz. Rastgele erişim ise doğrudan 10. elemana erişebileceğiniz anlamına gelir.
Diziler rastgele erişim sağladıkları için okuma işleminde oldukça hızlıdırlar. Birçok kullanım durumu rastgele erişime ihtiyaç duyar. Bu nedenle dizi kullanımı yaygındır.
Özet
- Algoritma hızı saniye cinsinden ölçülmez
- Dizi kullandığınızda tüm öğeler hafızada yan yana saklanır
- Bağlı listelerde bir öğenin adresi önceki öğe ile birlikte saklanır
- Diziler okuma işleminde daha hızlıdırlar.
- Bağlı listeler ekleme ve silme işleminde daha hızlıdırlar.
Kaynaklar
Umarım sizin için faydalı bir yazı olmuştur. Sağlıcakla kalın.
