Dinamik programlama

Uzun zamandır birşeyler yazamadım. Bir yerlerde dinamik programlama üzerine birşeyler okumuştum, açlığın tavana vurduğu iftar saatine doğru birden aklıma geldi. Ben de açlığımı bastırma, zamanı hızlandırma niyetiyle bir örnek program yazmaya karar verdim. Aşağıda dinamik programlama tekniği ile yazılmış küçük bir C programı görüyorsunuz :

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <math.h>

typedef unsigned long long ull_int;

ull_int fiboCalc(ull_int x);
void fiboBuildCache(size_t size);
void fiboLoadCache(size_t prevCacheSize);
void fiboFreeCache(void);

ull_int *fiboCache = NULL;
size_t fiboCacheSize = 0;

int main(int argc, char *argv[]) {
    srand(time(NULL));
    int i;
    for (i = 0; i < 100000000; i++) {
        int randNum = (abs(rand()) % 40);
        // printf("f(%d)\t= %d\n", randNum, fiboCalc(randNum));
    }
    fiboFreeCache();
    
    system("PAUSE");
    return EXIT_SUCCESS;
}

ull_int
fiboCalc(ull_int x) {
    if (x < 2) {
        return x;
    }
    size_t requiredCacheSize = (x + 1) * sizeof(ull_int);
    if (fiboCache == NULL || fiboCacheSize < requiredCacheSize) {
        fiboBuildCache(requiredCacheSize);
    }
    return fiboCache[x];
}

void
fiboBuildCache(size_t size) {
    size_t prevCacheSize = fiboCacheSize;
    if (fiboCache == NULL) {
        fiboCache = malloc(size);
        fiboCacheSize = size;
        fiboLoadCache(prevCacheSize);
    } else if (fiboCacheSize < size) {
        fiboCache = realloc(fiboCache, size);
        fiboCacheSize = size;
        fiboLoadCache(prevCacheSize);
    }
}

void
fiboLoadCache(size_t prevCacheSize) {
    int i, end;
    if (prevCacheSize == 0) {
        fiboCache[0] = 0;
        fiboCache[1] = 1;
        i = 2;
    } else {
        i = prevCacheSize / sizeof(ull_int);
    }
    end = fiboCacheSize / sizeof(ull_int);
    for (; i < end; i++) {
        fiboCache[i] = fiboCache[i - 2] + fiboCache[i - 1];
    }
}

void
fiboFreeCache(void) {
    if (fiboCache != NULL) {
        free(fiboCache);
        fiboCache = NULL;
        fiboCacheSize = 0;
    }
}

Programa göz gezdirdiğiniz de işlevinin fibonacci sayılarını hesaplamak olduğunu fark etmişsinizdir. Peki bu programı dinamik yapan nedir? Dinamik programlamayı bir problemin çözümünde, problemin kapsadığı alt problemleri birden fazla defa çözmemizi engellemeye dayanan bir teknik olarak ifade edebiliriz. Dolayısı ile dinamik programlama bir başka açıdan bakıldığında bir optimizasyon tekniğidir. Bu açıdan yukarıda ki programın yaptığı tam da budur. Problemimiz fibonacci sayılarını hesaplamaktır ve fibonacci sayıları fib(n) = fib(n-1) + fib(n-2) formülü ile hesaplanır. Dolayısı ise fibonacci sayılanın hesaplanması problemi alt problemlerin sonuçlarının tekrar tekrar kullanılabileceği bir türdedir. Yukarıda ki programda 0 ila 40 arasında rastgele oluşturulan 100.000.000 sayının fibonacci dizisinde ki karşılıkları hesaplanmaktadır. Bu program da aslında önemli bir kaç iyileştirme daha yapılabilir fakat bu haliyle dahi bir hayli verimlidir ve bunda dinamik programlama tekniğinin kullanılmasının önemi çok büyük. Kısacası alt problemlerin tekrarlandığı problem çözümlerinde alt problemlerin sonuçlarının saklanması ve tekrar tekrar kullanılması algoritmalarınızı çok hızlandırabilir.