[{"@context":"http:\/\/schema.org\/","@type":"BlogPosting","@id":"https:\/\/wiki.edu.vn\/wiki48\/2021\/12\/27\/externes-sortieren-wikipedia\/#BlogPosting","mainEntityOfPage":"https:\/\/wiki.edu.vn\/wiki48\/2021\/12\/27\/externes-sortieren-wikipedia\/","headline":"Externes Sortieren \u2013 Wikipedia","name":"Externes Sortieren \u2013 Wikipedia","description":"Externes Sortieren beschreibt Sortieralgorithmen, welche auf sehr gro\u00dfe Datenmengen ausgelegt sind. Algorithmen, die auf gro\u00dfen Datenmengen arbeiten, die nicht in","datePublished":"2021-12-27","dateModified":"2021-12-27","author":{"@type":"Person","@id":"https:\/\/wiki.edu.vn\/wiki48\/author\/lordneo\/#Person","name":"lordneo","url":"https:\/\/wiki.edu.vn\/wiki48\/author\/lordneo\/","image":{"@type":"ImageObject","@id":"https:\/\/secure.gravatar.com\/avatar\/44a4cee54c4c053e967fe3e7d054edd4?s=96&d=mm&r=g","url":"https:\/\/secure.gravatar.com\/avatar\/44a4cee54c4c053e967fe3e7d054edd4?s=96&d=mm&r=g","height":96,"width":96}},"publisher":{"@type":"Organization","name":"Enzyklop\u00e4die","logo":{"@type":"ImageObject","@id":"https:\/\/wiki.edu.vn\/wiki4\/wp-content\/uploads\/2023\/08\/download.jpg","url":"https:\/\/wiki.edu.vn\/wiki4\/wp-content\/uploads\/2023\/08\/download.jpg","width":600,"height":60}},"image":{"@type":"ImageObject","@id":"https:\/\/wikimedia.org\/api\/rest_v1\/media\/math\/render\/svg\/f82cade9898ced02fdd08712e5f0c0151758a0dd","url":"https:\/\/wikimedia.org\/api\/rest_v1\/media\/math\/render\/svg\/f82cade9898ced02fdd08712e5f0c0151758a0dd","height":"","width":""},"url":"https:\/\/wiki.edu.vn\/wiki48\/2021\/12\/27\/externes-sortieren-wikipedia\/","wordCount":4486,"articleBody":"Externes Sortieren beschreibt Sortieralgorithmen, welche auf sehr gro\u00dfe Datenmengen ausgelegt sind. Algorithmen, die auf gro\u00dfen Datenmengen arbeiten, die nicht in den Hauptspeicher passen, werden allgemein als External-Memory-Algorithmen bezeichnet.In der Analyse klassischer Sortieralgorithmen (z.\u00a0B. Quicksort) wird meist keine Speicherhierarchie bzw. der Zugriff auf Daten auf unterschiedlich schnellen Datentr\u00e4gern ber\u00fccksichtigt.Allerdings ist der Aufbau und die Hierarchie des Speichers sowie der Umgang der Algorithmen mit diesem f\u00fcr die Performance beim Sortieren von gro\u00dfen Datenmengen entscheidend.Ein gebr\u00e4uchliches Modell zur Betrachtung von External Memory Algorithmen ist das Parallel Disk Model (PDM).[1] Dieses verf\u00fcgt \u00fcber einen Hauptspeicher der Gr\u00f6\u00dfe M{displaystyle M} und einen oder mehreren externen Speicher unbegrenzter Gr\u00f6\u00dfe, die sogenannten Disks. Auf diesen finden die zu sortierenden Daten der Gr\u00f6\u00dfe N{displaystyle N} Platz. Oftmals wird zur Vereinfachung die Anzahl der Disks D=1{displaystyle D=1} angenommen und das vereinfachte Modell als External Memory Model (EMM) bezeichnet. Auch Aggarwal und Vitter stellten das Modell urspr\u00fcnglich mit einer einzelnen Disk, aber mehreren parallelen Schreib-Lese-K\u00f6pfen vor.[2] Der Hauptspeicher wie auch der externen Speicher verf\u00fcgen \u00fcber eine Blockgr\u00f6\u00dfe B{displaystyle B}. Mit einer IO-Operation, kannein Block pro Disk in den Hauptspeicher geladen oder in den externen Speicher zur\u00fcckgeschrieben werden. Zur besseren \u00dcbersicht werden au\u00dferdem die Eingabegr\u00f6\u00dfe n=N\/B{displaystyle n=N\/B} sowie die Gr\u00f6\u00dfe des Hauptspeichers m=M\/B{displaystyle m=M\/B} in Bl\u00f6cken angegeben. Im Gegensatz zur Analyse klassischer Sortieralgorithmen wird die Performance eines Algorithmus nicht an der Anzahl aller Operationen gemessen, sondern nur durch die Anzahl der IO-Operationen angegeben.F\u00fcr das Sortieren im PDM kann eine allgemeing\u00fcltige Schranke f\u00fcr die Anzahl der IO-Operationen angegeben werden.[1] Diese ist im Fall einer einzelnen oder mehrerer Disks (D\u22651{displaystyle Dgeq 1}) gegeben durch:\u0398(NDBlogM\/B\u2061NB)=\u0398(nDlogm\u2061n){displaystyle Theta left({frac {N}{DB}}log _{M\/B}{frac {N}{B}}right)=Theta left({frac {n}{D}}log _{m}nright)}In der Praxis ist logm\u2061n{displaystyle log _{m}n} eine kleine Konstante. F\u00fcr den untypischen Fall Blog\u2061m=o(log\u2061n){displaystyle Blog m=o(log n)} gilt diese Schranke lediglich f\u00fcr vergleichsbasierte Verfahren.Merge Sort[Bearbeiten | Quelltext bearbeiten]An den klassischen Merge Sort angelehnt ist der External Memory Merge Sort.[1][3] Zun\u00e4chst soll der Algorithmus f\u00fcr D=1{displaystyle D=1} betrachtet werden. Es werden nacheinander Datensegmente bestehend aus m{displaystyle m} Bl\u00f6cken in den Hauptspeicher geladen, dort sortiert und als sogenannter Run zur\u00fcck in den externen Speicher geschrieben werden.Die N\/M{displaystyle N\/M} Runs im externen Speicher werden anschlie\u00dfend mittels eines K-Way-Merges auf logm\u2061n{displaystyle log _{m}n} Rekursionsebenen zusammengefasst.  Vereinfachte Darstellung des Merge Sorts. Zuerst werden die einzelnen Runs im Hauptspeicher sortiert, anschlie\u00dfend werden die Runs gemerged. for j=1 to n\/M     Lade n\u00e4chstes Datensegment der Gr\u00f6\u00dfe M{displaystyle M} in Hauptspeicher     Sortiere Daten im Hauptspeicher     Schreibe sortierte Daten als run r1,j{displaystyle r_{1,j}} auf externen Speicher end for i=1 to \u2308logm\u2061n\u2309{displaystyle lceil log _{m}nrceil }     for j=1 to \u2308|ri|\/(m)\u2309{displaystyle lceil |r_{i}|\/(m)rceil }         Lade die jeweils ersten Bl\u00f6cke der runs ri,(j\u22121)(m)+1...ri,j(m){displaystyle r_{i,(j-1)(m)+1}...r_{i,j(m)}} in Merge-Buffer         while Merge-Buffer nicht leer             Merge runs ri,(j\u22121)(m)+1...ri,j(m){displaystyle r_{i,(j-1)(m)+1}...r_{i,j(m)}}             Schreibe Output-Buffer in externen Speicher falls voll             Lade n\u00e4chsten Block in Hauptspeicher falls ein Merge-Buffer bereits komplett gemerged         end     end endUm mehrere parallele Disks m\u00f6glichst effizient zu nutzen und die oben beschriebene Schranke einzuhalten, m\u00fcssen in jedem IO-Schritt m\u00f6glichst D{displaystyle D} Bl\u00f6cke bewegt werden.Zum effizienten Schreiben der Bl\u00f6cke zur\u00fcck auf die Disks wird daher die Gr\u00f6\u00dfe des internen Buffers im Hauptspeicher, der die gemergten Elemente enth\u00e4lt, auf D{displaystyle D} Bl\u00f6cke erweitert. Um auch beim Lesen einen h\u00f6heren Durchsatz zu gew\u00e4hrleisten wird au\u00dferdem ein Prefetching-Buffer hinzugef\u00fcgt.Wurden die Elemente in den vorherigen Schritten geschickt auf den einzelnen Disks verteilt und eine geeignete Prefetching-Strategie gew\u00e4hlt, gen\u00fcgt eine Buffergr\u00f6\u00dfe von \u0398(D){displaystyle Theta (D)} Bl\u00f6cken.Distribution Sort[Bearbeiten | Quelltext bearbeiten]Analog zum Merge Sort ist auch der Distribution Sort ein rekursiver Algorithmus.[1][3] Die Daten sollen nach S\u22121{displaystyle S-1} Partitionierungs\u00adelementen in S{displaystyle S} Buckets eingeteilt werden. Dabei gilt, dass alle Elemente innerhalb eines Buckets kleiner sind als jedes Element im darauf Folgenden.Diese Partitionierung wird dann rekursiv f\u00fcr die einzelnen Buckets wiederholt. Sind die Buckets klein genug um jeweils komplett in den Hauptspeicher geladen werden zu k\u00f6nnen, werden sie dort sortiert. Die Konkatenation der sortierten Buckets bildet somit die sortierte Reihenfolge der gesamten Daten.Die Wahl der Partitionierungselemente ist entscheidend um m\u00f6glichst gleich gro\u00dfe Buckets zu erhalten und somit eine gute Performance zu gew\u00e4hrleisten. Dies kann beispielsweise auf probabilistische Art und Weise erfolgen.Eine kleine, zuf\u00e4llige Menge an Elementen wird sortiert und die Partitionierungs\u00adelemente aus dieser ausgew\u00e4hlt. Die Gr\u00f6\u00dfe der Menge wird so gew\u00e4hlt, dass die Sortierung dieser f\u00fcr die Anzahl an IO-Operationen vernachl\u00e4ssigbar ist und keinen Einfluss auf die Schranke hat.Bei guter Partitionierung betr\u00e4gt die Rekursionstiefe O(logS\u2061n){displaystyle O(log _{S}n)}. Da f\u00fcr jedes Bucket ein Buffer im Hauptspeicher ben\u00f6tigt wird, kann S{displaystyle S} durch \u0398(m){displaystyle Theta (m)} nach oben abgesch\u00e4tzt werden.Um die oben gegebene Schranke zu erf\u00fcllen d\u00fcrfen somit auf jeder Rekursionsebene lediglich \u0398(n\/D){displaystyle Theta (n\/D)} IO-Operationen ausgef\u00fchrt werden. Um ein Bucket effizient in den Hauptspeicher zu laden, m\u00fcssen dessen Bl\u00f6cke zuvor gleichm\u00e4\u00dfig auf die verschiedenen Disks verteilt worden sein.Die zu den verschiedenen Buckets geh\u00f6renden Bl\u00f6cke werden entweder gemeinsam als ein Stripe aus dem Output-Buffer im Hauptspeicher auf den externen Speicher geschrieben oder es wird ein Stripe pro Bucket erstellt. Im Falle eines Stripes pro Bucket kann mit Hilfe von Randomized Cycling daf\u00fcr gesorgt werden, dass die n\u00e4chsten Bl\u00f6cke der verschiedenen Buckets auf m\u00f6glichst unterschiedliche Disks geschrieben werden m\u00fcssen. Diese Variante wird auch Randomized Cycling Distribution Sort genannt.Grunds\u00e4tzlich nehmen Operationen zur Sortierung einen gro\u00dfen Teil des Rechenaufwands ein.[3] In den letzten Jahren sind die Datenmengen auf denen gerechnet wird stetig gr\u00f6\u00dfer geworden.[1] Zur Bew\u00e4ltigung dieser Datenmengen sind External-Memory-Algorithmen n\u00f6tig. Effizientes Externes Sortieren hat dabei eine besondere Bedeutung, da viele External-Memory-Algorithmen auf Sortierverfahren beruhen.\u2191 abcde Jeffrey Scott Vitter: Algorithms and data structures for external memory.  In:  Foundations and Trends in Theoretical Computer Science. 2, Nr.\u00a04,  2008, S.\u00a030\u2013474.\u2191 Alok Aggarwal, Jeffrey Scott Vitter: The input\/output complexity of sorting and related problems.  In:  Communications of the ACM. 31, Nr.\u00a09,  1988, S.\u00a01116\u20131127.\u2191 abc Donald Knuth: The Art of Programming, Vol. 3 (Sorting and Searching). Addison-Wesley,  1973."},{"@context":"http:\/\/schema.org\/","@type":"BreadcrumbList","itemListElement":[{"@type":"ListItem","position":1,"item":{"@id":"https:\/\/wiki.edu.vn\/wiki48\/#breadcrumbitem","name":"Enzyklop\u00e4die"}},{"@type":"ListItem","position":2,"item":{"@id":"https:\/\/wiki.edu.vn\/wiki48\/2021\/12\/27\/externes-sortieren-wikipedia\/#breadcrumbitem","name":"Externes Sortieren \u2013 Wikipedia"}}]}]