BEARBEITEN:
Es stellt sich heraus, dass die langsame Version tatsächlich eine Einfügesortierung O (n ^ 2) ist und nicht eine Mischsortierung O (n log n), die das Leistungsproblem erklärt. Ich dachte, ich würde zukünftigen Lesern den Schmerz ersparen, durch den Code zu waten, um diese Antwort zu finden.
ORIGINAL BEGINNT HIER -------------------------------------------
Ich habe zwei Versionen von merge sort in haskell geschrieben und ich kann nicht verstehen, warum der eine 1000 mal schneller ist als der andere. In beiden Fällen beginnen wir damit, dass ein Element in der Liste sortiert wird und eine Liste mit einer Liste erstellt wird. Dann paaren wir Listen und fügen sie zusammen, bis nur noch eine Liste übrig ist. Das Problem scheint zu sein, dass ich in der langsamen Version "doMerge (x1: x2: xs) = doMerge $ merge x1 x2: doMerge xs" anrufe, aber doMerge (mergePairs xs) in der schnellen Version aufruft. Ich bin überrascht von dem 1000-fachen Geschwindigkeitsunterschied!
%Vor%Wenn Sie sich die Profiler-Ausgabe anschauen, ist es klar, dass die langsame Version Weise mehr Speicher zuweist. Ich bin mir nicht sicher warum. Beide Versionen scheinen in meinem Kopf ähnlich zu sein. Kann jemand erklären, warum die Zuteilung so anders ist?
slowMergeSort Profilergebnis:
%Vor%libMergeSort Profiling
%Vor% Die zweite davon ist O(n^2) und sollte nicht verwendet werden, da es sich um den falschen Algorithmus handelt (sollte nicht Mergesort genannt werden).
sortiert vollständig xs , was nur eine Konstante kürzer als die ursprüngliche Liste ist. Das Zusammenführen einer sehr kurzen Liste mit einer sehr langen Liste entspricht der Einfügung, also sehen wir, dass dies wirklich nur eine Einfügesortierung ist. Der ganze Punkt von mergesort ist teile und herrsche, das ist nicht teile und herrsche. Wenn die Länge der Listen größer wird, wird das Geschwindigkeitsverhältnis immer schlechter.
Das erste ist eine richtige Zusammenführungssortierung, da es Listen von etwa gleicher Länge zusammenführt.
Tags und Links haskell performance