Warum hat Microsoft in std::list::sort() auf eine Top-Down-Zusammenführungssortierung umgestellt?

std::list<>::sort() – Warum der plötzliche Wechsel zur Top-Down-Strategie?

Trotz der langjährigen Verwendung eines Bodens -up Merge Sort-Ansatz in std::list<>::sort() vollzog Microsoft Visual Studio 2015 einen Übergang zu einer überraschend ineffizienten rekursiven Implementierung der Top-Down-Merge-Sortierung. Diese Änderung wirft Fragen zu den zugrunde liegenden Beweggründen auf.

Anfangs wurde angenommen, dass Microsoft einen zwingenden Grund hatte, zu einem weniger effizienten Ansatz zu wechseln, insbesondere angesichts der Einführung nicht standardmäßig konstruierbarer und zustandsbehafteter Allokatoren in VS2015. Bei weiteren Untersuchungen wurde jedoch festgestellt, dass der ursprüngliche Bottom-Up-Merge-Sort-Algorithmus so geändert werden konnte, dass er mit Iteratoren funktioniert.

Microsofts Top-Down-Ansatz

Microsofts Top-Down-Implementierung verwendet a rekursiver Ansatz, um die Liste auf jeder Rekursionsebene in zwei Hälften zu teilen. Der offensichtliche Grund dafür besteht darin, Bedenken hinsichtlich der Speicherzuweisung und der Ausnahmesicherheit zu vermeiden. Anstatt ein Array von Listen zum Speichern sortierter Läufe zu erstellen, verwenden sie Iteratoren, um die Laufgrenzen innerhalb der ursprünglichen Liste zu verfolgen.

Während dieser Ansatz Probleme bei der Speicherzuweisung verhindern kann, führt er zu einer Ineffizienz in Form von Zugriff auf den Mittelpunkt der Liste bei jedem rekursiven Aufruf, was möglicherweise zu einer langsameren Ausführungszeit führt.

Alternativer Bottom-Up-Ansatz

Als Alternative haben andere Entwickler eine modifizierte Version des Bottom-Up-Ansatzes vorgeschlagen -up Merge Sort-Algorithmus, der Iteratoren anstelle eines Arrays von Listen verwendet. Bei diesem Ansatz wird ein Array von Iteratoren erstellt, wobei jeder Eintrag den Startpunkt eines sortierten Laufs darstellt. Während die Liste gescannt wird, werden Knoten in diesen Läufen zusammengeführt, bis eine einzige sortierte Liste erhalten wird.

Diese Methode bietet sowohl Geschwindigkeit als auch Speichereffizienz und übertrifft die Top-Down-Zusammenführungssortierung bei Listen mit um etwa 40–50 % verstreute Knoten im Speicher.

Fazit

Die Gründe für Microsofts Wechsel zur Top-Down-Merge-Sortierung bleiben etwas unklar. Auch wenn Bedenken hinsichtlich der Speicherzuteilung und der Sicherheit von Ausnahmen die Entscheidung beeinflusst haben könnten, ist es wichtig zu beachten, dass diese Probleme mit alternativen Ansätzen angegangen werden können, die eine höhere Effizienz gewährleisten. Die Wahl eines weniger effizienten Algorithmus deutet darauf hin, dass Microsoft möglicherweise der Stabilität und der Ausnahmebehandlung Vorrang vor der Leistung eingeräumt hat.

Das obige ist der detaillierte Inhalt vonWarum hat Microsoft in std::list::sort() auf eine Top-Down-Zusammenführungssortierung umgestellt?. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!