Sloučit algoritmus - Merge algorithm

Sloučené algoritmy jsou rodina algoritmů, které berou více seřazených seznamů jako vstup a vytvářejí jeden seznam jako výstup, který obsahuje všechny prvky vstupních seznamů v seřazeném pořadí. Tyto algoritmy se používají jako podprogramy v různých třídicích algoritmech , nejznámější sloučení řazení .

aplikace

Příklad pro sloučení řazení

Algoritmus sloučení hraje klíčovou roli v algoritmu řazení sloučení, algoritmu řazení založeném na srovnání . Koncepčně se algoritmus sloučení třídění skládá ze dvou kroků:

  1. Rekurzivně rozdělte seznam na podseznamy (zhruba) stejné délky, dokud každý podseznam neobsahuje pouze jeden prvek, nebo v případě iterativního (zdola nahoru) sloučeného řazení považujte seznam n prvků za n podseznamů velikosti 1. A seznam obsahující jeden prvek je podle definice seřazen.
  2. Opakovaně slučujte dílčí seznamy, abyste vytvořili nový seřazený dílčí seznam, dokud jediný seznam nebude obsahovat všechny prvky. Jediný seznam je seřazený seznam.

Algoritmus sloučení se v algoritmu řazení sloučení používá opakovaně.

Příklad sloučení je uveden na obrázku. Začíná to netříděným polem 7 celých čísel. Pole je rozděleno do 7 oddílů; každý oddíl obsahuje 1 prvek a je seřazen. Seřazené oddíly jsou poté sloučeny a vytvoří se větší, seřazené oddíly, dokud nezůstane 1 oddíl, seřazené pole.

Sloučení dvou seznamů

Sloučení dvou seřazených seznamů do jednoho lze provést v lineárním čase a lineárním nebo konstantním prostoru (v závislosti na modelu přístupu k datům). Následující pseudokód ukazuje algoritmus, který sloučí vstupní seznamy (buď spojové seznamy nebo pole ) a B do nové seznamu C . Funkce head poskytuje první prvek seznamu; „přetažení“ prvku znamená jeho odstranění ze seznamu, obvykle zvýšením ukazatele nebo indexu.

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

Když jsou vstupy propojené seznamy, lze tento algoritmus implementovat tak, aby používal pouze konstantní množství pracovního prostoru; ukazatele v uzlech seznamů lze znovu použít pro vedení účetnictví a pro vytvoření konečného sloučeného seznamu.

V algoritmu sloučení druhu, tento podprogram se obvykle používá k sloučit dvě dílčí pole A [lo..mid] , A [v polovině + 1..hi] z jednoho pole A . To lze provést zkopírováním dílčích polí do dočasného pole a následným použitím algoritmu sloučení výše. Alokaci dočasného pole se lze vyhnout, ale na úkor rychlosti a snadné programování. Byly navrženy různé algoritmy slučování na místě, které někdy obětovaly lineárně vázaný čas k vytvoření algoritmu O ( n log n ) ; pro diskusi viz Sloučit řazení § Varianty .

Sloučení K-way

k -wayové sloučení zobecňuje binární sloučení na libovolný počet k seřazených vstupních seznamů. Aplikace slučování k -way vznikají v různých třídicích algoritmech, včetně třídění trpělivosti a externího třídicího algoritmu, který rozděluje jeho vstup na k = 1/M- 1 bloky, které se vejdou do paměti, seřadí je jeden po druhém a poté tyto bloky sloučí.

Existuje několik řešení tohoto problému. Naivním řešením je udělat smyčku nad seznamy k, abyste pokaždé vybrali minimální prvek, a opakovat tuto smyčku, dokud nebudou všechny seznamy prázdné:

  • Vstup: seznam k seznamů.
  • Zatímco některý ze seznamů není prázdný:
    • Projděte seznamy a najděte ten s minimem prvního prvku.
    • Výstup minimálního prvku a odebrání ze seznamu.

V nejhorším případě tento algoritmus provádí ( k -1) ( n -k/2) porovnání prvků k provedení své práce, pokud je v seznamech celkem n prvků. Lze to vylepšit ukládáním seznamů do prioritní fronty ( min. Haldy ) s klíčem podle jejich prvního prvku:

  • Postavit min-haldy h o k- seznamů, pomocí první prvek jako klíč.
  • Zatímco některý ze seznamů není prázdný:
    • Nechť i = find-min ( h ) .
    • Výstup prvního prvku seznamu i a odebrání ze seznamu.
    • Znovu heapify h .

Hledání další nejmenší prvek, který je výstupem (find-min) a vratnou haldy pořadí nyní může být provedeno v O (log K ) času (konkrétně 2⌊log k porovnání), a celý problém může být vyřešen v O ( n log k ) čas (přibližně 2 n ⌊ log k srovnání).

Třetím algoritmem problému je řešení rozděl a panuj, které staví na algoritmu binárního sloučení:

  • Pokud k = 1 , vypíše seznam jednotlivých vstupů.
  • Pokud k = 2 , proveďte binární sloučení.
  • Jinak rekurzivně sloučte první seznamy k / 2⌋ a konečné seznamy k / 2⌉ a poté je binárně sloučte .

Když jsou vstupní seznamy tohoto algoritmu seřazeny podle délky, nejkratší, vyžaduje méně než n thanlog k srovnání, tj. Méně než polovinu počtu použitého haldy založeným algoritmem; v praxi to může být asi tak rychlé nebo pomalé jako haldy založený algoritmus.

Paralelní sloučení

Paralelní verze binárního algoritmu korespondence může sloužit jako stavební kámen v rámci paralelního sloučení druhu . Následující pseudokód demonstruje tento algoritmus ve stylu paralelního rozdělení a dobývání (převzato z Cormen et al. ). Působí na dvou tříděných polí A a B a zapíše seřazený výstup matice C . Zápis A [i ... j] označuje část A z indexu ij , exkluzivní.

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])

Algoritmus pracuje rozdělením buď A nebo B , podle toho, co je větší, na (téměř) stejné poloviny. Poté rozděluje druhé pole na část s hodnotami menšími než střed prvního a část s většími nebo stejnými hodnotami. ( Subrutina binárního vyhledávání vrací index v B, kde A [ r ] by bylo, pokud by bylo v B ; že toto je vždy číslo mezi k a .) Nakonec je každá dvojice polovin sloučena rekurzivně a protože rekurzivní volání jsou na sobě nezávislé, lze je provádět paralelně. Ukázalo se, že hybridní přístup, kdy se pro základní případ rekurze používá sériový algoritmus, v praxi funguje dobře

Práce provádí pomocí algoritmu pro dvou matic drží celkem n prvků, jako je doba chodu sériového verze je, je O ( n ) . To je optimální, protože n prvky musí být zkopírovány do C . Pro výpočet rozpětí algoritmu je nutné odvodit relaci Opakování . Jelikož jsou dvě rekurzivní volání sloučení paralelní, je třeba vzít v úvahu pouze nákladnější z těchto dvou hovorů. V nejhorším případě je maximální počet prvků v jednom z rekurzivních volání nanejvýš, protože pole s více prvky je dokonale rozděleno na polovinu. Přidáním nákladů na binární vyhledávání získáme toto opakování jako horní hranici:

Řešení je , což znamená, že to trvá tolik času na ideálním stroji s neomezeným počtem procesorů.

Poznámka: Rutina není stabilní : pokud jsou stejné položky odděleny rozdělením A a B , budou prokládány v C ; také výměna A a B zničí pořadí, pokud jsou mezi oběma vstupními poli rozloženy stejné položky. Výsledkem je, že při použití pro třídění tento algoritmus vytvoří druh, který není stabilní.

Jazyková podpora

Některé počítačové jazyky poskytují integrovanou nebo knihovní podporu pro slučování tříděných sbírek .

C ++

The C ++ je standardní šablonová knihovna má funkci std :: korespondence , který slučuje dva seřazeny rozsahy iterátorů a std :: inplace_merge , která slučuje dvě po sobě jdoucí setříděné rozsahy v místě . Kromě toho, std :: seznam (spojový seznam) třída má svou vlastní slučovací způsob, který přechází další seznam do sebe. Typ sloučených prvků musí podporovat operátor less-than ( < ), nebo musí být poskytnut s vlastním komparátorem.

C ++ 17 umožňuje různé zásady provádění, jmenovitě sekvenční, paralelní a paralelně nesekvenované.

Krajta

Standardní knihovna Pythonu (od 2.6) má také funkci sloučení v modulu heapq , která přebírá několik seřazených iterable a slučuje je do jednoho iterátoru.

Viz také

Reference

Další čtení

externí odkazy