Burak IŞIKLI :))

Dinamik Programlama(Dynamic Programming)

Posted in Algorithm, C/C++ by Burak IŞIKLI on 14 Ağustos 2009

Dinamik programlama bir problemi çözerken aynı alt-problemi birden fazla çözmemiz gereken durumlarda bu alt-problemi birden fazla kez çözmemizi engelleyen bir tekniktir. Dinamik programalama, matematik ve bilgisayar bilimlerinde karmaşık problemleri çözmek için kullanılan bir metottur. Overlapping subproblems ve optimal substructure denilen problemlerde uygunabiliyor.

Eğer problemimiz kendi içinde alt problemlere ayrılabiliyorsa overlapping subproblems’dir. Buna en iyi örnek Fibanicci serisidir. Daha önceden bu yazımda fibonacci serisini anlatmıştım.

Shortest Path Optimal SubstructureFakat problemimiz kendi içinde alt problemlere ayrıldığında daha iyi bir performans sağlıyorsa buna optimal substructure deniliyor. Buna en iyi örnek ise greedy algoritmasıdır. 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.

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 örneğimiz olan fibonacci dizimize başlayalım. Fibonacci dizimizi kısaca bir hatırlayalım.

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.

İlk yaptığımız prosesimizin fonksiyonunu hatırlayalım:

fib.cpp

// Recursive Function
int fib(int num) {
 if ((num == 0) || (num == 1))
 return num;
 else
 return (fib(num - 1) + fib(num - 2));
}

Bu kadar kısa bir kod yazarak çözümü sağlamıştık. Ancak bu yöntem kodun kısa olmasına rağmen performans açısından kötü bir yöntemdir.  Nedenine gelirsek mesela F(3)’ü adım adım hesaplayalım:

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

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

= ((F(1) + F(0)) + F(1)) + (F(1) + F(0))

Görüldüğü gibi F(4) değerini hesaplarken F(1)’ye 2 defa ihtiyacımız oldu ama 2 seferde de hesapladık. Prosesimizi değiştirerek bir de şu hale getirelim.

fib2.cpp

/*
 *
 * Program:  Fibonacci Series v2
 * Programmer: Burak ISIKLI
 *
 */

#include <iostream.h>

unsigned int fib2(unsigned int num);

unsigned int fibArray[1000];

// Main Function
int main() {
 unsigned int number, result;
 cout << "Fibonacci serisinin(fib(x)) sayisini giriniz x = ";
 cin >> number;

 result = fib2(number);
 cout << "fib( " << number << " ) = " << result << "\n\n";

 return 0;
}

unsigned int fib2(unsigned int num)
{
 unsigned int i = 2;
 fibArray[0] = fibArray[1] = 1;
 while(i <= num)
 {
 fibArray[i] = fibArray[i - 1] + fibArray[i - 2];
 i++;
 }
 return fibArray[num];
}

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

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. Daha bilimsel konuşacak olursak problemi temelde aynı mantıkla çalışan iki fonksiyonun birincisi O(2^n) iken ikincisi O(n) zamanda çözmektedir.

Kaynaklar:

http://en.wikipedia.org/wiki/Dynamic_programming

http://en.wikipedia.org/wiki/Optimal_substructure

http://e-bergi.com/2008/Mart/Dinamik-Programlama

/*
 *
 * Program:  Fibonacci Series v2
 * Programmer: Burak ISIKLI
 *
 */

#include <iostream.h>

unsigned int fib2(unsigned int num);

unsigned int fibArray[1000];

// Main Function
int main() {
 unsigned int number, result;
 cout << "Fibonacci serisinin(fib(x)) sayisini giriniz x = ";
 cin >> number;

 result = fib2(number);
 cout << "fib( " << number << " ) = " << result << "\n\n";

 return 0;
}

unsigned int fib2(unsigned int num)
{
 unsigned int i = 2;
 fibArray[0] = fibArray[1] = 1;
 while(i <= num)
 {
 fibArray[i] = fibArray[i - 1] + fibArray[i - 2];
 i++;
 }
 return fibArray[num];
}

Multi-Threaded(Çok Kanallı) Programlama

Posted in Java by Burak IŞIKLI on 16 Haziran 2009

Çok Kanallı Programlama (Multi-Threaded Programming), bir programda aynı anda birden fazla işin yapılabilmesidir. Yani bir kod parçası bir işlemi gerçekleştirirken aynı anda ona paralel olarak bir başka kod parçasının çalışması demektir. Birbirine paralel çalışan çalışanlardan her birine kanal (thread)

Java çok kanallı porgramlamayı temelden desteklemektedir. Yani çok kanallılık dile bir takım kütüphanelerle eklenmemiştir. Aslında her Java programı bir kanalda (thread’te) çalışır. Örneğin application’ların main method’unun çalıştırılmasıyla adı ‘main’ olan bir ana thread çalıştırılır. Ancak tek bir kanal olunca programcı yazdığı kodun bir thread’in içerisinde çalıştığını farketmez.  Thread bize eş zamanlı birden fazla işi yapma fırsatını yani multitasking sağlıyor.

Thread’in faydaları:

  • Kaynak paylaşımı
  • Daha az bekleme süresi
  • Daha verimli donanım kullanımı(Multiprocessor kullanımı)

Yeni bir thread yaratıldığında biz start komutu vermedikçe thread çalışmaya başlamıyor hazır durumda bekliyor. Biz start komutunu verdiğimizde çalışmaya başlıyor. Ayrıca thread’i sleep komutu ile belli süre bekletebiliyor, stop komutu ile öldürebiliyoruz.  Peki ama thread ile multithread arasında ne fark vardır?

multithread

Resimde gördüğümüz gibi threadler aynı kodu, veriyi ve dosyaları kullanmasına rağmen farklı register ve stack’leri vardır. Bu sayede aynı kod içinde farklı işler yapıp farklı şeyleri hafızada tutabiliyor. Java’da thread yaratmanın iki yolu var. Ben implement ederek kullandım. Ancak extend ederek de thread yaratılabilir. Thread pool diye bir kavram da var. Siz belirli bir thread sayısı veriyorsunuz. Thread pool boşta olan thread’i kullandırıyor. Multihreading yaşanabilecek en önemli sorunlardan biri, concurrent(eş zamanlılık) ve senkronizasyon sorunu. Siz aynı anda hem ekleme hem de silme yapmamınız gerekiyor. Aksi takdirde istediğinizi eklemeden hangi elemanı almaya çalışırsanız hangisini alacaksınız gibi bir soru karşımıza çıkıyor. Bunu çözmenin 3 yolu var:

  • Producer-consumer problemi: İşletim sistemleri dersinde öğrendiğimiz aynı mantık üretici-tüketici problemiyle çözebiliriz.
  • Circular buffer: Producer-consumer problemi benzer bir çözüm. Farkı kendiniz bir dizi oluşturuyorsunuz ve kilit kontrolü bu dizide oluyor.
  • Java collections: Kendimiz kilitlerle uğraşmadan bu işi java’ya bırakabiliriz. Java’nın bu konulara kendi çözüm getirdiği collections sınıfını kullanabiliriz.

Basit bir thread örneği(ThreadTest.java):


import java.util.*;

public class ThreadTest implements Runnable {
 public void run() {
 while (true) {
 try {
 Thread.sleep(1000);
 System.out.println("Other thread time : " + new Date());
 } catch (Exception e) {
 e.printStackTrace();
 }
 }
 }

 public static void main(String[] args) {
 ThreadTest test = new ThreadTest();
 Thread thread = new Thread(test);
 thread.start();
 System.out.println("Main thread");
 }
}

Bu programda ekrana “main thread” yazdıktan sonra  threadimiz başlatılarak 1 saniye aralıklarla tarihi ekrana yazıdırıyor.