Birleştirme algoritması - Merge algorithm

Birleştirme algoritmaları , girdi olarak birden çok sıralanmış listeyi alan ve çıktı olarak tek bir liste oluşturan, giriş listelerinin tüm öğelerini sıralı bir şekilde içeren bir algoritma ailesidir . Bu algoritmalar , en ünlüsü birleştirme sıralaması olan çeşitli sıralama algoritmalarında alt rutinler olarak kullanılır .

Uygulama

Birleştirilmiş sıralama için bir örnek

Birleştirme algoritması , karşılaştırmaya dayalı bir sıralama algoritması olan birleştirme sıralama algoritmasında kritik bir rol oynar . Kavramsal olarak, birleştirme sıralama algoritması iki adımdan oluşur:

  1. Listeyi, her bir alt liste yalnızca bir öğe içerene kadar (kabaca) eşit uzunluktaki alt listelere yinelemeli olarak bölün veya yinelemeli (aşağıdan yukarıya) birleştirme sıralama durumunda, n öğeden oluşan bir listeyi, 1 boyutunda n alt liste olarak düşünün. tek bir öğe içeren liste, tanım gereği sıralanır.
  2. Tek liste tüm öğeleri içerene kadar yeni bir sıralanmış alt liste oluşturmak için alt listeleri tekrar tekrar birleştirin. Tek liste, sıralanmış listedir.

Birleştirme algoritması, birleştirme sıralama algoritmasında tekrar tekrar kullanılır.

Resimde örnek bir birleştirme sıralaması verilmiştir. Sıralanmamış bir 7 tamsayı dizisiyle başlar. Dizi 7 bölüme ayrılmıştır; her bölüm 1 eleman içerir ve sıralanır. Sıralanan bölümler daha sonra, sıralanmış dizi olan 1 bölüm kalana kadar daha büyük, sıralanmış bölümler üretmek için birleştirilir.

İki listeyi birleştirme

İki sıralı listeyi tek bir listede birleştirmek, doğrusal zamanda ve doğrusal veya sabit uzayda (veri erişim modeline bağlı olarak) yapılabilir. Aşağıdaki sözde kod , giriş listelerini ( bağlı listeler veya diziler ) A ve B'yi yeni bir C listesinde birleştiren bir algoritmayı gösterir . Head işlevi , bir listenin ilk öğesini verir; Bir öğeyi "bırakmak", tipik olarak bir işaretçiyi veya dizini artırarak onu listesinden çıkarmak anlamına gelir.

algorithm merge(A, B) is
    inputs A, B : list
    returns list

    C := new empty list
    while A is not empty and B is not empty do
        if head(A) ≤ head(B) then
            append head(A) to C
            drop the head of A
        else
            append head(B) to C
            drop the head of B

    // By now, either A or B is empty. It remains to empty the other input list.
    while A is not empty do
        append head(A) to C
        drop the head of A
    while B is not empty do
        append head(B) to C
        drop the head of B

    return C

Girişler bağlantılı listeler olduğunda, bu algoritma yalnızca sabit miktarda çalışma alanı kullanacak şekilde uygulanabilir; listelerin düğümlerindeki işaretçiler, defter tutma ve nihai birleştirilmiş listeyi oluşturmak için yeniden kullanılabilir.

Birleştirme sıralama algoritmasında, bu alt rutin tipik olarak tek bir A dizisinin iki alt dizisini A[lo..mid] , A[mid+1..hi] birleştirmek için kullanılır . Bu, alt dizileri geçici bir diziye kopyalayarak ve ardından yukarıdaki birleştirme algoritmasını uygulayarak yapılabilir. Geçici bir dizinin tahsisinden kaçınılabilir, ancak hız ve programlama kolaylığı pahasına. Çeşitli yerinde birleştirme algoritmaları geliştirilmiştir, bazen bir O ( n log n ) algoritması üretmek için doğrusal zaman sınırını feda eder ; tartışma için bkz. Birleştirme sıralama § Varyantlar .

K-yollu birleştirme

k- yollu birleştirme, ikili birleştirmeyi , sıralanmış giriş listelerinin rastgele bir sayısı olan k'ye genelleştirir . K- yollu birleştirme uygulamaları, sabırla sıralama ve girdisini k = olarak bölen harici bir sıralama algoritması dahil olmak üzere çeşitli sıralama algoritmalarında ortaya çıkar. 1/M Belleğe sığan 1 blok, bunları tek tek sıralar ve ardından bu blokları birleştirir.

Bu soruna çeşitli çözümler mevcuttur. Naif bir çözüm, her seferinde minimum öğeyi seçmek için k listeleri üzerinde bir döngü yapmak ve tüm listeler boşalana kadar bu döngüyü tekrarlamaktır:

  • Girdi: k listesinin bir listesi .
  • Listelerden herhangi biri boş olmasa da:
    • Minimum ilk öğeye sahip olanı bulmak için listeler üzerinde dolaşın.
    • Minimum öğeyi çıkarın ve listesinden kaldırın.

En kötü durumda , bu algoritma ( k −1)( nk/2) listelerde toplam n öğe varsa işini gerçekleştirmek için öğe karşılaştırmaları . Listeleri , ilk öğeleri tarafından anahtarlanan bir öncelik kuyruğunda ( min-heap ) depolayarak geliştirilebilir :

  • İlk öğeyi anahtar olarak kullanarak k listelerinden bir min-yığın h oluşturun .
  • Listelerden herhangi biri boş olmasa da:
    • Let i = find-min ( h ) .
    • Liste i'nin ilk öğesini çıkarın ve listesinden kaldırın.
    • Yeniden yığınla h .

Çıktı alınacak bir sonraki en küçük öğeyi aramak (find-min) ve yığın sırasını geri yüklemek artık O (log k ) zamanında (daha spesifik olarak, 2⌊log k karşılaştırmaları) yapılabilir ve tam problem O'da çözülebilir. ( n log k ) zaman (yaklaşık 2 n ⌊log k karşılaştırma).

Sorun için üçüncü bir algoritma , ikili birleştirme algoritmasını temel alan bir böl ve yönet çözümüdür:

  • Eğer k = 1 , çıkış tek girişli listesi.
  • Eğer k = 2 , ikili birleştirme gerçekleştirin.
  • Else, yinelemeli ilk birleştirme k / 2⌋ listeleri ve nihai k / 2⌉ listeleri, daha sonra ikili birleştirme bunlar.

Bu algoritma için, giriş listeleri uzunluğuna göre zaman, kısa ilk olarak, daha az gerektiren n ⌈log k karşılaştırmalar, yani daha az bellek tabanlı algoritma tarafından kullanılır yarım sayıdan; pratikte, yığın tabanlı algoritma kadar hızlı veya yavaş olabilir.

paralel birleştirme

Bir paralel ikili birleştirme algoritması versiyonu bir yapı taşı olarak hizmet verebilir paralel birleştirme tür . Aşağıdaki sözde kod, bu algoritmayı paralel bir böl ve yönet tarzında gösterir (Cormen ve ark.'dan uyarlanmıştır ). A ve B sıralı iki dizide çalışır ve sıralanan çıktıyı C dizisine yazar . Notasyonu A [i ... j] kalan kısmını ifade A dizinden i yoluyla j münhasır.

algorithm merge(A[i...j], B[k...ℓ], C[p...q]) is
    inputs A, B, C : array
           i, j, k, ℓ, p, q : indices

    let m = j - i,
        n = ℓ - k

    if m < n then
        swap A and B  // ensure that A is the larger array: i, j still belong to A; k, ℓ to B
        swap m and n

    if m ≤ 0 then
        return  // base case, nothing to merge

    let r = ⌊(i + j)/2⌋
    let s = binary-search(A[r], B[k...ℓ])
    let t = p + (r - i) + (s - k)
    C[t] = A[r]

    in parallel do
        merge(A[i...r], B[k...s], C[p...t])
        merge(A[r+1...j], B[s...ℓ], C[t+1...q])

Algoritma, A veya B'den hangisi daha büyükse onu (neredeyse) eşit yarıya bölerek çalışır. Daha sonra diğer diziyi, birincinin orta noktasından daha küçük değerlere sahip bir parçaya ve daha büyük veya eşit değerlere sahip bir parçaya böler. ( İkili arama altprogram döner Endeks B burada A [ r ] bu olsaydı, olacaktır B ; arasındaki bu her zaman bir sayı olduğu , k ve .) Son olarak, yarım her çift birleştirilir yinelemeli ve yinelemeli aramalar yana birbirinden bağımsızdır, paralel olarak yapılabilirler. Özyineleme temel durumu için seri algoritmanın kullanıldığı hibrit yaklaşımın pratikte iyi performans gösterdiği gösterilmiştir.

Çalışma toplam tutan iki dizi için algoritması tarafından gerçekleştirilen N yani elemanlar, bunun bir seri versiyonunun çalışma süresi, bir O ( n ) . n öğenin C'ye kopyalanması gerektiğinden bu en uygunudur . Hesaplamak için yayılma algoritması, bir elde etmek için gerekli olan Yineleme ilişkisi . İki özyinelemeli birleştirme çağrısı paralel olduğundan, yalnızca iki çağrının daha maliyetli olanı dikkate alınmalıdır. En kötü durumda, özyinelemeli çağrılardan birindeki maksimum öğe sayısı en fazla, çünkü daha fazla öğeye sahip dizi tam olarak ikiye bölünür. İkili Aramanın maliyetini ekleyerek, bu tekrarı bir üst sınır olarak elde ederiz:

Çözüm, sınırsız sayıda işlemciye sahip ideal bir makinede bu kadar zaman alması anlamına gelir.

Not: Rutin sabit değildir : A ve B'yi bölerek eşit öğeler ayrılırsa , C'de araya eklenirler ; ayrıca , her iki girdi dizisi arasında eşit öğeler yayılırsa, A ve B'yi değiştirmek siparişi bozar. Sonuç olarak, bu algoritma sıralama için kullanıldığında kararlı olmayan bir sıralama üretir.

Dil desteği

Bazı bilgisayar dilleri , sıralanmış koleksiyonları birleştirmek için yerleşik veya kitaplık desteği sağlar .

C++

C ++ 'nın standart şablon Kütüphane fonksiyonuna sahip std :: birleştirme aralıklarını kriteri iki birleştirir yineleyicileri ve std :: inplace_merge iki ardışık sıralı aralıklar birleştirir, yerinde . Ayrıca, std::list (bağlı liste) sınıfının, başka bir listeyi kendi içinde birleştiren kendi birleştirme yöntemi vardır. Birleştirilen öğelerin türü, küçük ( < ) operatörünü desteklemeli veya özel bir karşılaştırıcı ile sağlanmalıdır.

C++17, sıralı, paralel ve paralel sırasız olmak üzere farklı yürütme ilkelerine izin verir.

piton

Python'un standart kitaplığı (2.6'dan beri) ayrıca, heapq modülünde birden çok sıralı yinelenebilir alan ve bunları tek bir yineleyicide birleştiren bir birleştirme işlevine sahiptir .

Ayrıca bakınız

Referanslar

daha fazla okuma

Dış bağlantılar