Rehber Dinamik diziler nasıl çalışır?

Merhaba,

Bu yazımda sizlere dinamik dizilerin (dynamic (sized) array) bildiğim kadarıyla nasıl çalıştığını ve implemente edildiğini aktarmaya çalışmak istedim. İyi okumalar.

"Dinamik dizi" ismindeki dinamik sıfatı, dizinin boyutunun değişkenliğini ifade ediyor. Başka bir deyişle, programlamadaki en temel araçlardan biri olan dizilere eleman ekleme/çıkarma işlevi sağlanıyor. Bu sayede program başlatılırken dizilere bir ilk boyut verilmesi gerekmeyip çalışma esnasında eleman ekleme/çıkarma yapılabiliyor. Oldukça işe yarar bir işlev, anlayacağınız.

Tabii burada kritik olan bir nokta da dinamik dizilerin oldukça hızlı ve verimli çalışması gerektiği. Ben de günümüz programlama dillerinden C++'ın vector'ünde ve Python'in varsayılan listesinde (list/[]) sağlanabilen hız ve verimin nasıl sağlandığını bildiğim kadarıyla anlatmaya çalışacağım.

Şimdi, dinamik dizi gerektiğinde genişleyebiliyor. (Boyutunun değişebildiğini söylemiştim ama aslında sadece genişliyor.) Bunun için de bir ilk boyuta sahip olmaya ihtiyacı yok (ama istenirse atanabilir), başta boşken bile sonradan boyut edinebiliyor. Yani başlangıçta hafızadan "yeterince büyük" yer edinmesi gibi bir durum yok; belki vardır benim bilmediğim durumlar ama değinmek istediğim nokta, bunun gereğinin olmaması. Dinamik dizinin aslına bakarsanız bildiğim tek olayı bu: Genişlemek. Bu işlevin çok hızlı yerine getirilmesi gerekiyor. Peki nasıl yapılabilir?

Anlatımları C++ ile yapacağım çünkü hafıza yönetimi bu dilde elle yapılabiliyor (new & delete).

Eleman ekledikçe boyutu bir bir artırmak​

Akla gelebilecek ilk yöntemlerdendir diye tahmin ediyorum. Diziye bir eleman eklendiğinde new ile dizi için hafızada yeni bir yer açabiliriz, elemanları eski yerden yeni yere kopyalar ve sonrasında eski yeri delete ile serbest bırakabiliriz. Basit olması için bir int dizisini ele alacağım:

[CODE lang="cpp" title="Dinamik dizi (ilk yöntem: boyutu bir bir artırma)"]#include <bits/stdc++.h>
using namespace std;

// "boyut" yerine belki sizeof ile bir şeyler yapılabilir ama basitlik için böyle yazdım.
void eleman_ekle(int *&dizi, int boyut, int eleman) {
// Yeni eleman için bir eleman fazla olacak şekilde hafızadan yeni alan tut.
int *yeni_dizi = new int[boyut + 1];

// Elemanları eski alandan yeniye taşı.
for (int i = 0; i < boyut; i++) {
yeni_dizi = dizi;
}

// Eski alanı serbest bırak.
delete dizi;

// Diziyi yeni alana göstert.
dizi = yeni_dizi;
}

int main() {
// Rastgelelik için seed'i saniyeye bağlı tanımlıyorum.
srand(time(0));

cout << "Kac eleman eklensin? ";
int eleman_sayisi;
cin >> eleman_sayisi;

// https://www.geeksforgeeks.org/measure-execution-time-function-cpp/
auto start = chrono::high_resolution_clock::now();

// Başta dizi boş. Dolu da olabilir ama.
int *dizi = new int[0];
for (int i = 0; i < eleman_sayisi; i++) {
int yeni_eleman = rand();
eleman_ekle(dizi, i, yeni_eleman);
}

auto end = chrono::high_resolution_clock::now();

auto gecen_zaman_ms = chrono::duration_cast<chrono::milliseconds>(end - start).count();

// Memory leak olmasın
delete dizi;

cout << eleman_sayisi << " eleman eklemek toplamda " << gecen_zaman_ms << " milisaniye surdu.\n";
}[/CODE]
Ideone test sonucu (100 bin eleman, 5.84 saniye): Ideone.com

6 saniye sürdü. Ben kendi bilgisayarımda, herhalde işlemcim i7 13700HX olduğundan 3554 milisaniye yani 3.5 saniye gördüm. Oldukça uzun. 100 bin yerine 1 milyon eleman eklediğimizi düşünsenize? Düşünmeyin hatta, onu da paylaşayım: Ideone.com. Sitenin desteklediği en yüksek limit (hesap açınca kullanılabilir oluyor) 15 saniye. Çokça aşıyordur tahminimce.

E neden böyle oldu? Çok zor değil aslında anlaması. Her eleman eklediğimizde dizinin boyutunu yalnızca 1 (bir) artırıyoruz:

• Boşken ekleme yapınca yeni yer tanımlamak için 1 ve kopyalama için 0,
• 1 eleman varken ekleme yapınca yeni yer tanımlamak için 2 ve kopyalama için 1,
• 2 eleman varken ekleme yapınca yeni yer tanımlamak için 3 ve kopyalama için 2,
• ...
• n eleman varken ekleme yapınca yeni yer tanımlamak için n + 1 ve kopyalama için n

işlem yapıyoruz ve toplam işlem sayısı n elemana ulaşmak için yaklaşık n^2 oluyor. Mesela 100 bin elemanlık testte yaklaşık 10^10 işlemin 5.84 saniye sürdüğünü gözlemledik. Eleman sayısı 10 katına çıkarsa süre de teoride 100 katına çıkar ve dolayısıyla 1 milyonluk testte yaklaşık 600 saniye gibi bir değer görmeyi bekleriz. Spoiler içinde paylaştığım kod ile farklı eleman sayıları için deney yapabilirsiniz:

Sürprizbozan: Eleman sayısına göre geçen ortalama süre hesaplama kodu

C++:

#include <bits/stdc++.h>
using namespace std;

// `boyut` yerine belki sizeof ile bir şeyler yapılabilir ama basitlik için böyle yazdım.
void eleman_ekle(int *&dizi, int boyut, int eleman) {
    // Yeni eleman için bir eleman fazla olacak şekilde hafızadan yeni alan tut.
    int *yeni_dizi = new int[boyut + 1];

    // Elemanları eski alandan yeniye taşı.
    for (int i = 0; i < boyut; i++) {
        yeni_dizi[i] = dizi[i];
    }

    // Eski alanı serbest bırak.
    delete dizi;

    // Diziyi yeni alana göstert.
    dizi = yeni_dizi;
}

int main() {
    // Rastgelelik için seed'i saniyeye bağlı tanımlıyorum.
    srand(time(0));

    cout << "Kac eleman eklensin? ";
    int eleman_sayisi;
    cin >> eleman_sayisi;

    int64_t ortalama_sure_ms = 0;
    const int ornek_sayisi = 10;
    for (int ornek = 0; ornek < ornek_sayisi; ornek++) {
        // https://www.geeksforgeeks.org/measure-execution-time-function-cpp/
        auto start = chrono::high_resolution_clock::now();

        // Başta dizi boş. Dolu da olabilir ama.
        int *dizi = new int[0];
        for (int i = 0; i < eleman_sayisi; i++) {
            int yeni_eleman = rand();
            eleman_ekle(dizi, i, yeni_eleman);
        }

        auto end = chrono::high_resolution_clock::now();

        auto gecen_zaman_ms = chrono::duration_cast<chrono::milliseconds>(end - start).count();
        ortalama_sure_ms += gecen_zaman_ms;

        // Memory leak olmasın :)
        delete dizi;
    }

    ortalama_sure_ms /= ornek_sayisi;

    cout << eleman_sayisi << " eleman eklemek 10 ornekte ortalama " << ortalama_sure_ms << " milisaniye surdu.\n";
}

Sonuç: n eleman eklemek toplamda yaklaşık n² işlem gerektiriyor.

Uzun lafın kısası, bu yöntem maalesef yeterince hızlı olmaktan çok uzak. Eğer günümüz dillerinde böyle bir yöntem tercih edilseydi hâlimiz beter olurdu.

---

Asıl yöntem: Gerektiğinde boyutu 2 katına çıkarmak​

Öncelikle eğlenceli kısım olan kodunu paylaşayım direkt:

[CODE lang="cpp" title="Verimli ve hızlı yöntem (gerektiğinde boyutu 2 katına çıkarma)" highlight="9, 12"]#include <bits/stdc++.h>
using namespace std;

// Bu çok daha hoş şekilde, bir class veya struct kullanılarak yazılabilir.
// İşin o tarafını sizlere bırakıyorum değerli arkadaşlar
// Bu sefer bir de size_t tip güncellemesi yaptım, daha uygun çünkü.
void eleman_ekle(int *&dizi, size_t &boyut, size_t &eleman_sayisi, int eleman) {
// Dizi boyutunu artırmamız gerekiyor, tamamen dolmuş çünkü.
if (boyut == eleman_sayisi) {
const size_t eski_boyut = boyut;
// Eğer boyut sıfır değilse 2 katına çıkar, sıfırsa 1 olsun.
boyut = boyut ? boyut << 1 : 1; // Veya 2 * boyut, çok fark etmez
int *yeni_dizi = new int[boyut];
for (int i = 0; i < eski_boyut; i++) {
yeni_dizi = dizi;
}

delete dizi;
dizi = yeni_dizi;
}

dizi[eleman_sayisi] = eleman;
eleman_sayisi++;
}

int main() {
// Rastgelelik için seed'i saniyeye bağlı tanımlıyorum.
srand(time(0));

cout << "Kac eleman eklensin? ";
int eklenecek_eleman_sayisi;
cin >> eklenecek_eleman_sayisi;

// https://www.geeksforgeeks.org/measure-execution-time-function-cpp/
auto start = chrono::high_resolution_clock::now();

size_t boyut = 0, eleman_sayisi = 0;
int *dizi = new int[boyut];
for (int i = 0; i < eklenecek_eleman_sayisi; i++) {
int yeni_eleman = rand();
eleman_ekle(dizi, boyut, eleman_sayisi, yeni_eleman);
}

auto end = chrono::high_resolution_clock::now();

// Bu sefer milisaniye çok büyük geliyor
// Mikrosaniye "us" ile ifade edilir. "Mikro" sembolü yerine "u" kullanılır.
auto gecen_zaman_us = chrono::duration_cast<chrono::microseconds>(end - start).count();

// Memory leak olmasın
delete dizi;

cout << eklenecek_eleman_sayisi << " eleman eklemek toplamda " << gecen_zaman_us << " mikrosaniye ("
<< gecen_zaman_us / 1000 << " ms) "
<< "surdu.\n ";
}[/CODE]
Ideone test sonucu (100 milyon eleman, 1.53 saniye): Ideone.com

Yeni yönteme hava attırmak istedim: Eleman sayısını 100 binden 100 milyona yani 1000 katına çıkardım ve buna rağmen ilk yöntemden 4 saniye daha hızlı çalıştı.

Ee, ne fark etti?

Yöntem başlığında da belirttiğim üzere bu yöntem boyutu bir bir artırmak yerine dizi dolduğunda boyutu 2 katına çıkarıyor. Bu ne işe mi yarıyor?

• Boşken ekleme yapınca yeni yer tanımlamak için 1 (ne zaman yeni yer tanımlansa 1 eksiği kadar kopyalama yapılıyor, onu yazmayacağım, işlem sayısı 2 katına çıkıyor gibi düşünün),
• 1 eleman varken yeni yer tanımlamak için 2,
• 2 eleman varken yeni yer tanımlamak için 4 (2 katına çıkarıyoruz),
• 3 eleman varken yeni yer tanımlamaya gerek yok çünkü 1 elemanlık boş yer var (hafıza olarak boş değil de pratikte elemanın değerini kullanmıyoruz),
• 4 eleman varken yeni yer tanımlamak için 8,
• 5/6/7 eleman varken boyut 8 olduğundan yeni yer tanımlamaya gerek yok,
• 8 eleman varken yeni yer tanımlamak için 16,
• 9-15 eleman varken boyut 16 olduğundan yeni yer tanımlamaya gerek yok,
• ...
• n eleman varken n 2'nin kuvvetiyse yeni yer tanımlamak için 2 * n, değilse sıfır

işlem yapılıyor. Daha şimdiden sezmiş olabilirsiniz niye daha az işlem yapıldığını:

Sürprizbozan: Çok daha hızlı olmasının, işlem azlığının nedeni

Diyelim ki toplamda n eleman ekleyeceğiz. Tüm eklemeleri düşünürsek boyut sadece 2'nin bir kuvvetiyken (ilk boyut 0 ya da 2'nin bir kuvveti değilse fark ediyor ama hız aynı) genişleme yapılıyor. 2'nin n'den büyük en küçük kuvveti 2^k olsun. Varsayım gereği 2'nin bir önceki kuvveti için 2^(k - 1) <= n geçerli. Toplamda 1 + 2 + 4 + ... + 2^k = 2^(k + 1) - 1 işlem yapılacaktır (nasıl bu değere eşit olduğunu anlamak için bu toplama 1 ekleyip baştan toplaya toplaya gidebilirsiniz). Düz hesap 2^(k + 1) diyelim biz ona, yani 4 * 2^(k - 1) olacak, bu da en fazla 4 * n olabilir.

Sonuç: n eleman eklemek en fazla 4 * n işlem gerektiriyor. Diğer işlemleri de hesaba katarsak katsayı artabilir ama yeterince küçük.

Dizinin bir ilk boyutu olduğunda da neler olduğunu gözlemlemek için birkaç deney yapabilirsiniz.

Farklı yöntemler​

Boyutu 2 katına çıkarma yöntemini modifiye edebilirsiniz, bu konuda serbestsiniz tabii ki. Örneğin 3, 4, 5 katına çıkarma gibi yollar deneyebilirsiniz. Sanırsam 2 katına çıkarma en ideal yöntemlerden. Bunun yanı sıra mesela dizinin boyutu sıfırken ekleme yaparken boyutu 1'e değil de atıyorum 34'e çıkarabilirsiniz. Her şey hayal gücünüze kalmış.

---

Peki ya eleman çıkarmak?​

Bir eleman çıkardığınızda dizinin boyutu eleman sayısının 2 katından büyük olursa boyutu yarıya indirmeyi düşünebilirsiniz; ama bu yavaşlamaya sebep olur çünkü mesela sürekli eleman sayısı/boyut oranı tam boyut güncelleme civarlarındayken çıkar-ekle-çıkar-ekle... yaptığınızı düşünün. Her seferinde boyut veya boyutun 2 katı kadar işlem yapılacak, en az ilk yöntem kadar yavaşlatmış olacağız her şeyi. Oysaki sadece eklemede boyut değiştirmek, çoğunlukla ekleme/çıkarma işlemlerinin tekte yapılmasını sağlıyor.

"Boyut değişmiyorsa eleman çıkarmak mümkün mü?" diye düşünebilirsiniz bu noktada. Siz isterseniz mümkün: Dizinizi boyuta göre değil de eleman sayısına göre kullanın. Bildiğim kadarıyla C++'taki vector bu şekilde işliyor: size (eleman sayısı) ve capacity (asıl boyut) diye iki ayrı kavram var.

---

Tamamen tecrübelerime dayanarak yaptığım bir anlatım oldu. Yanlış olduğunu düşündüğünüz yerler varsa düzeltmekten çekinmeyin, ekleme yapmak isterseniz de kapımız her zaman açık. Umarım işinize yarar ve eğlenceli olmuştur.

İyi Sosyal'ler! ​