Algoritmaları Optimize Etmek

Uzun bir süre sonra tekrar buralardayım.. E hadi bismillah o halde ;)

Biz mühendislerinin sahip olması gereken en genel yeteklerden biri en az kaynakla en çok işi ortaya çıkartabilmektir. Söz konusu bilgisayar mühendisliği olunca bu kavram kendini bilgisayar sistemleri kaynaklarına, daha da derine inersek yazılım geliştirme dünyası içinde üretilen kodların ya da bir problemin çözümüne yönelik algoritmaların daha az işlemci gücü, daha az ram ve daha az süre kullanarak işlerini tamamlaması halini almakta. İşin içinde “daha az tüket, daha fazla üret” mantığı olduğu için “optimizasyon” kavramı kaçınılmazlarımızdan biri olarak hayatımızın içerisine işliyor…

Aşağıdaki yazıda basit bir problemi alıp, problemin çözümüne yönelik basit bir algoritma önereceğim ve ardından önerdiğim bu algoritmanın adım adım nasıl optimize edileceğini ele alacağım. Hadi başlayalım o zaman:

Problemimiz: 0 ile 1000 arasındaki 3 ya da 5’e tam bölünebilen tam sayıların toplamı nedir? (Project Euler’deki 1. soru)

Problemin çözümüne yönelik en basit yaklaşım 0-1000 arasında teker teker ilerleyip sayının 3’e 5’e bölümünden kalanın 0 olup olmadığını kontrol etmektir. Algoritmayı gerçeklersek:

Algoritma gayet açık ve basit; fakat karmaşıklığı O(n) ve FPU üzerinde koşması gereken ve aritmetik olarak en uzun işlem olan bölme işlemi kullanmakta (Mod işlemleri [C için %], derleyici tarafından genellikle Division işlemlerine dönüştürülür). Algoritmaya biraz daha yakından bakarsanız bazı tekrarların yapıldığını göreceksiniz. Her 15 iterasyon (3*5) ifadesel olarak aynı sonuç kümesini oluşturmakta. Peki bu 15 iterasyonda neler olmakta?

  • (iterator + 3), (iterator + 6), (iterator + 9) ve (iterator + 12) 3’e tam bölünebilir.
  • (iterator + 5) ve (iterator + 10) 5’e tam bölünebilir.
  • (iterator + 0) 3 ve 5’e tam bölünebilir. (iterator + 15 sayısının bir sonraki 15 iterasyonunda iterator + 0 olacağına dikkat edin)

Bu da her 15 iterasyonda sonucun

olacağı anlamına geliyor.

Bu durumda asıl algoritmamızı, bölme işlemleri olmadan, dolayısıyla daha hızlı şekilde çalışacak halde optimize edebiliriz. Birkaç satır daha kod ekliyoruz, karmaşıklığı değiştiremiyoruz, halâ O(n) olarak kalıyor çok sayıda bölme işleminden kurtulmanın yanında iterasyon sayısını da hemen hemen 15 kat azaltmış oluyoruz:

Yukarıda göreceğiniz üzere, Max değerinin yani aralığın üst limitinin 15’in tam katı olmadığı durumlarda kalan sayıları toplama ekleyebilmek için ufak bir döngü daha kurmak zorunda kaldık. Bunun yanında ilk döngü şu şekilde optimize edilerek yeniden yazılabilir:

Peki neler oldu? özet olarak bakarsak, O(n) karmaşıklığında n*t sürede işi tamamlayan ve n*2 adet bölme işlemi yapan bir algoritmayı, n*t/15 sürede tamamlanan ve n/15 adet çarpma ve n*2/15 adet toplama işlemi yapan bir algoritmaya dönüştürmüş olduk. Left-over hesabını şu an için ele almamıza gerek yok. Algoritmaya getirdiği yük, algoritmanın ilk haline kıyasla inanılmaz derecede düşük. Algoritmanın mevcut durumuna bir inceleme daha yapalım ve biraz daha optimize ederek hızlandıralım:

Ooops.. Neler oldu orada? Önce döngü içindeki çarpma işlemini döngü dışına çıkarttık ve gerekli sınır ve döngü ilerleme sabitini düzenledik. Ardından ekstra toplama işlemini de döngü dışına taşıyarak sınırları düzenledik. Böylece n/15 olan döngü sayısındaki n/15 adet çapma işlemini 1 adet çarpma işlemine ve n/15 olan toplama işlemini 2 adet toplama işlemine dönüştürdük. Ne kadar hızlandık acaba? :))

Optimizasyona devam edelim, daha yapacak birkaç iş daha kaldı:
Bu bir döngü, x’leri y’lere ekleyip bir z sonucu üretiyor. Daha neler yapılabilir? 1-N aralığındaki aritmetik toplam formülünü şöyle bir hatırlayalım: Sum = n * (n+1) / 2. Mevcut problemimizle bir miktar ilişkili. Önemli olan bu formülü problemimizde nasıl uygulayabiliriz? Cevabı bulabilmek için birkaç iterasyonu elle yapalım, takip edelim:

  • i: 1; Max = 15; sum = 45 + LeftOvers
  • i: 2; Max = 30: sum = 45 + (45 + 105) = 195 + LeftOvers;
  • i: 3; Max = 45: sum = 45 + (45 + 105) + (45 + 105 + 105) = 450 + LeftOvers;
  • i: 4; Max = 60: sum = 45 + (45 + 105) + (45 + 105 + 105) + (45 + 105 + 105 + 105) = 810 + LeftOvers;

Asıl ilginç işler buradan itibaren başlıyor. Örnek olarak Max = 30 aldığımızda, dikkat ederseniz 45 sayısı (iterasyon sayısı) kadar toplamı etkiliyor. Bunun yanında ilk iterasyon haricinde her bir iterasyonda toplama 105 daha ekliyoruz. Yukarıyı biraz daha incelersek matematiksel ifadenin şu şekle dönüştüğünü görmez miyiz?

Max = 30 için
sum = 2*45 + (2-1)*((2-1)+1)/2*105

Buradan da (2-1)*((2-1)+1)/2 kısmını inceleyelim: (2-1)*((2-1)+1)/2 = 1*2/2 = n*(n+1)/2 :)
30’u de incelersek, 2 = 30/15 olduğunu yani taa en baştaki n/15 olduğunu göreceğiz, yani asıl iterasyon sayısı…

Bu durumda mevcut döngü artık şu hali almaz mı?:

Sonuç olarak algoritmayı da şu hale dönüştürmüş oluruz:

Son duruma şöyle son bir kez göz atarsak, algoritma karmaşıklığı O(1), döngü iterasyon sayısı en fazla 14 (left-over hesabı için). Artık verilen aralıktan bağımsız olarak sabit bit t sürede çalışacak bir algoritmamız mevcut…

Şimdiye kadar yaptığımız tüm işlemler çalışma süresiyle alakalı optimize işlemleriydi. Kaynak tüketimini de ele alırsak mevcut algoritmayı, okunabilirlikten feragat ederek, şu şekilde son haline optimize edebiliriz:

Artık test işlemlerine başlayabiliriz. Teorik olarak yaptığımız tüm bu optimize işlemleri gerçekten de çalışma süresini ve kaynak tüketimini etkiledi mi? Ben süre ile ilgili test kodumu ve ekran görüntüsünü vereyim, kaynak tüketimini siz değerlendirin :)

Optimizasyon

Problemi daha detaylı inceleyip, matematiği işin içine biraz daha fazla katarak daha hızlı bir algoritma elde edilebiliyor. Fakat o mevcut algoritmayı optimize etmekten ziyade “the ultimate” algoritmayı üretmek olduğu için ele almıyorum :)

Bu akşamlık bu kadar… Herkese iyi akşamlar..

It’s good to be back ;)

Etiket(ler): , , , .Yer işareti koy Kalıcı Bağlantı.

Bir Cevap Yazın