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.
Yaklaşık 5x olarak kaydedilen hızlanma yalnız o test düzenine aittir. Çekirdek sayısı, iş bölümü, senkronizasyon maliyeti ve bellek davranışı bilinmeden donanımdan bağımsız bir ölçeklenme sonucu olarak kullanılamaz.
Ölçüm Disiplini
Projede başlangıç ve bitiş sürelerini ortak yardımcı fonksiyonlarla ölçüyordum. Tekrarlanabilir bir benchmark için ayrıca ısınma, tekrar sayısı, aynı giriş kopyası, CPU yükü ve ölçüm dağılımı gibi koşulların sabitlenmesi gerekir.
Subset Sum'ın algoritmik çerçevesi ve dinamik programlama ilişkisi Veri Yapıları ve Algoritma Analizi notlarımın uygulamalı örneklerinden biridir.
