Merge sort algoritması, verilen bir diziyi her adımda ikiye bölen ve bu işlemi her eleman bir liste içinde olana kadar devam eden bir algoritmadır.
Her bir eleman bir diziye ekleninceye kadar bölündükten sonra karşılaştırma ve birleştirme işlemi başlar. Yani listelerdeki elemanlar birleştirilirken büyüklüklerine göre sıralanarak birleştirilir.
Merge sort algoritması zaman karmaşıklığı bakımından best case, average case ve worst case gibi durumların hepsinde (n log n) gibi bir hıza ulaşarak en stabil sıralama algoritması olmayı başarmıştır. Merge sort'un dezavantajı ise sürekli olarak veriyi kopyalamak gerektiği için hafızayı daha fazla kullanmasıdır. Büyük miktarda verilerle uğraşırken merge sort çok kullanışlıdır. Bu hızı daha da arttırmak için Python ile Paralel Programlama tekniğinden faydalanacağız.
PYTHON PARALEL PROGRAMLAMA (Multiprocessing)
Python'da multiprocessing özelliğini kullanabilmemiz için bir kaç farklı kütüphane mevcut. Burada merge sort kodunu yazarken recursive bir yapı kullandığım için multiprocessing kütüphanesi bir işime yaramayacak. Çünkü bu kütüphanede bir process başka bir processi çağırırken hata verir ve recursive bir şekilde process oluşturulmasına izin vermez. Aynı şekilde Pool oluşturup map ile ya da apply function ile recursive fonksiyonu gönderip processler oluşturmak istediğimizde de hatayla karşılaşırız. Bunu bypass edecek bir kod yazabiliriz ancak bu da zahmetli bir iş olacağından bu sınırlamanın olmadığı bir kütüphane kullanmak daha mantıklı olacak.
Yapılacak olan iş, dizinin çekirdek sayısı kadar parçaya ayrılıp çekirdeklere paylaştırılması ve böylece büyük verilerde katlanan bir sıralama hızına ulaşmaktır. Bunu diagram ile gösterek olursak ortaya şöyle bir şekil çıkar:
n derinliğe inerek 2^n sayıda process oluşturur ve her bir process kendi seri merge sortunu çalıştırır. 16 çekirdekli bir sistemde 4 birim derinliğe iner ve 16 process oluşturarak her processin, dizinin ayrı bir kısmını sıralaması sağlanır. Yukarıya dönüşte ise merge işlemi gerçekleştirilerek dizi hem sıralanır hem birleştirilir.
Proje linki: https://github.com/mertcenkk/ParallelMergeSort
Hiç yorum yok:
Yorum Gönder