Birleştirme algoritması - Merge algorithm

Algoritmaları birleştirme bir aileyiz algoritmalar birden fazla alır sıralanmış giriş olarak listeler ve giriş listelerinin tüm öğelerini sıralı sırayla içeren çıktı olarak tek bir liste oluşturur. Bu algoritmalar şu şekilde kullanılır: alt programlar çeşitliliğinde sıralama algoritmaları en ünlüsü sıralamayı birleştir.

Uygulama

Birleştirme sıralaması için bir örnek

Birleştirme algoritması, sıralamayı birleştir algoritma, bir karşılaştırmaya dayalı sıralama algoritması. Kavramsal olarak, birleştirme sıralama algoritması iki adımdan oluşur:

  1. Tekrarlı her bir alt liste yalnızca bir öğe içerene kadar listeyi (kabaca) eşit uzunlukta alt listelere bölün veya yinelemeli (aşağıdan yukarıya) birleştirme sıralaması durumunda, n gibi öğeler n boyut 1 alt listeleri. Tek bir eleman içeren bir 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ıralı 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ış 7 tamsayı dizisi ile başlar. Dizi 7 bölüme ayrılmıştır; her bölüm 1 öğe içerir ve sıralanır. Sıralanan bölümler, daha büyük, sıralı bölümler oluşturmak için birleştirilir, ta ki 1 bölüm, sıralı dizi kalana kadar.

İki listeyi birleştirme

Sıralanmış iki listeyi tek bir listeyle birleştirmek, doğrusal zaman ve doğrusal veya sabit uzay (veri erişim modeline bağlı olarak). Devamındaki sözde kod giriş listelerini birleştiren bir algoritmayı gösterir ( bağlantılı listeler veya diziler ) Bir ve B yeni bir listeye C.[1][2]:104 İşlev baş 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.

algoritma birleştirme (A, B) dır-dir    girişler A, B: liste İadeler liste C: = yeni boş liste süre A boş değil ve B boş değil yapmak        Eğer kafa (A) ≤ kafa (B) sonra            başını (A) C'ye ekle A'nın başını düşür Başka            kafasını (B) C'ye ekleyin B'nin kafasını bırakın // Şimdiye kadar ya A ya da B boştur. Diğer giriş listesini boşaltmaya devam eder.    süre A boş değil yapmak        başını (A) C'ye ekle A'nın başını düşür süre B boş değil yapmak        kafasını (B) C'ye ekleyin B'nin kafasını bırakın dönüş C

Girişler bağlantılı listeler olduğunda, bu algoritma yalnızca sabit miktarda çalışma alanı kullanmak için 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 altyordam genellikle iki alt diziyi birleştirmek için kullanılır A [lo..mid], A [mid..hi] tek bir dizinin Bir. Bu, alt dizileri geçici bir diziye kopyalayıp, ardından yukarıdaki birleştirme algoritmasını uygulayarak yapılabilir.[1] Geçici bir dizinin tahsisi önlenebilir, ancak hız ve programlama kolaylığı pahasına. Çeşitli yerinde birleştirme algoritmaları tasarlandı,[3] bazen doğrusal zaman sınırını feda ederek bir Ö(n günlük n) algoritma;[4] görmek Sıralama § Varyantlarını birleştir tartışma için.

K-yolu birleştirme

Ana makale: K-yolu birleştirme algoritması

kyollu birleştirme, ikili birleştirmeyi rastgele bir sayıya genelleştirir k sıralı giriş listeleri. Uygulamaları k-yollu birleştirme çeşitli sıralama algoritmalarında ortaya çıkar: sabır sıralaması[5] ve bir dış sıralama girdisini bölen algoritma k = 1/M − 1 hafızaya sığan bloklar, bunları tek tek sıralar ve sonra bu blokları birleştirir.[2]:119–120

Bu soruna birkaç çözüm var. Saf bir çözüm, k her seferinde minimum öğeyi seçmek için listeler ve tüm listeler boşalana kadar bu döngüyü tekrarlayın:

  • Giriş: bir liste k listeler.
  • Listelerden herhangi biri boş değilken:
    • Minimum ilk öğeye sahip olanı bulmak için listelerde döngü yapın.
    • Minimum elemanı çıktılayın ve listesinden kaldırın.

En kötü durumda, bu algoritma gerçekleştirir (k−1)(n−k/2) toplam varsa, çalışmasını gerçekleştirmek için öğe karşılaştırmaları n listelerdeki öğeler.[6]Listeleri bir klasörde saklayarak geliştirilebilir. öncelik sırası (min-yığın ) ilk unsurları tarafından anahtarlanmış:

  • Bir min-yığın oluşturun h of k anahtar olarak ilk öğeyi kullanarak listeler.
  • Listelerden herhangi biri boş değilken:
    • İzin Vermek ben = bul-min (h).
    • Listenin ilk öğesini çıktılar ben ve listesinden çıkarın.
    • Yeniden yığınla h.

Çıktı alınacak bir sonraki en küçük öğeyi aramak (min bul) ve yığın sırasını geri yüklemek artık şu adresten yapılabilir: Ö(günlük k) zaman (daha spesifik olarak, 2⌊log k⌋ karşılaştırmalar[6]) ve tüm sorun şu şekilde çözülebilir: Ö(n günlük k) zaman (yaklaşık 2n⌊Log k⌋ karşılaştırmalar).[6][2]:119–120

Problem için üçüncü bir algoritma, böl ve fethet ikili birleştirme algoritmasına dayanan çözüm:

  • Eğer k = 1, tek giriş listesinin çıktısını alın.
  • Eğer k = 2, ikili birleştirme gerçekleştirin.
  • Aksi takdirde, ilkini yinelemeli olarak birleştirin ⌊k/2⌋ listeler ve final ⌈k/2⌉ listeler, sonra ikili bunları birleştirir.

Bu algoritmaya giriş listeleri uzunluğa göre sıralandığında, en kısa önce, daha azını gerektirir n⌈Log k⌉ karşılaştırmalar, yani yığın tabanlı algoritma tarafından kullanılan sayının yarısından azı; pratikte, yığın tabanlı algoritma kadar hızlı veya yavaş olabilir.[6]

Paralel birleştirme

Bir paralel ikili birleştirme algoritmasının sürümü, bir paralel birleştirme sıralaması. Aşağıdaki sözde kod, bu algoritmayı bir paralel böl ve yönet stil (Cormen'den uyarlanmıştır et al.[7]:800). İki sıralı dizide çalışır Bir ve B ve sıralanmış çıktıyı diziye yazar C. Gösterim A [i ... j] kısmını gösterir Bir dizinden ben vasıtasıyla j, özel.

algoritma birleştirme (A [i ... j], B [k ... ℓ], C [p ... q]) dır-dir    girişler A, B, C: dizi i, j, k, ℓ, p, q: indisler İzin Vermek m = j - ben, n = ℓ - k Eğer m sonra        A ve B'yi değiştir // A'nın daha büyük dizi olmasını sağlayın: i, j hala A'ya aittir; k, ℓ ila B        takas m ve n Eğer m ≤ 0 sonra        dönüş  // temel durum, birleştirilecek bir şey yok    İzin Vermek r = ⌊ (ben + j) / 2⌋ İzin Vermek s = ikili arama (A [r], B [k ... ℓ]) İzin Vermek t = p + (r - i) + (s - k) C [t] = A [r] paralel olarak yap        birleştirme (A [i ... r], B [k ... s], C [p ... t]) birleştirme (A [r + 1 ... j], B [s ... ℓ] , C [t + 1 ... q])

Algoritma her ikisini de bölerek çalışır. Bir veya B, hangisi daha büyükse, (neredeyse) eşit yarıya bölünür. Daha sonra, diğer diziyi ilkinin orta noktasından daha küçük değerlere ve daha büyük veya eşit değerlere sahip bir parçaya böler. (The Ikili arama alt rutin dizini döndürür B nerede Bir[r] içinde olsaydı olurdu B; bu her zaman arasında bir sayı k ve ℓSon olarak, her yarım çift birleştirilir. tekrarlı ve özyinelemeli çağrılar birbirinden bağımsız olduğu için paralel olarak yapılabilir. Özyineleme temel durumu için seri algoritmanın kullanıldığı hibrit yaklaşımın pratikte iyi performans gösterdiği gösterilmiştir. [8]

iş algoritma tarafından toplamı tutan iki dizi için gerçekleştirilir n öğeler, yani seri versiyonunun çalışma süresi Ö(n). Bu optimaldir çünkü n öğelerin kopyalanması gerekiyor C. Hesaplamak için açıklık Algoritmanın bir Tekrarlama ilişkisi. İki özyinelemeli çağrısından beri birleştirmek paraleldir, yalnızca iki aramanın maliyeti dikkate alınmalıdır. En kötü durumda, özyinelemeli çağrılardan birindeki maksimum eleman sayısı en fazla çünkü daha fazla eleman içeren dizi tamamen ikiye bölünmüştür. Ekleniyor İkili Aramanın maliyeti, bu yinelemeyi bir üst sınır olarak elde ederiz:

Çözüm şudur yani sınırsız sayıda işlemciye sahip ideal bir makinede bu kadar zaman alır.[7]:801–802

Not: Rutin değil kararlı: eşit öğeler bölünerek ayrılırsa Bir ve B, araya girecekler C; ayrıca takas Bir ve B her iki girdi dizisi arasında eşit öğeler yayılırsa sıralamayı yok eder. Sonuç olarak, sıralama için kullanıldığında, bu algoritma kararlı olmayan bir sıralama üretir.

Dil desteği

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

C ++

C ++ 's Standart Şablon Kitaplığı işlevi var std :: birleştirme, sıralı iki aralığı birleştiren yineleyiciler, ve std :: inplace_merge, iki ardışık sıralı aralığı birleştiren yerinde. ek olarak std :: list (bağlantılı liste) sınıfının kendine ait birleştirmek başka bir listeyi kendi içinde birleştiren yöntem. Birleştirilen öğelerin türü, küçüktür (<) operatörü veya özel bir karşılaştırıcı ile sağlanmalıdır.

C ++ 17, farklı yürütme politikalarına, yani sıralı, paralel ve paralel sırasız olarak izin verir.[9]

Python

Python standart kitaplığı (2.6'dan beri) ayrıca bir birleştirmek işlevi heapq birden çok sıralı yineleyici alan ve bunları tek bir yineleyicide birleştiren modül.[10]

Ayrıca bakınız

Referanslar

  1. ^ a b Skiena, Steven (2010). Algoritma Tasarım Kılavuzu (2. baskı). Springer Science + Business Media. s. 123. ISBN  978-1-849-96720-4.
  2. ^ a b c Kurt Mehlhorn; Peter Sanders (2008). Algoritmalar ve Veri Yapıları: Temel Araç Kutusu. Springer. ISBN  978-3-540-77978-0.
  3. ^ Katajainen, Jyrki; Pasanen, Tomi; Teuhola, Jukka (1996). "Pratik yerinde birleştirme". Nordic J. Computing. 3 (1): 27–40. CiteSeerX  10.1.1.22.8523.
  4. ^ Kim, Pok-Oğlu; Kutzner, Arne (2004). Simetrik Karşılaştırmalarla Kararlı Minimum Depolama Birleştirme. European Symp. Algoritmalar. Bilgisayar Bilimi Ders Notları. 3221. sayfa 714–723. CiteSeerX  10.1.1.102.4612. doi:10.1007/978-3-540-30140-0_63. ISBN  978-3-540-23025-0.
  5. ^ Chandramouli, Badrish; Goldstein Jonathan (2014). Sabır bir Erdemdir: Modern İşlemcileri Yeniden Birleştirme ve Sıralama. SIGMOD / PODS.
  6. ^ a b c d Greene, William A. (1993). k-yolu Birleştirme ve k-ary Sorts (PDF). Proc. 31. Yıllık ACM Güneydoğu Konf. s. 127–135.
  7. ^ a b Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2009) [1990]. Algoritmalara Giriş (3. baskı). MIT Press ve McGraw-Hill. ISBN  0-262-03384-4.
  8. ^ Victor J. Duvanenko (2011), "Paralel Birleştirme", Dr. Dobb's Journal
  9. ^ "std: birleştirme". cppreference.com. 2018-01-08. Alındı 2018-04-28.
  10. ^ https://docs.python.org/library/heapq.html#heapq.merge

daha fazla okuma

  • Donald Knuth. Bilgisayar Programlama Sanatı, Cilt 3: Sıralama ve Arama, Üçüncü baskı. Addison-Wesley, 1997. ISBN  0-201-89685-0. Bölüm 5.2.4'ün 158–160. Sayfaları: Birleştirmeye Göre Sıralama. Bölüm 5.3.2: Minimum Karşılaştırma Birleştirme, s. 197–207.

Dış bağlantılar