Subset Sum Algoritmasının Optimizasyonu ve Paralelleştirilmesi
Subset Sum probleminde eşleşen alt kümeleri saymak için farklı algoritmaları karşılaştırdığım; 2^n arama uzayı, dinamik programlama ve iş parçacığı tabanlı paralelliği birlikte incelediğim optimizasyon projesi.
Bu proje, verilen bir tam sayı kümesinde elemanları toplamı hedef değere eşit olan alt kümeleri bulma ve sayma problemini farklı algoritmik yaklaşımlarla karşılaştırdığım çalışmadır.
Dönemin testinde n = 23 eleman için olası alt küme sayısı:
2^23 = 8.388.608olarak büyüyordu. Hedef toplam 200 seçildiğinde mevcut proje kaydında 17.891 eşleşen alt küme bulunduğu belirtilmiştir.
Brute Force ve Arama Uzayı
Her alt kümeyi tek tek üretmek doğrudan bir çözüm verir; ancak eleman sayısı arttıkça arama uzayı üstel büyür. n eleman için 2^n olasılık, küçük görünen bir n artışında bile işlem miktarını hızla büyütür.
Bu proje üzerinde çalışırken yalnız döngüyü hızlandırmanın yeterli olmadığını, önce aynı alt problemlerin tekrar hesaplanıp hesaplanmadığına bakmak gerektiğini gördüm.
Dinamik Programlama
Girdi değerleri ve hedef toplam uygun olduğunda dinamik programlama, bütün alt kümeleri açıkça üretmek yerine ulaşılabilir toplamlar veya her toplam için eşleşme sayıları üzerinden ilerleyebilir.
Bu yaklaşımın maliyeti 2^n yerine hedef toplamla ilişkili sözde polinom (pseudo-polynomial) bir yapıya dönüşebilir. Bu nedenle hedef değerin büyüklüğü ve değerlerin işaretleri, algoritmanın pratik maliyetini doğrudan etkiler.
Dolayısıyla "dinamik programlama her Subset Sum girdisinde hızlıdır" gibi genel bir sonuç doğru değildir. Projenin test veri kümesinde belirgin avantaj sağlamıştır.
Paralel Çalıştırma
Brute-force arama alanının bağımsız bölümleri farklı iş parçacıklarına dağıtılabilir. Dönemin proje kaydında paralel sürümün ilgili test koşullarında işlem süresini yaklaşık beşte bire indirdiği belirtilmiştir.
Bu sonucu bugünün performans yaklaşımıyla donanımdan bağımsız bir hızlanma oranı olarak sunmuyorum. Çekirdek sayısı, iş bölümü, senkronizasyon maliyeti ve bellek davranışı bilinmeden 5x gibi bir sonuç genellenemez.
Ölçüm Disiplini
Projede başlangıç ve bitiş sürelerini ortak yardımcı fonksiyonlarla ölçüyordum. Bugün aynı karşılaştırmayı yaparken ısınma, tekrar sayısı, aynı giriş kopyası, CPU yükü ve istatistiksel dağılım gibi koşulları ayrıca sabitlerdim.
Subset Sum'ın algoritmik çerçevesi ve dinamik programlama ilişkisi Veri Yapıları ve Algoritma Analizi notlarımın uygulamalı örneklerinden biridir.
