Sloučit třídění - Merge sort

Sloučit třídění

Příklad sloučení. Nejprve rozdělte seznam na nejmenší jednotku (1 prvek), poté porovnejte každý prvek se sousedním seznamem a seřaďte a sloučte dva sousední seznamy. Nakonec jsou všechny prvky seřazeny a sloučeny.
Třída	Algoritmus řazení
Datová struktura	Pole
Nejhorší výkon	${\ Displaystyle O (n \ log n)}$
Nejlepší výkon	${\ displaystyle \ Omega (n \ log n)}$typická, přírodní varianta${\ displaystyle \ Omega (n)}$
Průměrný výkon	${\ displaystyle \ Theta (n \ log n)}$
Nejhorší prostorová složitost	${\ Displaystyle O (n)}$celkem s pomocnými, pomocnými s propojenými seznamy${\ Displaystyle O (n)}$${\ displaystyle O (1)}$

V počítačové vědě je sloučení (také běžně hláskované jako mergesort ) účinný, univerzální a srovnávací algoritmus řazení . Většina implementací produkuje stabilní třídění , což znamená, že pořadí stejných prvků je stejné na vstupu i výstupu. Sloučení třídění je algoritmus rozděl a panuj, který vynalezl John von Neumann v roce 1945. Podrobný popis a analýza sloučení typu zdola nahoru se objevila ve zprávě Goldstina a von Neumanna již v roce 1948.

Algoritmus

Slučovací řazení koncepčně funguje následovně:

1. Rozdělte netříděný seznam do n podsložek, z nichž každý obsahuje jeden prvek (seznam jednoho prvku je považován za seřazený).
2. Opakovaně sloučit sublists produkovat nové setříděné sublists dokud je tam jen jeden podseznam zbývající. Toto bude seřazený seznam.

Implementace shora dolů

Příklad kódu podobného C používajícího indexy pro algoritmus řazení shora shora, který rekurzivně rozděluje seznam ( v tomto příkladu se nazývá spuštění ) na podseznamy, dokud velikost seznamu není 1, a poté tyto podseznamy sloučí k vytvoření seřazeného seznamu. Krok zpětného kopírování se vyhne střídáním směru sloučení s každou úrovní rekurze (kromě počáteční jednorázové kopie). Abyste tomu porozuměli, zvažte pole se dvěma prvky. Prvky jsou zkopírovány do B [], poté sloučeny zpět do A []. Pokud existují čtyři prvky, dosáhne-li se spodní části rekurzivní úrovně, spouštějí se jednotlivé prvky z A [] do B [] a pak na další vyšší úrovni rekurze se tyto dvouprvkové sloučí do A [ ]. Tento vzorec pokračuje s každou úrovní rekurze.

// Array A[] has the items to sort; array B[] is a work array.
void TopDownMergeSort(A[], B[], n)
{
    CopyArray(A, 0, n, B);           // one time copy of A[] to B[]
    TopDownSplitMerge(B, 0, n, A);   // sort data from B[] into A[]
}

// Split A[] into 2 runs, sort both runs into B[], merge both runs from B[] to A[]
// iBegin is inclusive; iEnd is exclusive (A[iEnd] is not in the set).
void TopDownSplitMerge(B[], iBegin, iEnd, A[])
{
    if (iEnd - iBegin <= 1)                     // if run size == 1
        return;                                 //   consider it sorted
    // split the run longer than 1 item into halves
    iMiddle = (iEnd + iBegin) / 2;              // iMiddle = mid point
    // recursively sort both runs from array A[] into B[]
    TopDownSplitMerge(A, iBegin,  iMiddle, B);  // sort the left  run
    TopDownSplitMerge(A, iMiddle,    iEnd, B);  // sort the right run
    // merge the resulting runs from array B[] into A[]
    TopDownMerge(B, iBegin, iMiddle, iEnd, A);
}

//  Left source half is A[ iBegin:iMiddle-1].
// Right source half is A[iMiddle:iEnd-1   ].
// Result is            B[ iBegin:iEnd-1   ].
void TopDownMerge(A[], iBegin, iMiddle, iEnd, B[])
{
    i = iBegin, j = iMiddle;
 
    // While there are elements in the left or right runs...
    for (k = iBegin; k < iEnd; k++) {
        // If left run head exists and is <= existing right run head.
        if (i < iMiddle && (j >= iEnd || A[i] <= A[j])) {
            B[k] = A[i];
            i = i + 1;
        } else {
            B[k] = A[j];
            j = j + 1;
        }
    }
}

void CopyArray(A[], iBegin, iEnd, B[])
{
    for (k = iBegin; k < iEnd; k++)
        B[k] = A[k];
}

Třídění celého pole se provádí pomocí TopDownMergeSort (A, B, délka (A)) .

Implementace zdola nahoru

Příklad kódu podobného C používající indexy pro algoritmus sloučení shora dolů, který zachází se seznamem jako s řadou n podsložek ( v tomto příkladu nazývaných běží ) o velikosti 1 a iterativně sloučí dílčí seznamy tam a zpět mezi dvěma vyrovnávacími paměťmi:

// array A[] has the items to sort; array B[] is a work array
void BottomUpMergeSort(A[], B[], n)
{
    // Each 1-element run in A is already "sorted".
    // Make successively longer sorted runs of length 2, 4, 8, 16... until the whole array is sorted.
    for (width = 1; width < n; width = 2 * width)
    {
        // Array A is full of runs of length width.
        for (i = 0; i < n; i = i + 2 * width)
        {
            // Merge two runs: A[i:i+width-1] and A[i+width:i+2*width-1] to B[]
            // or copy A[i:n-1] to B[] ( if (i+width >= n) )
            BottomUpMerge(A, i, min(i+width, n), min(i+2*width, n), B);
        }
        // Now work array B is full of runs of length 2*width.
        // Copy array B to array A for the next iteration.
        // A more efficient implementation would swap the roles of A and B.
        CopyArray(B, A, n);
        // Now array A is full of runs of length 2*width.
    }
}

//  Left run is A[iLeft :iRight-1].
// Right run is A[iRight:iEnd-1  ].
void BottomUpMerge(A[], iLeft, iRight, iEnd, B[])
{
    i = iLeft, j = iRight;
    // While there are elements in the left or right runs...
    for (k = iLeft; k < iEnd; k++) {
        // If left run head exists and is <= existing right run head.
        if (i < iRight && (j >= iEnd || A[i] <= A[j])) {
            B[k] = A[i];
            i = i + 1;
        } else {
            B[k] = A[j];
            j = j + 1;    
        }
    } 
}

void CopyArray(B[], A[], n)
{
    for (i = 0; i < n; i++)
        A[i] = B[i];
}

Implementace shora dolů pomocí seznamů

Pseudokód pro algoritmus sloučení shora dolů, který rekurzivně rozděluje vstupní seznam na menší podseznamy, dokud nejsou podseznamy triviálně seřazeny, a poté sloučí podseznamy při návratu do řetězce volání.

function merge_sort(list m) is
    // Base case. A list of zero or one elements is sorted, by definition.
    if length of m ≤ 1 then
        return m

    // Recursive case. First, divide the list into equal-sized sublists
    // consisting of the first half and second half of the list.
    // This assumes lists start at index 0.
    var left := empty list
    var right := empty list
    for each x with index i in m do
        if i < (length of m)/2 then
            add x to left
        else
            add x to right

    // Recursively sort both sublists.
    left := merge_sort(left)
    right := merge_sort(right)

    // Then merge the now-sorted sublists.
    return merge(left, right)

V tomto případě slučovací funkce sloučí levý a pravý dílčí seznam.

function merge(left, right) is
    var result := empty list

    while left is not empty and right is not empty do
        if first(left) ≤ first(right) then
            append first(left) to result
            left := rest(left)
        else
            append first(right) to result
            right := rest(right)

    // Either left or right may have elements left; consume them.
    // (Only one of the following loops will actually be entered.)
    while left is not empty do
        append first(left) to result
        left := rest(left)
    while right is not empty do
        append first(right) to result
        right := rest(right)
    return result

Implementace zdola nahoru pomocí seznamů

Pseudokód pro spojovací algoritmus sloučení zdola nahoru, který používá malé pole s pevnou velikostí odkazů na uzly, kde pole [i] je buď odkazem na seznam velikosti 2 ^i, nebo nula . node je odkaz nebo ukazatel na uzel. Funkce merge () by byla podobná té, která je uvedena v příkladu shlukových seznamů shora dolů, sloučí dva již seřazené seznamy a zpracovává prázdné seznamy. V tomto případě merge () použije uzel pro své vstupní parametry a návratovou hodnotu.

function merge_sort(node head) is
    // return if empty list
    if head = nil then
        return nil
    var node array[32]; initially all nil
    var node result
    var node next
    var int  i
    result := head
    // merge nodes into array
    while result ≠ nil do
        next := result.next;
        result.next := nil
        for (i = 0; (i < 32) && (array[i] ≠ nil); i += 1) do
            result := merge(array[i], result)
            array[i] := nil
        // do not go past end of array
        if i = 32 then
            i -= 1
        array[i] := result
        result := next
    // merge array into single list
    result := nil
    for (i = 0; i < 32; i += 1) do
        result := merge(array[i], result)
    return result

Přirozené sloučení

Přirozené sloučení je podobné sloučení typu zdola nahoru s tím rozdílem, že jsou zneužity všechny přirozeně se vyskytující běhy (seřazené sekvence) na vstupu. Lze využít jak monotónní, tak bitonické (střídavé nahoru/dolů) běhy, přičemž vhodnými datovými strukturami jsou seznamy (nebo ekvivalentně pásky nebo soubory) (používané jako fronty FIFO nebo zásobníky LIFO ). Při řazení sloučením zdola nahoru výchozí bod předpokládá, že každý běh je dlouhý jednu položku. V praxi budou mít náhodná vstupní data mnoho krátkých běhů, které se náhodou roztřídí. V typickém případě nemusí přirozené třídění sloučení potřebovat tolik průchodů, protože ke sloučení je méně běhů. V nejlepším případě je vstup již seřazen (tj. Je to jeden běh), takže při přirozeném sloučení stačí provést pouze jeden průchod dat. V mnoha praktických případech jsou přítomny dlouhé přirozené běhy, a proto je přirozené sloučení jako klíčová součást Timsortu využíváno . Příklad:

Start       :  3  4  2  1  7  5  8  9  0  6
Select runs : (3  4)(2)(1  7)(5  8  9)(0  6)
Merge       : (2  3  4)(1  5  7  8  9)(0  6)
Merge       : (1  2  3  4  5  7  8  9)(0  6)
Merge       : (0  1  2  3  4  5  6  7  8  9)

Formálně je přirozené sloučení považováno za běhy -optimální, kde je počet běhů v mínus jeden. ${\ displaystyle {\ mathtt {Runs}} (L)}$${\ displaystyle L}$

Druhy výběru náhrad turnajů se používají ke shromáždění počátečních běhů pro externí třídící algoritmy.

Analýza

Algoritmus rekurzivního slučovacího řazení používaný k třídění pole 7 celočíselných hodnot. Toto jsou kroky, které by člověk udělal k emulaci sloučení (shora dolů).

V třídění n objektů, sloučení má třídit je průměrný a nejhorší možný výkon v O ( n  log  n ). Pokud je doba chodu slučování, třídění pro seznam délky n je T ( n ), pak je vztah opakování T ( n ) = 2 T ( n / 2) + n vyplývá z definice algoritmu (aplikovat algoritmus na dva seznamy o poloviční velikosti oproti původnímu seznamu a přidejte n kroků provedených ke sloučení výsledných dvou seznamů). Uzavřená forma vyplývá z hlavní věty pro opakování rozděl a panuj .

Počet srovnání provedených sloučením řazení v nejhorším případě je dán čísly řazení . Tato čísla jsou stejná nebo mírně menší než ( n  ⌈ lg  n ⌉ - 2 ^{⌈lg  n ⌉} + 1), což je mezi ( n  lg  n - n + 1) a ( n  lg  n + n + O (lg  n ) ). Nejlepší případ sloučení má asi polovinu počtu iterací než jeho nejhorší případ.

Pro velký n a náhodně seřazený seznam vstupů se očekávaný (průměrný) počet sloučení třídění blíží α · n méně než nejhorší případ, kde${\ Displaystyle \ alpha = -1+\ sum _ {k = 0}^{\ infty} {\ frac {1} {2^{k} +1}} \ cca 0,2645.}$

V nejhorším případě sloučení řazení používá přibližně o 39% méně srovnání než quicksort ve svém průměrném případě, a pokud jde o pohyby, nejhorší případ sloučení řazení je O ( n  log  n ) - stejná složitost jako nejlepší případ quicksortu.

Sloučení třídění je u některých typů seznamů efektivnější než rychlé řazení, pokud k datům, která mají být tříděna, lze efektivně přistupovat pouze postupně, a je proto populární v jazycích, jako je Lisp , kde jsou sekvenční přístupové datové struktury velmi běžné. Na rozdíl od některých (efektivních) implementací quicksortu je sloučení řazení stabilním tříděním.

Nejběžnější implementace sloučení sort se netřídí na místě; proto velikost paměti vstupu musí být přidělena, aby byl tříděný výstup uložen (viz níže varianty, které vyžadují pouze n /2 mezery navíc).

Varianty

Varianty sloučení jsou primárně zaměřeny na snížení prostorové složitosti a nákladů na kopírování.

Jednoduchou alternativou pro snížení režie prostoru na n /2 je zachování levé a pravé jako kombinované struktury, zkopírování pouze levé části m do dočasného prostoru a nasměrování rutiny sloučení k umístění sloučeného výstupu do m . U této verze je lepší přidělit dočasný prostor mimo rutinu sloučení , aby bylo potřeba pouze jedno přidělení. Zmíněné nadměrné kopírování, které jsme zmínili dříve, je také zmírněno, protože poslední pár řádků před návratovým výsledkem ( sloučení funkce v pseudo kódu výše) se stává nadbytečným.

Jednou nevýhodou slučovacího řazení při implementaci do polí je jeho požadavek na pracovní paměť O ( n ) . Bylo navrženo několik místních variant:

• Katajainen a kol. předložit algoritmus, který vyžaduje konstantní množství pracovní paměti: dostatek úložného prostoru pro uložení jednoho prvku vstupního pole a další prostor pro uložení ukazatelů O (1) do vstupního pole. Dosahují časového limitu O ( n log n ) s malými konstantami, ale jejich algoritmus není stabilní.
• Bylo provedeno několik pokusů o vytvoření místního slučovacího algoritmu, který lze zkombinovat se standardním (shora dolů nebo zdola nahoru) slučovacím tříděním za účelem vytvoření sloučení na místě. V tomto případě může být pojem „na místě“ uvolněn ve smyslu „zabírání logaritmického prostoru zásobníku“, protože standardní slučovací třídění vyžaduje takové množství prostoru pro vlastní využití zásobníku. Ukázali to Geffert et al. že na místě je možné stabilní sloučení v čase O ( n log n ) s použitím konstantního množství škrábaného prostoru, ale jejich algoritmus je komplikovaný a má vysoké konstantní faktory: sloučení polí délky n a m může trvat 5 n + 12 m + o ( m ) pohyby. Tento vysoký konstantní faktor a komplikovaný místní algoritmus byly jednodušší a srozumitelnější. Bing-Chao Huang a Michael A. Langston představili přímočarý lineární časový algoritmus praktického sloučení na místě ke sloučení seřazeného seznamu pomocí pevného množství dalšího prostoru. Oba využili práce Kronroda a dalších. Spojuje se v lineárním čase a konstantním prostoru navíc. Algoritmus trvá o něco více průměrného času než standardní algoritmy pro slučovací třídění, přičemž lze bezplatně využívat O (n) dočasných extra paměťových buněk o méně než dvakrát. Algoritmus je praktickým způsobem mnohem rychlejší, ale pro některé seznamy je nestabilní. Ale pomocí podobných konceptů dokázali tento problém vyřešit. Mezi další místní algoritmy patří SymMerge, který zabere celkem 0 (( n + m ) log ( n + m )) času a je stabilní. Zapojení takového algoritmu do slučovacího řazení zvyšuje jeho složitost na nelineární , ale stále kvazilineární , O ( n (log n ) ² ) .
• Moderní stabilní lineární a na místě slučování je třídění sloučení bloků .

Alternativou, jak omezit kopírování do více seznamů, je přiřadit každému poli nové pole informací (prvky v m se nazývají klíče). Toto pole bude použito k propojení klíčů a všech souvisejících informací dohromady v seřazeném seznamu (klíč a související informace se nazývají záznamy). Poté sloučení seřazených seznamů pokračuje změnou hodnot propojení; vůbec není třeba přesouvat žádné záznamy. Pole, které obsahuje pouze odkaz, bude obecně menší než celý záznam, takže bude také použito méně místa. Jedná se o standardní třídící techniku, která není omezena na sloučení řazení.

Použití s ​​páskovými jednotkami

Sloučení algoritmů typu řazení umožnilo řadit velké soubory dat na raných počítačích, které měly podle moderních standardů malé paměti s náhodným přístupem. Záznamy byly ukládány na magnetickou pásku a zpracovávány na bankách magnetických páskových jednotek, jako jsou tyto IBM 729s .

Externí merge sort je praktické provozovat pomocí diskové nebo páskové jednotky, kdy se tříděné dat je příliš velký, aby se vešly do paměti . Externí třídění vysvětluje, jak je sloučení třídě implementováno s diskovými jednotkami. Typické řazení páskových jednotek používá čtyři páskové jednotky. Všechny I/O jsou sekvenční (kromě převíjení na konci každého průchodu). Minimální implementace se obejde pouze se dvěma vyrovnávací pamětí záznamů a několika programovými proměnnými.

Pojmenováním čtyř páskových jednotek jako A, B, C, D s původními daty na A a použitím pouze dvou vyrovnávacích pamětí záznamů je algoritmus podobný implementaci zdola nahoru , přičemž místo polí v paměti se používají páry páskových jednotek. Základní algoritmus lze popsat následovně:

1. Sloučit dvojice záznamů z A; psaní střídavě do dvou záznamů do C a D.
2. Sloučit dvouzáznamové dílčí seznamy z C a D do čtyřzáznamových podseznamů; psaní těchto střídavě do A a B.
3. Sloučit čtyřzáznamové dílčí seznamy z A a B do osmi záznamových podseznamů; psaní těchto střídavě do C a D
4. Opakujte, dokud nebudete mít jeden seznam obsahující všechna data, seřazená - v log ₂ ( n ) projde.

Místo toho, abychom začínali s velmi krátkými běhy, obvykle se používá hybridní algoritmus , kde počáteční průchod přečte mnoho záznamů do paměti, provede interní řazení pro vytvoření dlouhého běhu a poté tyto dlouhé běhy distribuuje do výstupní sady. Krok se vyhne mnoha časným průchodům. Například interní druh 1024 záznamů ušetří devět průchodů. Interní řazení je často velké, protože má takovou výhodu. Ve skutečnosti existují techniky, které mohou počáteční spuštění prodloužit než dostupná interní paměť. Jeden z nich, Knuthův „sněhový pluh“ (založený na binární minhaldě ), generuje běhy dvakrát delší (v průměru) než velikost použité paměti.

S určitou režií lze výše uvedený algoritmus upravit tak, aby používal tři pásky. Doby běhu O ( n log n ) lze také dosáhnout pomocí dvou front nebo zásobníku a fronty nebo tří zásobníků. V opačném směru můžeme pomocí k > dvou pásek (a položek O ( k ) v paměti) snížit počet páskových operací v O (log k ) časech pomocí k/2cestného sloučení .

Sofistikovanější sloučení, které optimalizuje využití páskové (a diskové) jednotky, je třífázové sloučení .

Optimalizace sloučení

Dlaždicové sloučení se použilo na řadu náhodných celých čísel. Vodorovná osa je index pole a svislá osa je celé číslo.

Na moderních počítačích může mít při optimalizaci softwaru prvořadý význam referenční lokalita , protože se používají víceúrovňové hierarchie paměti . Byly navrženy verze vyrovnávací paměti -algoritmy sloučení třídicího algoritmu, jejichž operace byly speciálně vybrány tak, aby minimalizovaly pohyb stránek do a z mezipaměti počítače. Například algoritmus řazení dlaždic sloučení zastaví dělení dílčích polí, když jsou dosaženy dílčí pole velikosti S, kde S je počet datových položek, které se vejdou do mezipaměti CPU. Každá z těchto podoblastí je řazena pomocí místního třídicího algoritmu, jako je napříkladvkládání, aby se zamezilo odkládání paměti, a normální sloučení je pak dokončeno standardním rekurzivním způsobem. Tento algoritmus prokázal lepší výkon na počítačích, které těží z optimalizace mezipaměti. (LaMarca & Ladner 1997)

Kronrod (1969) navrhl alternativní verzi sloučení, která využívá konstantní další prostor. Tento algoritmus byl později upřesněn. ( Katajainen, Pasanen a Teuhola 1996 )

Mnoho aplikací externího třídění také používá formu slučovacího třídění, kde se vstup rozdělí na vyšší počet podseznamů, ideálně na číslo, pro které jejich sloučení stále způsobí, že se aktuálně zpracovaná sada stránek vejde do hlavní paměti.

Paralelní sloučení

Sloučení řazení paralelizuje dobře díky použití metody rozděl a panuj . V průběhu let bylo vyvinuto několik různých paralelních variant algoritmu. Některé algoritmy řazení paralelního sloučení silně souvisí s algoritmem sekvenčního sloučení shora dolů, zatímco jiné mají jinou obecnou strukturu a používají metodu sloučení K-way .

Sloučit řazení s paralelní rekurzí

Postup sekvenčního sloučení lze popsat ve dvou fázích, dělící a spojovací. První se skládá z mnoha rekurzivních volání, která opakovaně provádějí stejný proces dělení, dokud nejsou podsekce triviálně tříděny (obsahující jeden nebo žádný prvek). Intuitivní přístup je paralelizací těchto rekurzivních hovorů. Následující pseudokód popisuje sloučení řazení s paralelní rekurzí pomocí klíčových slov fork a join :

// Sort elements lo through hi (exclusive) of array A.
algorithm mergesort(A, lo, hi) is
    if lo+1 < hi then  // Two or more elements.
        mid := ⌊(lo + hi) / 2⌋
        fork mergesort(A, lo, mid)
        mergesort(A, mid, hi)
        join
        merge(A, lo, mid, hi)

Tento algoritmus je triviální modifikací sekvenční verze a není dobře paralelizován. Jeho zrychlení proto není příliš působivé. To má rozpětí z , což je jen zlepšení ve srovnání s postupným verzi (viz Úvod do algoritmů ). To je dáno hlavně metodou sekvenčního sloučení, protože je úzkým hrdlem paralelních spouštění. ${\ displaystyle \ Theta (n)}$${\ displaystyle \ Theta (\ log n)}$

Sloučit řazení s paralelním slučováním

Lepšího paralelismu lze dosáhnout použitím algoritmu paralelního sloučení . Cormen a kol. prezentovat binární variantu, která sloučí dvě seřazené dílčí sekvence do jedné seřazené výstupní sekvence.

V jedné ze sekvencí (delší v případě nestejné délky) je vybrán prvek středního indexu. Jeho poloha v druhé sekvenci je určena takovým způsobem, že by tato sekvence zůstala setříděna, pokud by byl tento prvek vložen v této poloze. Jeden tedy ví, kolik dalších prvků z obou sekvencí je menších a lze vypočítat polohu vybraného prvku ve výstupní sekvenci. U takto vytvořených dílčích sekvencí menších a větších prvků je algoritmus sloučení opět prováděn paralelně, dokud není dosaženo základního případu rekurze.

Následující pseudokód ukazuje upravenou metodu řazení paralelního sloučení pomocí algoritmu paralelního sloučení (převzato z Cormen et al.).

/**
 * A: Input array
 * B: Output array
 * lo: lower bound
 * hi: upper bound
 * off: offset
 */
algorithm parallelMergesort(A, lo, hi, B, off) is
    len := hi - lo + 1
    if len == 1 then
        B[off] := A[lo]
    else let T[1..len] be a new array
        mid := ⌊(lo + hi) / 2⌋ 
        mid' := mid - lo + 1
        fork parallelMergesort(A, lo, mid, T, 1)
        parallelMergesort(A, mid + 1, hi, T, mid' + 1) 
        join 
        parallelMerge(T, 1, mid', mid' + 1, len, B, off)

Aby bylo možné analyzovat relaci opakování pro rozpětí nejhorších případů, rekurzivní volání parallelMergesort musí být začleněna pouze jednou kvůli jejich paralelnímu provedení, získání

$${\ Displaystyle T _ {\ infty}^{\ text {sort}} (n) = T _ {\ infty}^{\ text {sort}} \ left ({\ frac {n} {2}} \ right)+ T _ {\ infty}^{\ text {merge}} (n) = T _ {\ infty}^{\ text {sort}} \ left ({\ frac {n} {2}} \ right)+\ Theta \ vlevo (\ log (n)^{2} \ vpravo).}$$

Podrobné informace o složitosti postupu paralelního sloučení najdete v tématu Sloučení algoritmu .

Řešení této recidivy je dáno pomocí

$${\ Displaystyle T _ {\ infty}^{\ text {sort}} = \ Theta \ left (\ log (n)^{3} \ right).}$$

Tento algoritmus paralelního sloučení dosahuje paralelismu , který je mnohem vyšší než rovnoběžnost předchozího algoritmu. Takové řazení může v praxi dobře fungovat, když je kombinováno s rychlým stabilním sekvenčním tříděním, jako je například vkládání a rychlé sekvenční sloučení jako základní případ pro slučování malých polí. ${\ textstyle \ Theta \ left ({\ frac {n} {(\ log n)^{2}}} \ right)}$

Paralelní vícecestné sloučení

Zdá se svévolné omezit algoritmy řazení sloučením na metodu binárního sloučení, protože obvykle jsou k dispozici procesory p> 2. Lepším přístupem může být použití metody sloučení K-way , zobecnění binárního sloučení, ve které jsou tříděny seřazené sekvence. Tato varianta sloučení je vhodná k popisu algoritmu řazení na PRAM . ${\ displaystyle k}$

Základní myšlenka

Paralelní Vícecestný mergesort proces na čtyřech procesorech až .${\ displaystyle t_ {0}}$${\ displaystyle t_ {3}}$

Vzhledem k netříděné sekvenci prvků je cílem seřadit sekvenci s dostupnými procesory . Tyto prvky jsou rovnoměrně rozděleny mezi všechny procesory a tříděny lokálně pomocí sekvenčního algoritmu řazení . Sekvence se tedy skládá z tříděných sekvencí délky . Pro zjednodušení budiž násobek , takže pro . ${\ displaystyle n}$${\ displaystyle p}$${\ displaystyle S_ {1}, ..., S_ {p}}$${\ textstyle \ lceil {\ frac {n} {p}} \ rceil}$${\ displaystyle n}$${\ displaystyle p}$${\ textstyle \ left \ vert S_ {i} \ right \ vert = {\ frac {n} {p}}}$${\ Displaystyle i = 1, ..., p}$

Tyto sekvence budou použity k provedení vícesekvenčního výběru/výběru rozdělovače. Pro algoritmus určuje dělicí prvky s globální pozici . Poté se pomocí binárního vyhledávání určí odpovídající pozice v každé sekvenci, a tak se dále rozdělí na podsekvence s . ${\ Displaystyle j = 1, ..., p}$${\ displaystyle v_ {j}}$${\ textstyle k = j {\ frac {n} {p}}}$${\ displaystyle v_ {1}, ..., v_ {p}}$${\ displaystyle S_ {i}}$${\ displaystyle S_ {i}}$${\ displaystyle p}$${\ displaystyle S_ {i, 1}, ..., S_ {i, p}}$${\ textstyle S_ {i, j}: = \ {x \ in S_ {i} | rank (v_ {j-1}) <rank (x) \ leq rank (v_ {j}) \}}$

Kromě toho jsou prvky procesoru přiřazeny , tj. Všechny prvky mezi hodnostmi a hodnostmi , které jsou rozděleny mezi všechny . Každý procesor tedy obdrží sekvenci seřazených sekvencí. Skutečnost, že hodnost rozdělovacích prvků byla zvolena globálně, poskytuje dvě důležité vlastnosti: Na jedné straně byla zvolena tak, aby každý procesor mohl po přiřazení stále pracovat s prvky. Algoritmus je dokonale vyvážený zátěží . Na druhou stranu jsou všechny prvky na procesoru menší nebo rovny všem prvkům na procesoru . Každý procesor tedy provádí p -way sloučení lokálně a získává tak seřazenou sekvenci ze svých dílčích sekvencí. Kvůli druhé vlastnosti není nutné provádět žádné další p -way -merge, výsledky je nutné sestavit pouze v pořadí podle čísla procesoru. ${\ displaystyle S_ {1, i}, ..., S_ {p, i}}$${\ displaystyle i}$${\ textstyle (i-1) {\ frac {n} {p}}}$${\ textstyle i {\ frac {n} {p}}}$${\ displaystyle S_ {i}}$${\ displaystyle k}$${\ displaystyle v_ {i}}$${\ displaystyle k}$${\ textstyle n/p}$${\ displaystyle i}$${\ displaystyle i+1}$

Výběr více sekvencí

Ve své nejjednodušší podobě, vzhledem k seřazeným sekvencím rovnoměrně rozloženým na procesorech a pořadí , je úkolem najít prvek s globálním hodnocením ve spojení sekvencí. Lze to tedy použít k rozdělení každé na dvě části pomocí dělicího indexu , kde spodní část obsahuje pouze prvky, které jsou menší než , zatímco prvky větší než jsou umístěny v horní části. ${\ displaystyle p}$${\ displaystyle S_ {1}, ..., S_ {p}}$${\ displaystyle p}$${\ displaystyle k}$${\ displaystyle x}$${\ displaystyle k}$${\ displaystyle S_ {i}}$${\ displaystyle l_ {i}}$${\ displaystyle x}$${\ displaystyle x}$

Předložený sekvenční algoritmus vrací indexy rozdělení v každé sekvenci, např. Indexy v sekvencích , jejichž globální pozice je menší než a . ${\ displaystyle l_ {i}}$${\ displaystyle S_ {i}}$${\ displaystyle S_ {i} [l_ {i}]}$${\ displaystyle k}$${\ Displaystyle \ mathrm {rank} \ left (S_ {i} [l_ {i} +1] \ right) \ geq k}$

algorithm msSelect(S : Array of sorted Sequences [S_1,..,S_p], k : int) is
    for i = 1 to p do 
	(l_i, r_i) = (0, |S_i|-1)
	
    while there exists i: l_i < r_i do
	// pick Pivot Element in S_j[l_j], .., S_j[r_j], chose random j uniformly
	v := pickPivot(S, l, r)
	for i = 1 to p do 
	    m_i = binarySearch(v, S_i[l_i, r_i]) // sequentially
	if m_1 + ... + m_p >= k then // m_1+ ... + m_p is the global rank of v
	    r := m  // vector assignment
	else
	    l := m 
	
    return l

Pro analýzu složitosti je zvolen model PRAM . Pokud jsou data rovnoměrně rozdělena mezi všechny , má provedení p-fold metody binarySearch dobu běhu . Očekávaná hloubka rekurze je stejná jako v běžném Quickselectu . Celková předpokládaná doba běhu je tedy . ${\ displaystyle p}$${\ Displaystyle {\ mathcal {O}} \ left (p \ log \ left (n/p \ right) \ right)}$${\ Displaystyle {\ mathcal {O}} \ left (\ log \ left (\ textstyle \ sum _ {i} | S_ {i} | \ right) \ right) = {\ mathcal {O}} (\ log ( n))}$${\ Displaystyle {\ mathcal {O}} \ left (p \ log (n/p) \ log (n) \ right)}$

Aplikuje na souběžně multiway merge sort, tento algoritmus musí být vyvolán paralelně tak, že všechny splitter prvky hodnosti pro nacházejí současně. Tyto rozdělovací prvky pak lze použít k rozdělení každé sekvence na části se stejnou celkovou dobou běhu . ${\ textstyle i {\ frac {n} {p}}}$${\ Displaystyle i = 1, .., p}$${\ displaystyle p}$${\ Displaystyle {\ mathcal {O}} \ left (p \, \ log (n/p) \ log (n) \ right)}$

Pseudo kód

Níže je uveden úplný pseudokód algoritmu paralelního vícecestného sloučení. Předpokládáme, že před a po vícesekvenčním výběru existuje synchronizace bariér, takže každý procesor může správně určit rozdělovací prvky a sekvenční oddíl.

/**
 * d: Unsorted Array of Elements
 * n: Number of Elements
 * p: Number of Processors
 * return Sorted Array
 */
algorithm parallelMultiwayMergesort(d : Array, n : int, p : int) is
    o := new Array[0, n]                         // the output array
    for i = 1 to p do in parallel                // each processor in parallel
        S_i := d[(i-1) * n/p, i * n/p] 	         // Sequence of length n/p
	sort(S_i)                                // sort locally
        synch
	v_i := msSelect([S_1,...,S_p], i * n/p)          // element with global rank i * n/p
        synch
	(S_i,1, ..., S_i,p) := sequence_partitioning(si, v_1, ..., v_p) // split s_i into subsequences
	    
	o[(i-1) * n/p, i * n/p] := kWayMerge(s_1,i, ..., s_p,i)  // merge and assign to output array
	
    return o

Analýza

Za prvé, každý procesor třídí přiřazené prvky lokálně pomocí složitého algoritmu řazení . Poté je nutné rozdělovací prvky vypočítat včas . Nakonec musí být každá skupina rozdělení rozdělena paralelně každým procesorem s dobou běhu pomocí sekvenčního algoritmu slučování p-way . Celková doba běhu je tedy dána vztahem ${\ displaystyle n/p}$${\ Displaystyle {\ mathcal {O}} \ left (n/p \; \ log (n/p) \ right)}$${\ Displaystyle {\ mathcal {O}} \ left (p \, \ log (n/p) \ log (n) \ right)}$${\ displaystyle p}$${\ displaystyle {\ mathcal {O}} (\ log (p) \; n/p)}$

${\ Displaystyle {\ mathcal {O}} \ left ({\ frac {n} {p}} \ log \ left ({\ frac {n} {p}} \ right)+p \ log \ left ({\ frac {n} {p}} \ right) \ log (n)+{\ frac {n} {p}} \ log (p) \ right)}$.

Praktické přizpůsobení a aplikace

Algoritmus vícecestného slučovacího třídění je velmi škálovatelný díky vysoké schopnosti paralelizace, která umožňuje použití mnoha procesorů. Díky tomu je algoritmus životaschopným kandidátem pro třídění velkého množství dat, například zpracovaných v počítačových klastrech . Protože paměť v takových systémech obvykle není omezujícím zdrojem, je nevýhoda prostorové složitosti typu sloučení zanedbatelná. V takových systémech se však stávají důležitými další faktory, které nejsou při modelování na PRAM brány v úvahu . Zde je třeba zvážit následující aspekty: Hierarchie paměti , když se data nevejdou do mezipaměti procesorů, nebo režie komunikace při výměně dat mezi procesory, což by se mohlo stát překážkou, když k datům již nelze přistupovat prostřednictvím sdíleného Paměť.

Sanders a kol. ve svém příspěvku představili hromadný synchronní paralelní algoritmus pro víceúrovňové vícecestné mergesort, který rozděluje procesory do skupin velikosti . Všechny procesory se nejprve seřadí lokálně. Na rozdíl od jednoúrovňového vícecestného mergesortu jsou tyto sekvence rozděleny na části a přiřazeny příslušným skupinám procesorů. Tyto kroky se v těchto skupinách rekurzivně opakují. To snižuje komunikaci a zejména se vyhýbá problémům s mnoha malými zprávami. K definování skupin procesorů (např. Racků , klastrů , ...) lze použít hierarchickou strukturu podkladové reálné sítě . ${\ displaystyle p}$${\ displaystyle r}$${\ displaystyle p '}$${\ displaystyle r}$

Další varianty

Sloučení řazení bylo jedním z prvních třídicích algoritmů, kde bylo dosaženo optimálního zrychlení, přičemž Richard Cole používal chytrý algoritmus podvzorkování k zajištění sloučení O (1). Jiné sofistikované algoritmy paralelního třídění mohou dosáhnout stejné nebo lepší časové hranice s nižší konstantou. Například v roce 1991 David Powers popsal paralelizovaný quicksort (a související třídění radixů ), který může pracovat v čase O (log n ) na CRCW paralelním stroji s náhodným přístupem (PRAM) s n procesory provedením implicitního dělení. Powers dále ukazuje, že pipelined verze dávkovač je Bitonic mergesort v O ((log n ) ² ) Čas na motýla třídícím sítě je v praxi vlastně rychlejší než jeho O (log n ) druhy na PRAM a on poskytuje podrobnou diskusi o skryté režie ve srovnání, radix a paralelní třídění.

Porovnání s jinými algoritmy řazení

Přestože má heapsort stejné časové limity jako sloučení, vyžaduje místo mer ( n ) sloučení řazení pouze pomocný prostor Θ (1 ). Na typických moderních architekturách efektivní implementace rychlého řazení obecně překonávají slučovací třídění pro třídění polí založených na RAM. Na druhé straně je sloučení řazení stabilním tříděním a je efektivnější při zpracování sekvenčních médií s pomalým přístupem. Sloučení řazení je často nejlepší volbou pro třídění propojeného seznamu : v této situaci je relativně snadné implementovat třídění sloučení takovým způsobem, že vyžaduje pouze Θ (1) místa navíc a pomalý výkon náhodného přístupu propojeného list dělá některé další algoritmy (například quicksort) špatně fungující a jiné (jako například heapsort) zcela nemožné.

Od verze Perl 5.8 je slučovací řazení výchozím algoritmem řazení (v předchozích verzích Perlu to bylo quicksort). V Javě , se Arrays.sort () metody používají korespondenci třídit nebo laděným quicksort v závislosti na datové typy a pro spínač účinnost realizace na vložení třídění , když jsou méně než sedm prvků pole roztříděním. Jádro Linuxu používá pro své propojené seznamy sloučení. Python používá Timsort , další vyladěný hybrid sloučení a vkládání, který se stal standardním algoritmem řazení v Java SE 7 (pro pole neprimitivních typů), na platformě Android a v GNU Octave .

Poznámky

Reference

• Cormen, Thomas H .; Leiserson, Charles E .; Rivest, Ronald L .; Stein, Clifford (2009) [1990]. Úvod do algoritmů (3. vydání). MIT Press a McGraw-Hill. ISBN 0-262-03384-4.
• Katajainen, Jyrki; Pasanen, Tomi; Teuhola, Jukka (1996). „Praktický kombinovaný třídič na místě“ . Severský žurnál výpočetní techniky . 3 (1): 27–40. CiteSeerX  10.1.1.22.8523 . ISSN  1236-6064 . Archivováno od originálu dne 2011-08-07 . Citováno 2009-04-04 .. Také praktický Mergesort na místě . Také [3]
• Knuth, Donald (1998). „Oddíl 5.2.4: Řazení podle sloučení“. Třídění a vyhledávání . Umění počítačového programování . 3 (2. vyd.). Addison-Wesley. s. 158–168. ISBN 0-201-89685-0.
• Kronrod, MA (1969). „Optimální algoritmus řazení bez operačního pole“. Sovětská matematika - Doklady . 10 : 744.
• LaMarca, A .; Ladner, RE (1997). „Vliv cache na výkon třídění“. Proč. 8. Ann. Symp. ACM-SIAM O diskrétních algoritmech (SODA97) : 370–379. CiteSeerX  10.1.1.31.1153 .
• Skiena, Steven S. (2008). „4.5: Mergesort: Třídění podle Divide-and-Conquer“. The Algorithm Design Manual (2nd ed.). Springer. s. 120–125. ISBN 978-1-84800-069-8.
• Sun Microsystems. „Arrays API (Java SE 6)“ . Citováno 2007-11-19 .
• Oracle Corp. „Pole (Java SE 10 a JDK 10)“ . Citováno 2018-07-23 .

externí odkazy

• Algoritmy animovaného třídění: Sloučit řazení na stroji Wayback (archivováno 6. března 2015) - grafická ukázka
• Otevřené datové struktury - Oddíl 11.1.1 - Sloučit třídění , Pat Morin