2 dk, tahmini okuma süresi
Dizi Veri Türleri ve Analiz
En Son Güncelleme: 15 Ekim, 2022§Bir Açıklama ile Başlayalım
Dizi, sıralanmış ve dizine alınmış yapılandırılmış bir veridir. Diziler her dilde farklı şekillerde oluşturulur, ancak hepsi hemen hemen aynı şekilde indekslenir. Bu yazıda birkaç dilde dizi veri yapısından ve bunlarla nasıl çalışabileceğimizden bahsedeceğim.
§Diziyi Başlangıç Boyutu ve Türüyle Tanımlama
Dizileri nasıl tanımladığımız değişebilir ve performansı etkileyebilir. Python, JavaScript ve Java gibi dillerdeki örnekler için, dizinin başlangıç boyutunu tanımlamamız gerekmez. Python ve JavaScript'te farklı veri türlerini aynı dizi yapısında tutabiliriz. Ancak Java'da dizide tutacağımız değerlerin türünü tanımlamamız gerekiyor.
Bir dizi için bir başlangıç boyutu tanımlamadan, dizimize daha fazla öğe ekleyerek dizimizin boyutunu kolayca artıralım. Bunun nedeni, perde arkasında dilimizin bellek tahsisinin kendisini zorluyor olmasıdır. Dizinin boyutlarını hızlı bir şekilde büyütmenin birçok yöntemi vardır. Boyut tanımlamamız gereken dillerle çalışmayı sevdiğim yöntem, dizinin boyutunu kontrol etmek ve gerekirse boyutu iki katına çıkarmak. Python'da dinamik bir dizinin davranışını taklit edecek kodu yazdım. Temelde python'da yerleşik olmasına rağmen, gerçekte nasıl çalıştığını görmek önemli diye düşünüyorum:
import ctypes
# Python, Java'daki gibi statik bir diziye sahip değil
class DynamicArray(object):
# the constructor
def __init__(self):
self.n = 0 # Dizinin içindeki gerçek eleman sayısı
self.capacity = 1 # başlangıç kapasitesi
self.A = self.make_array(self.capacity) # verilen kapasiteye sahip diziyi oluştur
# len(instance) örneğin uzunluğunu döndürür
def __len__(self):
return self.n
def __getitem__(self, k):
# dizide k dizini varsa:
if not 0 <= k < self.n:
return IndexError('Sınırların dışında! Ekleme yok')
return self.A[k] # tabiki varsa geri döndür
def append(self, ele):
# kapasiteye ulaşıldığında boyutu iki katına çıkar
if self.n == self.capacity:
self._resize(2*self.capacity)
self.A[self.n] = ele # öğeyi ekle
self.n += 1 # dizinin boyutunu bir artır
def insertAt(self, item, index): # belirli bir dizine ekle
if index < 0 or index > self.n:
# dizin negatif veya dizi boyutundan büyükse
print("Geçersiz dizin")
return
# boyut kapasiteye ulaşırsa tekrar
if self.n == self.capacity:
self._resize(2*self.capacity)
# boşluk oluşturmak için verilen indeksten sonra tüm öğeleri bir nokta sekiz hareket ettirmek, sağdan sola gitmek
for i in range(self.n-1, index-1, -1):
self.A[i+1] = self.A[i]
# sonunda öğeyi yerleştir
self.A[index] = item
self.n+=1
# dizinin sonundan sil
def delete(self):
# boş bir diziyi işlemeyelim
if self.n == 0:
print("Dizi boş")
return
# dizideki son öğeye 0 ver
self.A[self.n-1]
self.n -= 1
# belirli bir dizinde kaldırma gerçekleştir
def removeAt(self, index):
# insertAt metodu gibi
if self.n == 0:
print("Dizi boş")
if index < 0 or index >= self.n:
return IndexError("Endeks sınırların dışında! Silme yok")
# dizideki son öğeyse
if index == self.n -1:
self.A[index] = 0
self.n -= 1
return
for i in range(index, self.n-1):
# elemanları bir indeks sola taşımak
self.A[i] = self.A[i+1]
# bir eleman çıktı, bu yüzden diziyi kısalt
self.A[self.n-1] = 0
self.n -= 1
# Son olarak kapasite artışları için yeniden boyutlandırma yöntemi
# Her seferinde kapasiteyi ikiye katlıyoruz
def _resize(self, new_cap):
B = self.make_array(new_cap) # Yeni daha büyük dizi
# her şeyi yeni dizinin içine taşı
for k in range(self.n):
B[k] = self.A[k]
self.A = B
self.capacity = new_cap
def make_array(self, new_cap):
return (new_cap * ctypes.py_object)()
arr = DynamicArray()
arr.append(1)
arr.append(2)
arr.append(3)
arr.append(4)
arr.append(5)
arr.append(6)
print(len(arr))
Dinamik dizi işlemlerini uygulamak için bu kodu seçtiğiniz dilde yeniden oluşturabilir ve değiştirebilirsiniz. Örneğin, C veya Java'da.
C'de dizileri başlangıç boyutu ve türleri ile tanımlarız. Bu, hız ve bellek kullanımı açısından birçok fayda sağlar. Bu, C'nin genel olarak Python ve JavaScript'ten daha hızlı olmasının nedenlerinden biri.
Python'da ayrıca sabit diziler oluşturmak için array yöntemini kullanabiliriz (3.3 sürümünden beri):
import array
list = list(range(10))
arr = array.array('i', list)
arr # array('i', [0, 1, 2, 3, 4, 5, 6, 7, 8, 9])
i burada "integer" anlamına gelir. Bu, python'daki yerleşik listeler için daha yüksek performanslı bir seçenektir. Belki ileride kullanmayı düşünebilirsiniz. Ayrıca veri biliminde numpy gibi popüler çerçeveleri kullanırken başlangıç boyutları ve veri türleri ile diziler oluşturmanız gerekir. Örneğin:
import numpy as np
np.ones((2, 5), dtype=float)
Bu bize aşağıdaki yapıyı verecektir:
array([[ 1., 1., 1., 1., 1.],
[ 1., 1., 1., 1., 1.],
[ 1., 1., 1., 1., 1.]])
Aynı mantığı Python ve JavaScript'te uygulamak hala mümkündür. Örneğin, Python'da numpy kitaplığını kullanacaksanız
JavaScript, yazılan ve boyutlandırılmış bir dizi oluşturmamıza izin veren bir nesneye sahiptir. TypedArray, altta yatan ikili veri arabelleğini temsil eden ve dizileyen yapıyı açıklar geliştirici.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/ArrayBuffer). Javascript'te yazılan bir diziyi şu şekilde oluştururuz:
// Bayt cinsinden boyutunu ve içereceği veri türünü tanımlayarak
// yazılan bir dizi oluşturuyoruz.
const tp1 = new Int8Array(4); Int8Array [0, 0, 0, 0]
tp1[3] = 77;
console.log(tp1); Int8Array [0, 0, 0, 77]
TypedArray (object) hakkında daha fazla bilgi edinmek istiyorsanız bu makaleyi okuyabilirsiniz. Kesinlikle okumaya değer. Veri türleri hakkında fazla bilginiz yoksa önce bu wikipedia makalesini de okumak isteyebilirsiniz.
§Dizi İşlemleri Analizi
Javascript dizilerinde ve python listelerinde ekleme ve silme işlemleri O(N) (doğrusal) zamana mal olur. Bunun nedeni, içine bir öğe eklediğimizde, öğeleri yerleştirme noktasından sonra hareket ettirmemiz. İlk önce tüm öğeleri bir indeks sağa taşıyarak eklemek istediğimiz alanı boşaltıyoruz. Bu işlem yapıldığında maddeyi verilen dizine ekliyoruz. Silme yapmak istediğimizde aynı işlemi tersten yapıyoruz. Önce dizini boşaltıyoruz ve ardından dizinden sonraki her şeyi bir dizini sola itiyoruz.
Dizilerimiz indekslendiğinden arama işlemleri yalnızca sabit zaman alır. Örneğin bağlantılı bir listeyle karşılaştırıldığında, bu işlem önemli ölçüde daha hızlı (O(N) ve O(1)).
§Sonuç
Uygulama geliştirmeye başladığımızda ve temelleri atladığımızda (çünkü böyle çok daha eğlenceli oluyor) performans açısından bu bize pahalıya mal olabilir. Boş zamanlarınızda programlamanın temellerini öğrenmek fena bir fikir değil.
Şimdi umarım dizi veri yapısı hakkında daha iyi bir fikriniz vardır ve daha derine inmeniz için size ilham verebilmişimdir. Öğrenmeye devam edin !
Ilker Akbiyikİçindekiler
Benzer Paylaşımlar
