Bu yazımda oldukça yüksek bir performans kazancı sağlamamıza yarayan bir optimizasyon metodundan bahsedeceğim : “Dinamik Programlama”.

Öncelikle şunun altını çizmeliyim. Dinamik programlamada geçen programlama sözcüğü sadece bilgisayar programlarını kapsamamaktadır, çünkü burada kullandığımız program sözcüğü “matematiksel programlama” dan gelmektedir, ki bu da kısaca sıkça kullandığımız optimizasyon(bir nevi iyileştirme demek optimizasyon belki kullanmayan da vardır :) kelimesine denk gelmektedir. Özetle buradaki program çokça kullandığımız ders programı, maç programı gibi deyişlerden pek de farklı bir program değildir. Ama biz bu sayımızda konumuzu bilgisayar programları ve algoritmalar üzerinden anlatacağız orası da ayrı :)

Kısaca tanımlamaya çalışırsak dinamik programlama bir problemi çözerken aynı alt-problemi birden fazla çözmemiz gereken durumlarda bu alt-problemi birden fazla kez çözmemizi engelleyen bir tekniktir. Az sonra vereceğim Fibonacci dizisi örneğinde daha güzel anlayacaksınız ama özellikle özyinemeli çözüme sahip problemlerde dinamik programlama problem çözüm yolumuzun verimini olağanüstü bir biçimde artırmaktadır.

Dinamik programlama uygulamalarımızda temel olarak 3 teknikten faydalanacağız:

  • Çözümü aynı olan alt-problemler
  • Büyük bir problemi küçük parçalara bölmek ve bu küçük parçaları kullanarak baştaki büyük problemimizin sonucuna ulaşmak
  • Çözdüğümüz her alt-problemin sonucunu bir yere not almak ve gerektiğinde bu sonucu kullanarak aynı problemi tekrar tekrar çözmeyi engellemek.

Şimdi buraya kadar anlattıklarımızı bir örnek üzerinde güzelce görelim. Yukarıda da bahsettiğim üzere dinamik programlamanın çok güzel ve zekice kullanılabileceği temel bir problem olan Fibonacci dizisi üzerinden dinamik programlamanın ne olduğunu daha net bir şekilde inceleyelim. Örneklerimi C Programlama dili üzerinden yapacağım. Tabiki aynı zamanda neyi neden yaptığımızı normal cümlelerle de açıklayacağım.

Kısaca hatırlamamız gerekirse Fibonacci dizisinin özelliği dizideki her sayının kendinden önceki 2 sayının toplamına eşit olmasıdır. Yani şöyle bir dizidir.

1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89...

Eğer herhangi bir sayının Fibonacci karşılığına F(n) dersek,

F(0) = F(1) = 1 olmak üzere

F(n) = F(n-1) + F(n-2)'dir Fibonacci dizisinde.

Fibonacci dizisini hatırladığımıza göre şimdi ilk hedef olarak kendimize C dilinde çok basit bir Fibonacci fonksiyonu yazalım.

unsigned int fibonacci(unsigned int sayi)
{
    if(sayi == 0 || sayi == 1)
    return 1;
    return fibonacci(sayi - 1) + fibonacci(sayi - 2);
}

Burada yaptığımız şey tamamen yukarıda Fibonacci dizisinin matematiksel açılımını yazarken yaptığımız şeyin aynısı. 0 ve 1 in Fibonacci'si 1 diğer sayıların kendilerinden 1 önceki ve 2 önceki sayıların Fibonacci'sinin toplamına eşit olduğudur. Fakat kod ne kadar basit ve kısa olsa da bu gerçekten çok kötü bir yöntem Fibonacci dizisini hesaplamada. Nedenine gelirsek mesela F(4)'ü adım adım hesaplayalım:

F(4) = F(3) + F(2)
     = (F(2) + F(1)) + F(2)
     = ((F(1) + F(0)) + F(1)) + F(2)
     = ((F(1) + F(0)) + F(1)) + (F(1) + F(0))

gördüğümüz gibi F(4) ün değerini hesaplarken F(2)'ye 2 defa ihtiyacımız oldu ama 2 seferde de hesapladık bu yöntemle aynı şeyi. Daha büyük sayıların Fibonacci'sini hesaplamak çok daha fazla tekrar tekrar aynı sayıların Fibonacci'sini hesaplamamıza yol açacak kolaylıkça anlayabileceğiniz üzere(isterseniz elle bir deneyin :D) Ve 50'den büyük sayıların Fibonacci'lerini hesaplamanızı imkansız kılacak bu yöntem bilgisayarınızda.

Neden bir kere hesapladığımız bir değeri tekrar tekrar hesaplayalım ki ilk hazır bulmuş olduğumuz cevabı kullanmak varken! Bir de şu fonksiyona göz atalım.

unsigned int fibonacciArray[1000];

unsigned int fibonacci2(unsigned int sayi)
{
    unsigned int i = 2;
    fibonacciArray[0] = fibonacciArray[1] = 1;
    while(i <= sayi)
    {
        fibonacciArray[i] = fibonacciArray[i - 1] + fibonacciArray[i - 2];
        i++;
    }
    return fibonacciArray[sayi];
}

Burada yaptığımız işlem ise şu. Hesapladığımız Fibonacci sayılarını bir array'e kaydediyoruz. Daha sonra lazım olunca bu değerleri direkt array'den hazır bi şekilde alıyoruz. Böylece tekrar tekrar aynı işlemi yapmaktan kurtuluyoruz.

(NOT: burada fibonacci2 fonksiyonuna boş değer döndürüp, programınızın başında bu fonksiyonu sadece 1 kez çağırıp sonra array'deki hazır sonuçları programınızda kullanmanız mantıklı olandır burada sadece eğitimsel amaçlı olarak fonksiyon değer dönmektedir, diğer fonksiyonla aynı işi yaptığımız anlaşılır olsun diye)

Performans karşılaştırması yapacak olursak kendi bilgisayarımda fibonacci(50) 8dk. 36 sn'de sonuç verirken fibonacci2(50) 0.003 sn'de sonuç veriyor. Kısacası muhteşem bir performans kazancımız oldu! Daha bilimsel konuşacak olursak temelde aynı mantıkla çalışan iki fonksiyonun birincisi O(2n) iken ikincisi O(n) zamanda çözmektedir problemi.

Bu yazımızda kısaca sizlere dinamik programlamanın ne olduğundan ve yazdığımız programlara nasıl adapte edebileceğimizden bahsettik. Umarım faydalı bir yazı olmuştur. Diğer sayılarda da buluşmak üzere...

Kaynaklar: