Sortare externă - External sorting

Sortarea externă este o clasă de algoritmi de sortare care pot gestiona cantități masive de date . Sortarea externă este necesară atunci când datele care sunt sortate nu se încadrează în memoria principală a unui dispozitiv de calcul (de obicei RAM ) și, în schimb, trebuie să se afle în memoria externă mai lentă , de obicei o unitate de hard disk . Astfel, algoritmii de sortare externă sunt algoritmi de memorie externă și astfel aplicabili în modelul de calcul al memoriei externe .

Algoritmii de sortare externă se împart în general în două tipuri, sortarea distribuției, care seamănă cu quicksort , și sortarea externă de îmbinare, care seamănă cu sortarea de îmbinare . Acesta din urmă folosește de obicei o strategie hibridă de fuzionare a sortării. În faza de sortare, bucăți de date suficient de mici pentru a se potrivi în memoria principală sunt citite, sortate și scrise într-un fișier temporar. În faza de îmbinare, subfisierele sortate sunt combinate într-un singur fișier mai mare.

Model

Algoritmii de sortare externă pot fi analizați în modelul de memorie externă . În acest model, o memorie cache sau o memorie internă de dimensiunea M și o memorie externă nelimitată sunt împărțite în blocuri de dimensiunea B , iar timpul de funcționare al unui algoritm este determinat de numărul de transferuri de memorie între memoria internă și cea externă. La fel ca omologii lor care nu ascund memoria cache , algoritmii de sortare externi optimi asimptotic ating un timp de funcționare (în notație O mare ) de . ${\ displaystyle O \ left ({\ tfrac {N} {B}} \ log _ {\ tfrac {M} {B}} {\ tfrac {N} {B}} \ right)}$

Sortare fuziune externă

Un exemplu de sortare externă este algoritmul de sortare a îmbinării externe , care este un algoritm de îmbinare K-way . Sortează bucăți care se potrivesc fiecare în RAM, apoi îmbină bucățile sortate împreună.

Algoritmul sortează mai întâi M articole odată și pune listele sortate înapoi în memoria externă. Apoi, recursiv , fuzionează pe listele sortate. Pentru a face această îmbinare, elementele B din fiecare listă sortată sunt încărcate în memoria internă, iar minimul este redat în mod repetat. ${\ displaystyle {\ tfrac {M} {B}}}$

De exemplu, pentru sortarea a 900 megaocteți de date folosind doar 100 megaocteți RAM:

1. Citiți 100 MB de date din memoria principală și sortați-le după o metodă convențională, cum ar fi quicksort .
2. Scrieți datele sortate pe disc.
3. Repetați pașii 1 și 2 până când toate datele sunt în bucăți de 100 MB sortate (există 900 MB / 100 MB = 9 bucăți), care acum trebuie să fie îmbinate într-un singur fișier de ieșire.
4. Citiți primii 10 MB (= 100 MB / (9 bucăți + 1)) din fiecare bucată sortată în buffere de intrare în memoria principală și alocați restul de 10 MB pentru un buffer de ieșire. (În practică, s-ar putea oferi performanțe mai bune pentru a face bufferul de ieșire mai mare și bufferele de intrare puțin mai mici.)
5. Efectuați o îmbinare pe 9 căi și stocați rezultatul în bufferul de ieșire. Ori de câte ori tamponul de ieșire se umple, scrieți-l în fișierul sortat final și goliți-l. Ori de câte ori oricare dintre cele 9 buffere de intrare se golește, umpleți-l cu următorii 10 MB din bucata sa asociată de 100 MB, până când nu mai sunt disponibile date din bucată. Acesta este pasul cheie care face ca sortarea îmbinării externe să funcționeze extern - deoarece algoritmul de îmbinare face doar o trecere secvențială prin fiecare bucată, fiecare bucată nu trebuie încărcată complet; mai degrabă, părți secvențiale ale bucății pot fi încărcate după cum este necesar.

Din punct de vedere istoric, în loc de un fel, uneori s-a folosit un algoritm de înlocuire-selecție pentru a efectua distribuția inițială, pentru a produce în medie jumătate din numărul de bucăți de ieșire cu dublul lungimii.

Permise suplimentare

Exemplul anterior este un sortare în două treceri: prima sortare, apoi fuzionarea. Sortarea se termină cu o singură îmbinare k -way, mai degrabă decât o serie de treceri de îmbinare bidirecționale ca într-o sortare tipică de îmbinare în memorie. Acest lucru se datorează faptului că fiecare trecere de îmbinare citește și scrie fiecare valoare de pe și pe disc, deci reducerea numărului de treceri compensează mai mult decât costul suplimentar al unei îmbinări k -way.

Limita la îmbinarea cu o singură trecere este că, pe măsură ce crește numărul de bucăți, memoria va fi împărțită în mai multe buffere, astfel încât fiecare buffer este mai mic. În cele din urmă, citirile devin atât de mici încât se cheltuie mai mult timp pe căutările de disc decât transferul de date. O unitate tipică de hard disk magnetic poate avea un timp de acces de 10 ms și o rată de transfer de date de 100 MB / s, astfel încât fiecare căutare necesită la fel de mult timp ca transferarea a 1 MB de date.

Astfel, pentru sortare, să zicem, 50 GB în 100 MB de RAM, utilizarea unei singure treceri de îmbinare pe 500 de căi nu este eficientă: putem citi doar 100 MB / 501 ± 200 KB din fiecare bucată simultan, deci 5/6 din timpul discului este petrecut în căutare. Utilizarea a două treceri de îmbinare rezolvă problema. Apoi, procesul de sortare ar putea arăta astfel:

1. Rulați pasul inițial de sortare a bucăților ca înainte pentru a crea bucăți sortate de 500 × 100 MB.
2. Rulați o primă trecere combinând 25 × 100 MB bucăți odată, rezultând 20 × 2,5 GB bucăți sortate.
3. Rulați o a doua trecere de îmbinare pentru a îmbina bucățile sortate de 20 × 2,5 GB într-un singur rezultat sortat de 50 GB

Deși acest lucru necesită o trecere suplimentară asupra datelor, fiecare citire are acum 4 MB lungime, deci doar 1/5 din timpul discului este petrecut în căutare. Îmbunătățirea eficienței transferului de date în timpul trecerilor de îmbinare (16,6% până la 80% este aproape o îmbunătățire de 5 ori) mai mult decât compensează numărul dublat de treceri de îmbinare.

La fel ca sortările în memorie, sortările externe eficiente necesită timp O ( n log n ): creșterile liniare ale dimensiunii datelor necesită creșteri logaritmice ale numărului de treceri și fiecare trecere ia un număr liniar de citiri și scrieri. Folosind dimensiunile mari de memorie furnizate de computerele moderne, factorul logaritmic crește foarte lent. În ipoteze rezonabile, cel puțin 500 GB de date pot fi sortate folosind 1 GB de memorie principală înainte ca o a treia trecere să devină avantajoasă și de multe ori mai multe date pot fi sortate înainte ca o a patra trecere să devină utilă. Mediile cu timp redus de căutare, cum ar fi unitățile SSD, cresc, de asemenea, cantitatea care poate fi sortată înainte ca transferurile suplimentare să îmbunătățească performanța.

Dimensiunea memoriei principale este importantă. Dublarea memoriei dedicate sortării înjumătățește numărul de bucăți și numărul de citiri pe bucată, reducând numărul de căutări necesare cu aproximativ trei sferturi. Raportul dintre RAM și stocarea pe disc pe servere face de cele mai multe ori convenabil să faceți tipuri uriașe pe un cluster de mașini, mai degrabă decât pe o mașină cu mai multe treceri.

Sortare distribuție externă

Sortarea distribuției externe este similară cu cea rapidă . Algoritmul găsește aproximativ pivoturi și le folosește pentru a împărți N elemente în subarrayuri de dimensiuni aproximativ egale, fiecare dintre ale cărui elemente sunt toate mai mici decât următorul, și apoi se repetă până când dimensiunile subarrayurilor sunt mai mici decât dimensiunea blocului . Când subarrayurile sunt mai mici decât dimensiunea blocului, sortarea se poate face rapid, deoarece toate citirile și scrierile se fac în cache , iar în modelul de memorie externă sunt necesare operații. ${\ displaystyle {\ tfrac {M} {B}}}$${\ displaystyle O (1)}$

Cu toate acestea, găsirea exactă a pivoturilor nu ar fi suficient de rapidă pentru a face sortarea distribuției externe asimptotică optimă . În schimb, găsim ceva mai puțini pivoti. Pentru a găsi acești pivoti, algoritmul împarte N elemente de intrare în bucăți și ia toate elementele și utilizează recursiv algoritmul median al medianelor pentru a găsi pivote. ${\ displaystyle {\ tfrac {M} {B}}}$${\ displaystyle {\ tfrac {N} {M}}}$${\ displaystyle {\ sqrt {\ tfrac {M} {16B}}}}$${\ displaystyle {\ sqrt {\ tfrac {M} {B}}}}$

Există o dualitate , sau similitudine fundamentală, între algoritmi bazati pe fuziune și distribuție.

Performanţă

Sort Benchmark , creat de om de știință de calculator Jim Gray , compară algoritmi de sortare externe implementate folosind hardware și software - ul fin reglate. Implementările câștigătoare utilizează mai multe tehnici:

• Folosind paralelismul
  • Mai multe unități de disc pot fi utilizate în paralel pentru a îmbunătăți viteza de citire și scriere secvențială. Aceasta poate fi o îmbunătățire foarte eficientă din punct de vedere al costurilor: un câștigător Sort Benchmark din categoria de sortare Penny Sort, centrat pe costuri, folosește șase unități de disc într-o mașină de altfel.
  • Software-ul de sortare poate utiliza mai multe fire , pentru a accelera procesul pe computerele multicore moderne.
  • Software-ul poate utiliza I / O asincron, astfel încât o rundă de date să poată fi sortată sau fuzionată în timp ce alte rulări sunt citite sau scrise pe disc.
  • Mai multe mașini conectate prin legături rapide de rețea pot sorta fiecare parte dintr-un imens set de date în paralel.
• Creșterea vitezei hardware
  • Folosirea mai multor RAM pentru sortare poate reduce numărul de căutări de disc și poate evita nevoia de mai multe treceri.
  • Memoria externă rapidă, precum unitățile SSD, poate accelera sortările, fie dacă datele sunt suficient de mici pentru a se potrivi în întregime pe SSD-uri sau, mai rar, pentru a accelera sortarea bucăților de dimensiuni SSD într-un sortare cu trei treceri.
  • Mulți alți factori pot afecta viteza maximă de sortare a hardware-ului: viteza procesorului și numărul de nuclee, latența accesului RAM, lățimea de bandă de intrare / ieșire, viteza de citire / scriere a discului, timpul de căutare a discului și altele. „Echilibrarea” hardware-ului pentru a minimiza blocajele este o parte importantă a proiectării unui sistem de sortare eficient.
  • Eficiența costurilor, precum și viteza absolută pot fi esențiale, în special în mediile cluster în care costurile reduse ale nodurilor permit achiziționarea mai multor noduri.
• Creșterea vitezei software-ului
  • Unii participanți la Sort Benchmark folosesc o variantă a sortării radix pentru prima fază de sortare: separă datele într-unul din numeroasele "coșuri" în funcție de începutul valorii sale. Sortarea datelor de referință este aleatorie și se potrivește mai ales acestei optimizări.
  • Compactarea intrării, a fișierelor intermediare și a ieșirii poate reduce timpul petrecut pe I / O, dar nu este permis în criteriul de referință Sortare.
  • Deoarece Sort Benchmark sortează înregistrările lungi (100 de octeți) utilizând taste scurte (10 octeți), software-ul de sortare uneori rearanjează tastele separat de valori pentru a reduce volumul I / O de memorie.

Vezi si

• Fuzionare sortare mainframe
• Algoritm de memorie externă
• Funnelsort
• Sortare de distribuție fără memorie cache

Referințe

linkuri externe

• STXXL, un set de instrumente de algoritm care include mergesort extern
• Un exemplu de fuziune externă
• O implementare K-Way Merge
• Sortarea memoriei externe în Java
• Un exemplu de implementare pennysort folosind Judy Arrays
• Sortați criteriul de referință