Veri Yapıları: Python Örnekleriyle Kapsamlı Bir Rehber

Veri yapıları hem dijital hem de fiziksel dünyada vardır. Bir sözlük, verilerin bir kitap içinde alfabetik sırayla düzenlenmiş sözcük tanımlarından oluştuğu fiziksel bir veri yapısı örneğidir. Bu düzenleme belirli bir sorguyu mümkün kılar: Bir kelime verildiğinde, tanımına bakılabilir.

Özünde veri yapısı, belirli türdeki sorguları ve işlemleri kolaylaştıracak şekilde verileri düzenleme yöntemidir.

Önce diziler, listeler, kuyruklar ve yığınlar gibi doğrusal veri yapılarıyla başlayacağız. Ardından doğrusal ve doğrusal olmayan yapılar arasındaki farkı açıklayıp karma tablolar, ağaçlar ve grafiklere dalacağız.

Daha fazlasını öğrenmek isterseniz, Python'da veri yapıları ve algoritmalar kursuna göz atın.

Diziler

Diziler, birçok programlama dilinde bulunan temel veri yapılarıdır. Bellekte sabit sayıda (N) değeri art arda depolamayı sağlarlar.

Dizi öğeleri, ilk öğe 0 indeksinde ve son öğe (N-1) indeksinde olacak şekilde indekslenir.

Aşağıdaki işlemlere izin verirler:

1. Belirli bir indeksteki değeri okumak.
2. Belirli bir indeksteki değeri güncellemek.
3. Depolanan tüm değerler üzerinde yineleme yapmak.
4. Dizinin boyutunu elde etmek.

Diziler, depolanacak değerlerin sayısının önceden bilindiği ve başlıca işlemlerin belirli indekslerde veri okuma/yazma olduğu senaryolarda son derece etkilidir.

Aralık ayı için günlük sıcaklık ölçümlerini depolamanız gereken bir senaryoyu düşünün. Kullanıcıların belirli bir günün sıcaklığını alabilmesini ve ay boyunca çeşitli istatistiksel analizler yapabilmesini isteyebilirsiniz.

Aralık ayındaki gün sayısı önceden 31 olarak bilindiğinden, diziler sıcaklık ölçümlerini depolamak için mükemmel bir seçimdir. Başlangıçta 31 boş konumlu bir dizi oluşturulur. Ardından her sıcaklık ölçümü alındığında, ilgili günün sıcaklığı karşılık gelen dizi indeksine atanır: 1. gün 0. indekse, 2. gün 1. indekse ve bu şekilde 31. gün 30. indekse kaydedilir.

İlgili indekse erişerek belirli bir günün sıcaklığı alınabilir. Ortalama sıcaklık gibi istatistikler, tüm öğeler üzerinde yineleme yapıp kümülatif bir toplam tutulduktan sonra dizinin boyutuna bölünerek belirlenebilir.

Diziler Python'da yerel olarak bulunmaz. Çeşitli veri türlerinin altında kullanılan yapıdırlar ancak dil tarafından doğrudan desteklenmezler. Dizileri açıkça kullanmak için, bir dizi uygulaması sunan array gibi kütüphanelerden yararlanılabilir. Ancak çoğu durumda dizi gerektiren durumlarda sabit boyutlu bir liste kullanmak daha pratiktir. Listeler esnektir ve Python'un temel işlevselliğinin bir parçasıdır; bunu az sonra ele alacağız.

31 öğeden oluşan ve her biri None ile başlatılan bir diziyi simüle etmek için [None] * 31 kullanarak bir liste oluşturabiliriz. Burada None, henüz herhangi bir sıcaklık ölçümü kaydedilmediğini belirtir.

december_temperatures = [None] * 31

Belirli bir indeksteki değeri ayarlamak için december_temperatures[index] kullanırız; burada index 0 ile 30 arasındaki bir sayıdır. Örneğin, ilk günün sıcaklığını (0. indekste saklanır) kaydetmek için şöyle yaparız:

december_temperatures[0] = 15

Bir sıcaklığa erişmek de benzer şekilde basittir: december_temperatures[index] kullanılır.

print(december_temperatures[0])

15

Listeler

Şimdi de Aralık'a odaklanmak yerine, belirli bir süre boyunca periyodik sıcaklık ölçümleri almak için bir yere sensör kurduğumuzu hayal edin. Bu senaryoda, oluşturulduğunda sabit boyutlu olduğu için dizi kullanmak en iyi seçenek olmayabilir; alan tükenebilir.

Bu durumda daha uygun veri yapısı liste olur. İki tür liste vardır:

• Dizi listeleri
• Bağlı listeler

Dizi listeleri

Dizi listeleri, dizilerin daha esnek bir versiyonu olarak görülebilir. Dizilerin yaptığı her şeyi yapabilirler ve ayrıca yeni değerler ekleyebilirler; dolayısıyla boyutları oluşturulurken sabit değildir. Python'da dizi listeleri list() kullanmaya karşılık gelir.

Uygulamaları, alan tükendiğinde genişletilen bir dizi kullanmaya dayanır; bu nedenle adı dizi listesidir. Ancak daha önce öğrendiğimiz gibi diziler büyüyemez; peki bu nasıl mümkün oluyor?

Bir dizi listesinin alttaki dizisi dolduğunda ve yeni bir değer eklemek istediğimizde, perde arkasında daha büyük bir dizi oluşturulur. Önceki tüm değerler bu yeni, daha büyük diziye kopyalanır. Ardından yeni değer, yeni dizideki ilk uygun konuma eklenir.

Bu diziye 71 değerini eklemek istediğimizi hayal edin:

Bu işlem şu şekilde gerçekleştirilebilir:

Bu işlem her yapıldığında ayrılan yeni alan miktarı, dizi listesinin performansı için kritiktir. Eğer her eklemede yalnızca eklenen yeni değer için bir konum içeren bir dizi oluştursaydık, bu her ekleme işleminin var olan verinin tamamının kopyalanmasını gerektireceği anlamına gelirdi. Bu son derece verimsiz olurdu—sırf yeni bir kayıt eklemek için milyonlarca kaydı kopyalamak zorunda olduğunuzu hayal edin.

Bunun yerine yaygın strateji, ihtiyaç duyulduğunda dizi boyutunu iki katına çıkarmaktır. Bu yaklaşım, zamanla bu ek kopyalama adımlarının etkisini nötralize eder.

Python listesine öğe eklemek için .append() metodunu kullanırız. İşte boş bir liste oluşturup bir sıcaklık ölçümü eklemenin örneği:

temperatures = []
temperatures.append(35)

Bağlı listeler

Bilgisayarda verileri yapılandırmak için değerleri birbirleriyle ilişkilendirmenin bir yoluna ihtiyacımız vardır. Diziler bunu, bitişik bellek konumlarını — yani doğrudan yan yana olan bellek konumlarını — ayırıp değerleri sıralı şekilde depolayarak başarır. Bunu bir sokaktaki evler sırası gibi düşünün: her evin benzersiz bir adresi (indeksi) vardır ve fiziksel olarak yan yanadırlar.

Ancak bu, verileri düzenlemenin tek yolu değildir. Alternatif bir yöntem, düğüm tabanlı bir yapı kullanmaktır.

Düğüm, bir değeri ve diğer düğümlere referansları saklayan bir nesnedir. Örneğin, düğümleri kullanarak liste benzeri bir yapı oluşturmak için, bir değeri ve listedeki sonraki elemana bir referans tutan bir düğüme sahip olabiliriz. Python'da bu bir sınıfla uygulanabilir:

class Node:
    def __init__(self, value, next_node):
        self.value = value
        self.next_node = next_node

Bu yaklaşımla, next_node referansı aracılığıyla değerleri birbirine bağlayarak bir liste oluşturabiliriz. İşte 42, 17 ve 37 değerlerinden oluşan bir liste oluşturan bir kod parçası:

node_37 = Node(37, None) # 37'den sonra düğüm yok, bu yüzden next_node None
node_17 = Node(17, node_37)
node_42 = Node(42, node_17)

Düğümleri bu şekilde elle bağlamak pratik değildir. Gerçek uygulamada, listenin ilk ve son düğümlerine referansları tutan başka bir sınıf oluşturmak gerekir. Yeni bir değer eklemek için:

1. İstenen değeri içeren bir düğüm oluştururuz.
2. Bu yeni düğümü, mevcut son düğümün sonraki düğümü olarak ayarlarız.
3. Son düğüm referansını yeni eklenen bu düğüme güncelleriz.

71 değerini örnek dizimize eklemek istediğimizi düşünün:

Bu işlem şu şekilde gerçekleştirilebilir:

class LinkedList:
    def __init__(self):
        self.first_node = None
        self.last_node = None

    def append(self, value):
        node = Node(value, None)
        if self.first_node is None:
            self.first_node = node
            self.last_node = node
        else:
            self.last_node.next_node = node
            self.last_node = node

Dizi listelerinde olduğu gibi, değerlere indeksleriyle doğrudan erişemeyiz. Belirli bir indeksteki değeri okumak için ilk düğümden başlamamız ve istenen indekse ulaşana kadar düğümden düğüme sıralı olarak ilerlememiz gerekir. Bu süreç doğrudan erişime göre oldukça yavaştır. Listede milyonlarca değer depolanmışsa, belirli bir indekse ulaşmak için bellekte milyonlarca değeri okumamız gerekebilir.

Bağlı listenin avantajı, listenin başından veya sonundan öğeleri anında ekleyip çıkarabilmemizdir. Bu yetenek, sırada tartışacağımız iki yeni veri yapısının—kuyruklar ve yığınlar—uygulanmasını mümkün kılar.

Kuyruklar

Müşteri siparişlerini kaydeden ve mutfağa ileten bir restoran uygulaması geliştirdiğinizi hayal edin. Müşteriler restorana geldiklerinde sipariş vermek için sıraya girecek ve geliş sırasına göre hizmet bekleyeceklerdir. Bu, sıradaki ilk müşterinin siparişini ilk alması ve son müşterinin son alması gerektiği anlamına gelir.

Mutfağa geldiğimizde, şef aynı anda tek bir siparişe odaklanmayı tercih eder; bu yüzden uygulama yalnızca mevcut siparişi göstermelidir. Bir sipariş hazırlanıp gönderildiğinde, sıradaki bir sonraki sipariş görüntülenmelidir.

Yukarıdaki gereksinimleri, aşağıdaki işlemleri destekleyen bir veri yapısına ihtiyaç olarak yorumlayabiliriz:

1. Öğe eklemek.
2. İlk eklenen öğeyi görüntülemek.
3. İlk eklenen öğeyi kaldırmak.

Bu işlemler tam olarak kuyruğun sunduklarıdır. Kuyruk, bağlı liste kullanılarak uygulanabilir; öğeler listeye eklenerek kuyruğa alınır. Öğeler geliş zamanına göre sıralandığından, her zaman ilk düğüm bir sonraki hizmet verilecek olandır.

Yukarıdaki siparişler kuyrukta şu şekilde saklanırdı:

Bir sipariş hazır olduğunda, bir sonraki düğüm varsa ilk öğeyi next_node'una güncelleyerek kaldırılabilir. Yeni ilk düğüm, ikinci düğüm olur:

Kuyruklar, ilk giren ilk çıkar (FIFO) veri yapısı olarak tanımlanır; çünkü ilk eklenen öğe ilk kaldırılan öğedir. Restoran örneğimizde, ilk gelen müşteri ilk hizmet verilen (ve şefin listesinden çıkarılan) müşteridir.

Python'da kuyruk kullanmak için collections modülündeki deque koleksiyonunu kullanabiliriz. Aşağıda bu modülü içe aktararak boş bir kuyruk oluşturuyoruz:

from collections import deque
orders = deque()

Kuyruğun sonuna yeni bir öğe eklemek için .append() metodunu kullanırız:

orders.append("burger")
orders.append("sunday")
orders.append("fries")

Bir sonraki siparişi kuyruk başından alıp kaldırmak için .popleft() metodunu kullanırız:

orders.append("burger")
orders.append("sunday")
orders.append("fries")

burger
sunday
fries

Yığınlar

Bazı durumlarda, kuyruğun davranışının tersini isteriz—en son eklenen öğeyi takip etmek isteriz.

Bunu örneklemek için, bir resim düzenleyiciye geri alma özelliği eklemekle görevlendirildiğinizi düşünün. Bu, kullanıcının eylemlerini izlemeyi ve en son işlemlere erişim sağlamayı gerektirir. Çünkü geri alma işlevleri genellikle son yapılan işlemden başlayarak ilkine doğru işlemleri tersine çevirir.

Yığın, tam olarak şu işlemleri destekleyen bir veri yapısıdır:

1. Öğe eklemek.
2. En son eklenen öğeyi görüntülemek.
3. En son eklenen öğeyi kaldırmak.

Kuyruklar gibi, yığınlar da bağlı liste kullanılarak uygulanabilir. Öğe ekleme yine listeye ekleme yaparak gerçekleştirilir. Ancak ilgimiz listedeki ilk öğeden ziyade son öğeye kayar. En son öğeyi almak için listenin son öğesine bakarız. Son öğeyi kaldırmak için de o öğeyi silmemiz gerekir.

Düğüm yapımızda yalnızca sonraki düğümü izliyorduk. Son öğeyi kaldırmayı kolaylaştırmak için, ondan önce gelen öğeye erişmemiz, onun next_node'unu silmemiz ve bu düğümü son düğüm olarak terfi ettirmemiz gerekir. Bunu, her düğümün bir önceki düğümünü de izlemek üzere düğüm yapısını değiştirerek başarabiliriz. Böyle bir bağlı listeye çift bağlı liste denir.

Yığınlar, son giren ilk çıkar (LIFO) veri yapısı olarak tanımlanır; çünkü en son eklenen öğe ilk kaldırılan ögedir.

Python'da yığın kullanmak için aynı deque koleksiyonunu kullanabiliriz. Yeni öğeler eklemek için .append() metodunu kullanırız:

from collections import deque
actions = deque()

actions.append("crop")
actions.append("desaturate")
actions.append("resize")

Yığının tepesinden bir sonraki öğeyi alıp kaldırmak için .pop() metodunu kullanırız:

print(actions.pop())
print(actions.pop())
print(actions.pop())

resize
desaturate
crop

Doğrusal ve Doğrusal Olmayan Veri Yapıları

Şimdiye dek beş veri yapısını inceledik: diziler, dizi listeleri, bağlı listeler, kuyruklar ve yığınlar. Bunların her biri, öğelerin bir sırada düzenlendiği ve her öğenin net bir önceki ve sonraki öğeye sahip olduğu için doğrusal veri yapısıdır.

Şimdi odağımızı doğrusal olmayan veri yapılarına kaydıracağız. Doğrusal türlerin aksine, bu yapılar öğeleri doğrusal bir biçimde yan yana düzenlemez. Dolayısıyla tanımlı bir önceki ve sonraki öğe kavramına sahip değildirler. Bunun yerine öğeler arasında farklı türde ilişkiler kurarlar.

Bu özellik, onları yalnızca verileri bellekte depolamaya hizmet etmekten ziyade, veriler üzerinde özel sorguları yüksek verimle çalıştırmaya özellikle uygun kılar.

Karma tablolar

Bu makaleye, gerçek hayattan bir veri yapısı örneği olan sözlüklerden bahsederek başladık. Verileri belirli bir alanla aranabilecek şekilde düzenlemek (örneğin bir kelime verildiğinde tanımına bakmak) genelde son derece faydalıdır; bu nedenle bilgisayar bilimciler de bunu mümkün kılan bir veri yapısı icat etmiştir.

Bu veri yapısını anlamak için sanal bir sözlük oluşturarak — yani şunları yapabildiğimiz bir veri yapısı oluşturarak — nasıl ilerleyebileceğimize bakalım:

1. Bir kelimeyi tanımıyla birlikte eklemek.
2. Bir kelime verildiğinde, tanımını aramak.

Aralık ayı boyunca sıcaklık kaydetme örneğini hatırlayın. Her güne karşılık gelen 31 öğeli bir dizi kullanmış ve sıcaklıkları ilgili indekslerde depolamıştık. Bu yaklaşım, herhangi bir günün sıcaklığını etkin şekilde bulmayı sağlar.

Bu durum, (day, temperature) veri çiftleriyle çalışmaya benzer; burada amaç günü belirterek temperature'ı elde etmektir. Benzer şekilde, sözlükler durumunda (word, definition) çiftleriyle çalışır ve bir word verildiğinde definition'ı bulmayı hedefleriz.

Bu tür çiftlere anahtar-değer çiftleri ya da kayıtlar denir. Anahtar, arama sorgusunda kullanılan parametredir; değer ise o sorgunun sonucudur.

Sözlük probleminde dizi kullanmamızı engelleyen şey, anahtarlarımızın sayılar yerine dizgiler olmasıdır. Sayısal anahtarlarla, değerleri karşılık gelen indekslerde konumlandırarak anahtarlarla değerleri doğrudan bir diziyle ilişkilendirebiliriz.

Bu sorunu çözmek için önce kelimeleri sayılara dönüştürmemiz gerekir. Bu dönüşümü yapan fonksiyona karma fonksiyonu denir. Böyle bir fonksiyon oluşturmanın birçok yolu vardır. Örneğin, harflere sayısal değerler atayabiliriz; a = 1, b = 2, c = 3 gibi ve ardından bu değerleri toplayabiliriz.

Örneğin data kelimesi 4 + 1 + 20 + 1 = 26 olarak hesaplanır. Ancak bu fonksiyonun birazdan tartışacağımız sakıncaları vardır. İyi bir karma fonksiyonunun nasıl tasarlanacağı bu makalenin kapsamı dışındadır; neyse ki Python, bu işi verimli şekilde yapan hash() fonksiyonunu sağlar.

hash("data")

-6138587229816301269

Yukarıdaki örnekte karma fonksiyonunun negatif bir sayı ürettiğini fark etmiş olabilirsiniz. Dizi pozitif indekslerinin 0 ile N - 1 arasında olduğunu unutmayın. Anahtarları sayılara dönüştürdükten sonra, modül operatörü % kullanılarak 0 ile N - 1 aralığına eşlenebilirler (bölmenin kalanı; örneğin 10 % 3 işlemi 1 döndürür).

Bir not olarak, Python’un hash() fonksiyonu farklı program çalıştırmalarında farklı değerler döndürebilir. Yalnızca aynı program çalışması içinde deterministiktir; yani programı birden çok kez çalıştırırsanız aynı nesne için farklı karma değerleri görebilirsiniz.

100 öğe içeren bir dizi düşünün. "data" dizgesine karşılık gelen indeksi bulmak için şöyle ilerleriz:

hash("data") % 100

31

Karma tablo veri yapısı özünde, anahtarlara bir karma fonksiyonu uygulayarak elde edilen indekslerde anahtar-değer çiftlerini depolayan büyük bir dizidir.

Yer kısıtlamaları nedeniyle yukarıdaki diyagramda tanımı temsil etmek için yalnızca "def" kısaltması yer almaktadır. Pratikte ise her kaydın ikinci öğesi, kelimenin tam tanımı olur.

Dikkate alınması gereken bir başka önemli husus daha vardır. 100'den çok daha fazla kelime olduğu için kelime eklemeye devam edersek, farklı kelimelerin kaçınılmaz olarak aynı karma değeri ürettiğini görürüz. Bunu çözmek için, her bir dizi öğesini tek bir anahtar-değer çiftiyle sınırlamak yerine, aynı karma değerini paylaşan tüm kayıtları depolamak için bir bağlı liste kullanırız.

İki kayıt aynı karmayı ürettiğinde buna çakışma denir. Bu durum, arama sürecini biraz değiştirir. Karma kodu hesaplandıktan sonra doğru kaydı bulmak için listeyi dolaşmak gerekir. Bu yaklaşım arama işlemini yavaşlatsa da, yeterince büyük bir başlangıç dizi boyutu (100'den büyük) ve iyi tasarlanmış bir karma fonksiyonu kullanmanın çakışmaların etkisini önemli ölçüde hafiflettiği gösterilebilir. Sonuç olarak verimlilik, neredeyse bir dizi kadar yüksek kalır.

Etkin şekilde tasarlanmış bir karma fonksiyonu için, aynı karmayı üreten farklı değerler bulmak nadir olmalıdır. Bu nedenle bir kelimedeki karakterlerin sayısal değerlerini sadece toplayan basit bir karma fonksiyonu ideal değildir. Harfleri aynı olan herhangi iki kelime, sıraları ne olursa olsun, aynı karma kodunu verir. Örneğin “listen” ve “silent” aynı karmayı üretir. Buna karşılık Python’un yerleşik karma fonksiyonu çok daha sağlamdır ve çakışmaları en aza indirmeye özel olarak tasarlanmıştır.

Karma tablolar, mevcut en önemli veri yapıları arasında sayılır. Son derece verimli ve çok yönlüdürler. Python'da dict() sınıfı ile uygulanırlar. Bir sözlüğe benzemesi nedeniyle Python'da bu veri yapısı karma tablo yerine sözlük olarak adlandırılır.

Basitlik adına, örneğimiz ekleme ve arama işlemlerine odaklanıyor. Genel olarak sözlükler daha esnektir ve silme gibi ek işlemleri de destekler. Python'da boş bir sözlük (karma tablo) oluşturmak için {} kullanabilirsiniz; örneğin:

word_definitions = {}
word_definitions["data"] = "Facts or information."

Bir kelimenin tanımına, kelimeyi anahtar olarak kullanarak şu şekilde erişebilirsiniz:

print(word_definitions["data"])

Facts or information.

Ağaçlar

Bir emlak ajansı için web sitesi geliştirdiğinizi hayal edin. Göreviniz, kullanıcıların ilanları fiyata göre filtrelemesine olanak tanıyan bir özellik oluşturmak. Özellik şunlara izin vermelidir:

1. En ucuz ilanı bulmak.
2. En pahalı ilanı bulmak.
3. Belirli bir fiyatın altındaki tüm ilanları bulmak.

Genellikle bu süreç, tüm ev ilanlarının taranmasını ve istenen fiyat aralığının dışındaki ilanların elenmesini içerir. Ancak hedefimiz, ilgili ilanları bulmak için tüm veri kümesini incelemeyi gerektirmeyecek şekilde daha ölçeklenebilir bir çözüm geliştirmektir. Ağaçlar, bu tür sorguları yanıtlamak için mükemmel bir veri yapısıdır.

Ağaçlar, bağlı listeler gibi düğüm tabanlı veri yapılarıdır. Ancak önceki ve sonraki referanslar yerine, her düğüm bir değer ile iki referans tutar: sol düğüm ve sağ düğüm.

Emlak ajansı web sitesi örneğimizde, her düğüm bir mülk ilanını temsil eder. Fiyatla ilgili sorguları optimize etmek için şu kuralı belirleyeceğiz: daha düşük fiyatlı ilanlar her zaman bir düğümün solunda, daha yüksek fiyatlı ilanlar ise her zaman sağında saklanacaktır.

Somut bir örnek olarak, 42, 17, 73, 4, 22 ve 89 değerlerini tutan aşağıdaki ağacı ele alalım.

Her düğüm için, soldaki tüm düğümler daha küçük değerlere, sağdakiler ise daha büyük değerlere sahiptir. Bu özelliği sağlayan ağaca ikili arama ağacı (BST) denir. İkili denmesinin nedeni, her düğümün en fazla iki başka düğüme (çocuklara) referans vermesidir. Terimdeki arama kısmı ise, sol ve sağ çocuklardaki sıralama özelliğinin ağacı verimli şekilde aramayı mümkün kılmasından gelir.

BST'nin en ucuz ve en pahalı ilanları hızlıca bulmaya nasıl yardımcı olduğunu şimdiden görebiliyoruz. Değer sıralaması sayesinde en ucuz her zaman en soldaki, en pahalı ise her zaman en sağdaki düğümdür.

Bu, verilerin çoğunu incelemeden onları bulabileceğimiz anlamına gelir. En üstteki düğümden, yani kök düğümden başlayarak, minimumu bulmak için sürekli sol bağlantıları, maximumu bulmak için sağ bağlantıları izleriz. Bu, yalnızca kökten minimuma ve kökten maximuma giden yol üzerindeki düğümlerin incelenmesi gerektiği anlamına gelir.

En az 50 değere sahip tüm düğümleri bulmak istediğimizi varsayalım. Bunu başarmak için şu adımları atabiliriz:

• Kökten başlayarak hedefimiz olan 50'yi kökün değeri 42 ile karşılaştırırız.
• 50'nin daha büyük olduğunu görerek, kökün ve solundaki tüm düğümlerin daha küçük değerler içerdiğini anlarız. Dolayısıyla onları göz ardı edebiliriz.
• Ardından kökün sağındaki 73 düğümüne geçeriz. Karşılaştırınca 50'nin 73'ten küçük olduğunu buluruz. Bu, 73 düğümünün sağındaki tüm düğümlerin kriterlerimizi karşıladığına işaret eder.
• Ancak 73'ün sol çocuğu olmadığı için aramamız orada sona erer.

BST'lerin sorguları önemli ölçüde hızlandırabileceğini şimdiden görebiliyoruz. Bu küçük örnekte bile verilerin yarısını incelemekten kaçındık.

Genel olarak, verilen bir aralığa uyan tüm düğümleri bir BST'de belirlemek, sonuç sayısına yakın sayıda düğümün incelenmesini gerektirir. Bu, her bir veri noktasını incelemeye kıyasla büyük bir avantajdır. 1.000.000 ilan ve yalnızca 10 sonuç döndüren bir sorgu olduğunu hayal edin. Bir liste kullanıldığında, aralığa uymayanları elemek için bir milyon ilanın incelenmesi gerekir. Bir BST ile yaklaşık 10 ilan incelenir. Bu, 100.000 kat hız artışı demektir.

Bir BST'nin verimliliği, ağacın dengesine büyük ölçüde bağlıdır. Önceki değerleri küçükten büyüğe — 4, 17, 22, 42, 73 ve ardından 89 — eklersek, aşağıda gösterildiği gibi dengesiz bir ağaçla karşılaşabiliriz:

Bir BST'de maksimum değeri bulmak için kökten başlayıp sağ bağlantıları, olmayan bir sağ bağlantıya sahip bir düğüme ulaşana kadar izlediğimizi hatırlayın. Yukarıdaki diyagramda olduğu gibi dengesiz bir ağaçta bu işlem, her bir düğümün incelenmesini gerektirir. İdeal olarak, düğümlerin sol ve sağ arasında eşit dağılmasını isteriz. Bu dengenin nasıl sürekli sağlanacağına ilişkin ayrıntılar bu makalenin kapsamı dışındadır. Bu tür dengeyi korumasıyla bilinen bir ikili arama ağacı türü AVL ağacı olarak adlandırılır.

avltree paketi, bir AVL ağacı uygulaması sağlar. Aşağıdaki kod parçası, bu ev ilanları veri kümesi üzerinde, bu ABD Emlak Veri Kümesi'nin temizlenmiş bir alt kümesiyle nasıl kullanılabileceğini gösterir.

import csv
from avltree import AvlTree as Tree

# İlanlar CSV verisini yükleyin
with open("listings.csv", "rt") as f:
    reader = csv.reader(f)
    listings = list(reader)

# Fiyat sütununa (sütun indeksi 2) göre ağacı oluşturun
tree = Tree()
for listing in listings[1:]:
    price = float(listing[2])
    tree[price] = listing

# En ucuz ilan fiyatını gösterin
print("Cheapest:", tree.minimum())

# En pahalı ilan fiyatını gösterin
print("Most expensive:", tree.maximum())

# Fiyatı 100.000 ile 110.000 arasında olan ilanların sayısını gösterin
listings_in_range = list(tree.between(100000, 110000))
print("Num listings between 100000 and 110000:", len(listings_in_range))

Cheapest: 50017.0
Most expensive: 19999900.0
Num listings between 100000 and 110000: 403

Önce csv modülünü kullanarak listings.csv veri kümesini okuyoruz. Ardından fiyat sütununa dayalı bir AVL ağacı oluşturuyoruz. Son olarak minimum fiyatı, maksimum fiyatı ve 100.000 ile 110.000 $ arasındaki ilan sayısını belirlemek için minimum(), maximum() ve between() metodlarını kullanıyoruz.

Grafikler

Bu makalede ele alacağımız son veri yapısı grafiktir.

Bir sosyal medya platformundan veri analiz ettiğinizi varsayalım. Bu veriler, kullanıcıların bir listesinden ve aralarındaki arkadaşlıklardan oluşuyor ve amacınız sosyal ağ içindeki toplulukları belirlemek. Topluluk kavramı çeşitli şekillerde tanımlanabilse de genellikle, grup içinde anlamlı sayıda arkadaşlığın bulunduğu kullanıcılar topluluğunu ifade eder.

Elimizde varlıklar ve bu varlık çiftleri arasındaki ilişkiler olduğunda veriyi temsil etmek için grafikler ideal veri yapısıdır. Örneğimizde varlıklar kullanıcılar, ilişkiler ise arkadaşlıklarıdır.

Grafikler düğüm tabanlı yapılardır. Ancak düğümler arasında doğrusal veya hiyerarşik bağlantılar sergileyen bağlı listeler ve ağaçların aksine, bir grafikte herhangi bir düğüm, birden çok başka düğüme bağlanabilir. Düğümler arasındaki bu bağlantılara kenar denir ve aralarındaki ilişkileri belirtir.

Sosyal ağ örneğimizde her kullanıcıyı bir düğüm olarak görselleştirebiliriz. İlgili kullanıcılar arasındaki arkadaşlığı belirtmek için iki düğüm arasında bir kenar çizilebilir.

Yukarıdaki diyagram, küçük bir sosyal ağ içindeki arkadaşlıkları temsil eden bir grafiği göstermektedir. Düğümler kullanıcıları temsil eder ve adlarıyla etiketlenmiştir; kenarlar ise arkadaşlıkları temsil eder. Örneğin Anna'nın Steve, Claire ve Jack ile arkadaş olması, onun düğümünün bu kişilerin düğümlerine bağlandığı anlamına gelir.

Bir grafik veri yapısının desteklemesi gereken işlemler şunlardır:

1. Yeni bir düğüm eklemek.
2. İki düğümü bir kenarla bağlamak.
3. Belirli bir düğüme bağlı tüm düğümleri almak.

Grafik uygulamasının yaygın bir yolu, karma tablo ve listeler kullanmaktır. Her düğüm için bir kayıt içeren bir karma tablo oluşturulur. Her kaydın anahtarı düğümün kendisi, değeri ise o düğümün bağlı olduğu tüm düğümleri içeren bir listedir.

networkx paketi, grafik oluşturma ve üzerinde işlem yapma için bir Python uygulaması sunar. Ayrıca networkx kütüphanesi, topluluk tespiti de dahil olmak üzere geniş bir grafik algoritmaları yelpazesini kapsar. Yukarıda bahsedilen grafiği oluşturmak ve yaygın bir topluluk tespiti algoritmasını uygulayarak sonuçları görmek için bunu kullanalım.

Grafik oluşturmayı başlatmak için networkx kütüphanesini içe aktarır ve boş bir grafik başlatırız:

import networkx as nx
G = nx.Graph()

Düğümler add_node() metoduyla eklenebilir.

G.add_node("Anna")
G.add_node("Steve")
G.add_node("Jack")
G.add_node("Claire")
G.add_node("Bob")
G.add_node("Jane")
G.add_node("John")
G.add_node("Rute")
G.add_node("Alex")

Kenarlar add_edge() metoduyla eklenebilir.

G.add_edge("Anna", "Steve")
G.add_edge("Anna", "Jack")
G.add_edge("Anna", "Claire")
G.add_edge("Steve", "Claire")
G.add_edge("Claire", "Jack")
G.add_edge("Jack", "Bob")
G.add_edge("Bob", "John")
G.add_edge("Bob", "Jane")
G.add_edge("John", "Jane")
G.add_edge("Rute", "Alex")

Grafiğimizi oluşturduktan sonra içindeki toplulukları hesaplayabiliriz. Topluluk tespiti için tasarlanmış çeşitli algoritmalar vardır; bu örnekte Louvain yöntemini kullanacağız. Topluluk tespiti algoritmaları networkx'in community alt paketinde bulunur. Özellikle louvain_communities() fonksiyonuna odaklanacağız.

Şu şekilde kullanılır:

communities = nx.community.louvain_communities(G)
print(communities)

[{'Jack', 'Claire', 'Anna', 'Steve'}, {'Bob', 'John', 'Jane'}, {'Rute', 'Alex'}]

Çıktı, her bir kümenin bir topluluğu temsil ettiği kümeler listesidir. Algoritmanın üç topluluk tespit ettiğini görüyoruz; bu da grafiğin yapısı göz önüne alındığında beklentilerimizle örtüşüyor.

Grafikler hakkında daha fazla bilgi edinmek için, Python'da Dijkstra algoritmasını nasıl uygulayacağınızı öğrenin.

Doğru Veri Yapısını Seçmek

Her veri yapısını tanıtırken, desteklediği işlemlerin bir listesini sunduk. Bu işlemler, o veri yapısının ne zaman kullanılacağına ilişkin kılavuz görevi görür; çünkü söz konusu işlemleri verimli şekilde gerçekleştirecek biçimde tasarlanmışlardır.

Örneğin Python list() öğe kaldırma gibi ek işlemleri de destekler. Ancak bu ek işlemler, dizi listesinin mükemmel olduğu şeyler değildir. Özellikle, bir öğeyi listenin ortasından kaldırmak, kaldırılan öğe dışındaki tüm verilerin yeni bir listeye kopyalanmasını gerektirir ve bu çok zaman alabilir.

Veriler doğal olarak sayılarla indeksleniyorsa ve giriş sayısı biliniyorsa (örneğin bir ayın günleri), genellikle dizi tercih edilir. Daha genel indeksleme veya dinamik veri kümeleri için sözlükler iyi bir alternatif çözümdür.

Verileri art arda, bir seferde bir giriş olacak şekilde işlemek için, istenen işleme sırasına bağlı olarak sıklıkla kuyruklar veya yığınlar kullanılır.

Veriler üzerinde, belirli bir aralıktaki tüm girişleri ya da uç değerleri bulmak gibi daha karmaşık sorgular yapmak istediğimizde genellikle ağaçlar yanıt olur.

Son olarak, veri noktaları çiftleri arasında bir ilişki olduğunda, bu ilişkileri depolamak ve temsil etmek için grafik etkili bir yoldur. Bu tür ikili ilişki içeren veri kümeleri hakkında yaygın soruları yanıtlamamızı sağlayan grafik algoritmaları vardır.

Veri yapıları geniş bir alandır ve burada yalnızca buzdağının görünen kısmını ele aldık. Bazı durumlarda çözüm, ele alınan soruna tamamen uyarlanmış yepyeni bir veri yapısı tasarlamaktır. Yine de, bu makalede tartışılan veri yapılarıyla aşina olmak, veriyle ilgili sorunlarınızı çözerken sizi doğru yöne yönlendirecektir.

Sonuç

Bu makalede, veri yapılarınin, bilgiyi verimli şekilde almayı kolaylaştırmak için verileri belirli biçimlerde düzenleme yöntemleri olduğunu öğrendik.

İki temel veri yapısı türü vardır: dizi tabanlı (örneğin karma tablolar) ve düğüm tabanlı (örneğin grafikler) yapılar.

Diziler, kuyruklar ve yığınlar gibi doğrusal yapılar, öğeleri ardışık olarak, birbiri ardına düzenler. Buna karşılık, karma tablolar, ağaçlar ve grafikler gibi doğrusal olmayan yapılar, verileri verinin içindeki ilişkilere dayalı olarak düzenler.

Uygun veri yapısının seçimi, gerçekleştirilecek sorguların niteliğine bağlıdır.

Python'daki çeşitli veri yapıları hakkında bilgi edinmek isterseniz, Python veri yapıları üzerine bu eğiticiye göz atın.