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.

Yeni diller ve Groovy

Webte dolaşırken bir yazı ile karşılaştım. Php platformunu kullanan ve gücüne inanan bir meslektaşım son zamanlarda o kadar çok dilcik tasarlandı ki artık bunun sonu nereye varır diye yazmış ve Groovy'e "dilcik" yakıştırmasında bulunmuştu.

Son yıllarda çok sayıda dilin tasarlanıp uygulandığı hepimizin bildiği bir gerçek olduğu düşüncesindeyim. Fakat bu dillerin biri hakkında birşeyler yazmak istedim. Bu dil Groovy.

Günümüzde bir çok bilgisayar uzmanı ve programcının kullandığı bir ifade var bu ilginç dönem için "Diller çağı" diye nitelendiriyorlar bu dönemi. Son 10 sene içerisinde o kadar fazla yeni dil tasarlandı ve uygulandı ki takip etmek neredeyse imkansız. Fakat bunun ne anlama geldiği bence başlıbaşına bir tartışma konusu. Tüm bu dillerin arasından geçenlerde Groovy ile tanıştım. Şunu söylemeliyim ki gerçekten etkileyici bir proje Groovy. Pyhton yada Ruby gibi esneklik ve üretkenlikte adından söz ettiren dillerden hem dil bazında hem üretkenlik bazında asla geri kalmıyor Groovy. Günümüz programlama inceliklerinin tamamını yada çok önemli bir kısmını uygulayabilicek kapasiteye sahip olduğunu söylemeliyim. Ayrıca ardında çok güçlü bir platform ve sınırsız kütüphane barındırıyor bu dil. Çünkü groovy ile on yılı aşkın süredir yazılmış ve kullanıma hazır yüzbinlerce java sınıfını sorunsuz kullanabiliyorsunuz. Hem de nokta kadar bir değişiklik gerektirmeden. Ayrıca Groovy çok büyük oranda kendi sintaksına ek olarak java sintaksını da destekleyen bir dil, yani resmen java sintaksında kod yazıyorsunuz ve groovy yorumlayıcısı bu kodu derleme gerektirmeden işletebiliyor. Bu niteliği mevcut Java programcılarının dili öğrenmesinde büyük kolaylık getiriyor. Ayrıca bir özelliğe daha sahip ki değinmeden geçemem. Groovy kodu java sınıflarına(java bycode code) derlenebiliyor ve java ile yazılmış programlarda hiç bir değişiklik gerekmeden bu sınıfları kullanabiliyorsunuz. Bu dil ayrıca yaygın programlama ihtiyaçları için çok başarılı bir utility kütüphanesine sahip. Yani neredeyse Groovy Java dilinin yeni nesil bir uyarlaması diyebiliriz. Doğruyu söylemek gerekirse halen bir çok projesinde Php, C++ gibi dil ve platformları kullanmak zorunda kalan ben birçok defalar keşke diyorum. Keşke Php'de closureları desteklese. Keşke Php dil bazında DOM ve XML parsing ve generating desteklese, keşke Php'ninde temel kütüphane işlevselliği tamamen nesne yönelimli paradigmayı kullansa. Keşkeler böyle sürüyor gidiyor.. Burada asıl değinmek istediğim aslında uzun süredir kullandığımız birçok dil ve platformun artık kendilerini bir nebze olsun modernize etmeleri gerektiğidir. Php'de bunların arasında. Php hala anonim fonsiyonları desteklemiyorsa artık bence birşeylerin sorgulanmasını gerekir. Çünkü Groovy gibi dil ve teknolojilerin arkasındaki kaynaklar çok daha kısıtlı olduğu halde bu niteliklerin tümü Groovy ve Ruby gibi dillerde mevcut. Yaygın deyimle "diller çağı" bence dil tasarımda kalitenin yitirildiği, etrafta bir çok amacsız ve plansız dilin boy gösterdiği bir dönem değil. Aksine programcılık sanatında bir rönesans olarak dahi nitelendirilebilir. Yıllarca kısıtlı dil kümeleri ve kısıtlayıcı programlama yaklaşımları ve tekniklerinin kırıldığı bir dönem olduğu inancındayım bu dönemin. Bence programcı olarak çalışan, düşünen ve yaşayan dostlarımın Groovy gibi genç, heyecanlı ve nitelikli projelere daha iyimser, daha sağ duyulu bakmaları daha güzel bir yaklaşım olurdu.

Hug a developer today...

Programcılar ve yaşadıkları üzerine hoş bir kısa film. İzlemenizi öneriyorum :)

Buyrun izleyin

Konsol uygulamaları için arguman ayırıcı

Aslında birkaç haftadır aklımdaydı bir komut satırı ayırıcısı yazmak. Fakat bir türlü bir iki gün ayırıp başlayamamıştım bu işe. En sonunda zaman bu zamandır dedim ve yazdım bir prototip. Aslında bu kararı böylesine kesinlikle alışımda finallerin stresinden kurtulma fikri etkili oldu diyebilirim. Programcıların bir çoğu program yazarak rahatlar :) Her neyse, şimdilik komut satırı ayrıcımız sade ve ufak, fakat GNU komut satırı uygulamalarında uygulanan komut argüman stiliyle uyumlu çalışıyor. Bununla beraber üzülerek belirtmeliyim ki henüz harici bir dökümantasyona sahip değil. Kaynak kod içinde mümkün olduğunca açıklama yazmaya çalıştım. Fakat sınav meşguliyeti dolayısıyla bu işe çok kısa bir süre ayırabildiğimden pek vakıf olabildiğimi söyleyemem. Eğer projelerinde bu kodu kullanmak isteyen varsa şimdilik ufak bir örnek program ve kaynak kod açıklamalarıyla idare etmek zorunda. Ayrıca kullanmayı düşünenler olursa diye ufak kütüphanemizin temel çalışma prensibini açıklayıp, örneklemek istedim.

Öncelikle kütüphane’nin temel hedefi komut satırı uygulamalarını yazarken argüman ayırma derdine bir çözüm olmasıdır. Yani

ls -la /home
ps -aux
diff --brief -biw file1 file2

gibi komut satırı çağrılarında kullanılabilecek farklı formlardaki argumanları işleyebilmemize yarar. Bununla birlikte kütüphanin kullanımı Callback Mechanizm adı verilen bir programlama tekniğine dayanır. Ne demek bu Callback Mechanizm? Kısaca geri çağrı mekanizması olarak açıklayabiliriz. Yani bir olayın gerçekleşmesine bağlı olan eylem(fonksiyon) çağrısı mekanizması. MVC mimarisine aşina olanlar için bu mekanizma zaten gayet tanıdıktır. Çünkü bu sistem olay temelli programlamada çok yaygın kullanılır. (Popüler Qt kütüphanesi benzer fakat farklı bir mekanizma kullanır SIGNAL/SLOT) Konumuzdan fazla uzaklaştırmadan kütüphanemizi açıklamaya devam edersek. Kütüphane C++ dilinin nesne yönelimli kullanımına bir örnek teşkil eder. Basit bir struct ve bir class tanımından meydana gelir. Kütüphaneye dahil olan tüm tanımlar CLParser namespace’i içinde tanımlanmıştır. Şimdi kütüphanin kullanımına tipik bir önrek vereyim :

int main(int argc, char **argv) {
CLParser::CLParser clp(argc, argv); // Nesne tanımı
clp.setShortPrefix("-"); // Kısa parametre ön eki
clp.setLongPrefix("--"); // Uzun parametre ön eki
clp.setMaxNotPrefixedCC(2); // Maks. ön eksiz argüman sayısı(dosya ismi vb.)
// Argumanları ayıkla ve gerekli fonksiyon çağrılarını gerçekleştir
clp.parse();

return 0;
}

İşte bu kadar basit. Aslında örnek programımızda setShortPrefix, setLongPrefix ve setMaxNotPrefixedCC fonksiyonlarının kullanımının gereksiz olduğunu söyleyebilirim. Çünkü zaten ön tanımlı olarak kısa parametre ön eki "-" ve uzun parametre ön eki "--" olarak belirlenmiştir. Ayrıca yine maksimum ön eksiz argüman sayısı varsayılan olarak 1 olarak belirlenmiştir. Bu kodlarıda varsayılan değerlerin kullanımı vasıtasıyla kaldırdığımızda örnek programımız :

int main(int argc, char **argv) {
CLParser::CLParser clp(argc, argv); // Nesne tanımı
// Argumanları ayıkla ve gerekli fonksiyon çağrılarını gerçekleştir
clp.parse();

return 0;
}

Bir hayli sade değil mi? :) Peki şimdi şu soruyu sorabilirsiniz. "İşlev nerede? Yani tamam kütüphane argumanları parse ediyor fakat işlev?" İşlevsellik için daha önce belirtilen callback mekanizmasını kullanıyoruz. Kütüphanemizle birlikte gelen CLCommands.h ve CLCommands.cpp dosyaları üzerinde bir kaç değişiklik yapmamız yeterli. Bu dosyalar parser(ayırıcı)'ımızın ayırdığı belli argümanlara karşı hangi callback fonksiyonlarının eşleştiğini belirlememize yarıyor.

Aşağıda CLCommands.h dosyasının birazcık sadeleştirilmiş ve türkçeye çevrilmiş bir versiyonu mevcut. İncelediğinizde kütüphanenin nasıl kullanıldığını anlayacağınızı umuyorum.

namespace CLParser {

///////////////////////////////////////
// GERİ ÇAĞRI FONKSİYON PROTOTİPLERİ //
///////////////////////////////////////

/*
Tüm geri çağrı fonksiyonları aşağıdaki prototiple aynı imzayı taşımalıdır.
(Aynı geri dönüş ve giriş argümanı tip ve sıralamasını kullanmalıdır)
void func(char *command, int argc, char **args);
*/

void cbNPArgs(char *command, int argc, char **args);
void cbA(char *command, int argc, char **args);
void cbB(char *command, int argc, char **args);
void cbC(char *command, int argc, char **args);
void cbDE(char *command, int argc, char **args);
void cbDEF(char *command, int argc, char **args);
void cbDEFG(char *command, int argc, char **args);

//////////////////////////////////////////////////////////////////////////////////
// GERİ ÇAĞRI TABLOSU (TÜM GERİ ÇAĞRI METODLARI BU NOKTADA PARSER İLE BİRLEŞİR) //
//////////////////////////////////////////////////////////////////////////////////

const CLCommand COMMAND_SET[] = {

{"a", cbA, 2}, // Kısa ön ekli "a" argümanı. 2 parametre alır. Geri çağrı fonksiyonu "cbA"
{"A", cbA, 2}, // "a" komutuna kısa yol.(alias)

{"b", cbB, 3}, // Kısa ön ekli "b" argümanı. 3 parametre alır. Geri çağrı fonksiyonu "cbB"
{"c", cbC}, // Kısa ön ekli "c" argümanı. Parametre almaz. Geri çağrı fonksiyonu "cbC"

{"de", cbDE, 2}, // Uzun ön ekli "de" argümanı. 2 parametreli. Geri çağrı fonksiyonu "cbDE"
{"Foo", cbDE, 4}, // Uzun ön ekli "Foo" argümanı. "de" argümanıyla aynı geri çağrı fonksiyonunu kullanır. 4 parametreli.

{"def", cbDEF, 3}, // Uzun ön ekli "def" argümanı. 3 parametre alır. Geri çağrı fonksiyonu "cbDEF"
{"defg", cbDEFG}, // Uzun ön ekli "defg" command. Parametre almaz. Geri çağrı fonksiyonu "cbDEFG"

/*
Bu komut özel bir anlam ifade eder.
Ön ek almamış herhangi bir argumanı ifade eder. (dosya isimleri vb.)
*/
{"*", cbNPArgs} // Ön ek almamış herhangi bir arguman (dosya ismi gibi). Geri çağrı fonksiyonu "cbNPArgs"
};

} // namespace CLParser

Görüldüğü üzere kullanımı oldukça basit. Tek yapmanız gereken bir karakter(kısa ön ek kullanır) yada birden çok karakter uzunluğunda bir arguman(uzun ön ek kullanır) ve parser'ın bu arguman'a rastladığında çağrıcağı fonksiyonu tanımlamaktır. Ayrıca tercihen arguman'ın alabileceği bir parametre sayısıda verebilirsiniz. Örneğin

komut -a 1 2

Yukarıda ki komut satırı çağrısı bir adet arguman("a") ve bu argumana ait iki parametre("1", "2") alır.

Parser otomatik olarak "a" argümanıyla eşleşen geri çağrı fonksiyonunu çağarıcaktır ve bu geri çağrı fonksiyonuna

void geri_cagri_fonk(char *command, int argc, char **args);
                     ^               ^             ^
                     ARGÜMAN'IN      ARGÜMAN'IN    ARGÜMAN'IN
                     KENDİSİ         PARAMETRE     PARAMETRE
                                     SAYISI        LİSTESİ

şeklinde iletilir.

Parser kısa ve uzun ön ekli argümanların olası sayıda parametrelerini destekler. Bunlara ek olarak kısa ön ekli argümanların birleştirilmiş yazımınıda desteklemektedir. Fakat tahmin edeceğiniz gibi bu durumda birleştirilen argümanlar parametre almayan türden olmalıdır. Örneğin

ls -l -a
ls -la yada ls -al

biçminde yazılabilir. Unutulmamalıdır ki burada -l ve -a parametrelerinin birleştirilebilmeleri için parametre almayan türden kısa ön ekli argümanlar olmaları gerekmektedirler.

Yazımı sonlandırırken belirtmem gereken bir nokta da geri çağrı prototiplerinin nerede implemente ediliceğidir. Ben bu iş için CLCommands.cpp dosyasını kullanıyorum. Fakat siz kendi tercihinizi yapmakta özgürsünüz.

Yazımın açıklayıcı olduğunu umuyorum. Proje kodu GPL lisansı sahiptir. İstediğiniz değişikliği yapmakta özgürsünüz. Bu uzunlukta bir metini sıkılmadan okuduğunuz için size ayrıca teşekkür ediyorum.. İyi eğlenceler..

PROJE KODUNU INDIR