Ich habe eine 500-GB-Textdatei mit etwa 10 Milliarden Zeilen, die in alphabetischer Reihenfolge sortiert werden muss. Was ist der beste Algorithmus? Kann meine Implementierung und Einrichtung verbessert werden?
Im Moment verwende ich den Befehl coreutils sort:
LANG=C
sort -k2,2 --field-separator=',' --buffer-size=(80% RAM) --temporary-directory=/volatile BigFile
Ich führe dies in AWS EC2 auf einer virtuellen Maschine mit 120 GB RAM und 16 Kernen aus. Es dauert den größten Teil des Tages.
/ volatile ist ein 10 TB RAID0-Array.
Der Trick 'LANG = C' liefert einen x2-Geschwindigkeitsgewinn (dank 1 )
Standardmäßig verwendet 'sort' 50% des verfügbaren RAM. Ein Anstieg auf 80-90% führt zu einer gewissen Verbesserung.
Mein Verständnis ist, dass gnu 'sort' eine Variante des Merge-Sort-Algorithmus mit O (n log n) ist, der am schnellsten ist: siehe 2 & 3 . Würde ein Wechsel zu QuickSort helfen (ich bin mit einer instabilen Sorte zufrieden)?
Eine Sache, die mir aufgefallen ist, ist, dass nur 8 Kerne verwendet werden. Dies hängt mit default_max_threads zusammen, die in linux coreutils sort.c auf 8 gesetzt sind (siehe 4 ). Würde es helfen, sort.c mit 16 neu zu kompilieren?
Vielen Dank!
NACHVERFOLGEN :
@dariusz
Ich habe Chris und Ihre Vorschläge unten verwendet.
Da die Daten bereits stapelweise generiert wurden: Ich habe jeden Bucket separat sortiert (auf mehreren separaten Maschinen) und dann die Funktion 'sort --merge' verwendet. Funktioniert wie ein Zauber und ist viel schneller: O (log N / K) gegen O (log N).
Ich habe das Projekt auch von Grund auf neu überdacht: Einige Daten werden jetzt nachbearbeitet, während die Daten generiert werden, sodass einige nicht benötigte Daten (Rauschen) vor dem Sortieren verworfen werden können.
Insgesamt führte die Reduzierung der Datengröße und das Sortieren / Zusammenführen zu einer massiven Reduzierung der Rechenressourcen, die zur Erreichung meines Ziels erforderlich sind.
Vielen Dank für all Ihre hilfreichen Kommentare.
Der Vorteil von Quicksort gegenüber Mergesort ist kein zusätzlicher Speicheraufwand. Der Vorteil von Mergesort ist die garantierte O (n log n) -Laufzeit, bei der Quicksort bei schlechter Drehpunktabtastung viel schlechter sein kann. Wenn Sie keinen Grund zur Besorgnis über die Speichernutzung haben, ändern Sie diese nicht. Wenn Sie dies tun, stellen Sie einfach sicher, dass Sie eine Quicksort-Implementierung auswählen, die eine solide Pivot-Abtastung durchführt.
Ich denke nicht, dass es spektakulär helfen würde, sort.c neu zu kompilieren. Es könnte sich um eine Mikrooptimierungsskala handeln. Ihr Engpass hier ist jedoch die Speicher- / Festplattengeschwindigkeit, nicht die verfügbare Prozessormenge. Meine Intuition wäre, dass 8 Threads Ihren E / A-Durchsatz bereits maximieren und Sie keine Leistungsverbesserung sehen würden, aber dies würde sicherlich von Ihrem spezifischen Setup abhängen.
Sie können auch erhebliche Leistungssteigerungen erzielen, indem Sie die Verteilung Ihrer Daten nutzen. Beispielsweise können gleichmäßig verteilte Daten sehr schnell durch einen einzelnen Bucket-Sortierdurchlauf sortiert werden und anschließend mithilfe von Mergesort die Buckets sortiert werden. Dies hat auch den zusätzlichen Vorteil, dass der gesamte Speicheraufwand für Mergesort verringert wird. Wenn die Speicherkomplexität von Mergesort O (N) beträgt und Sie Ihre Daten in K Buckets aufteilen können, beträgt Ihr neuer Speicheraufwand O (N / K).
Dieser Artikel stammt aus dem Internet. Bitte geben Sie beim Nachdruck die Quelle an.
Bei Verstößen wenden Sie sich bitte [email protected] Löschen.
Lass mich ein paar Worte sagen