Stabile vs. instabile Sortierung

Bei store2be haben wir ein Problem festgestellt, als wir unsere Rails-Testsuiten in unseren beiden Hauptentwicklungsumgebungen ausführten. Unter Mac OS X hatten wir einen Test, der durchgehend fehlschlug, während er unter Linux jedes Mal gut durchlief, was in gewisser Weise die alte Software beweist Entwicklungsspruch über die Wichtigkeit, Entwicklungsmaschinen so ähnlich wie möglich zu haben, auf denen Ihr Produktionscode ausgeführt wird.

Bei der Untersuchung stellten wir fest, dass das Problem darin bestand, wie der jeweilige Test erwartete, dass Elemente sortiert wurden.

Was ist passiert

Der grundlegende Unterschied zwischen stabilen und instabilen Sortieralgorithmen besteht darin, dass bei der Sortierung nach einem nicht eindeutigen Wert, der mehrere Elemente gruppiert, die ursprüngliche Reihenfolge der Elemente beibehalten wird. Dies ist im Wesentlichen das, was wir getestet haben, dass Elemente in Gruppen sortiert wurden und dass sie innerhalb jeder Gruppe in ihrer ursprünglichen Reihenfolge (der Reihenfolge, in der sie hinzugefügt wurden) blieben.

Der einfachste Weg, um diesen Unterschied zu erkennen, besteht darin, nach einem nicht eindeutigen Wert zu sortieren, der eine Gruppe von Elementen definiert, z. B. ein "Dringlichkeits" -Feld für eine Aufgabe. Wenn eine Sortierfunktion nur dieses Dringlichkeitsfeld berücksichtigt, bleibt die endgültige Reihenfolge von zwei Elementen mit derselben Dringlichkeit dem verwendeten Algorithmus überlassen und es kann nicht garantiert werden, dass die ursprüngliche Reihenfolge beibehalten wird. Ein anderes Beispiel ist das Sortieren nach dem ersten Buchstaben des Wortes anstelle des gesamten Wortes. Jeder Sortieralgorithmus gibt Ihnen ein korrekt sortiertes Array, aber nur ein stabiler Algorithmus behält die ursprüngliche Reihenfolge der Elemente in jeder Gruppe bei.

Wir haben ein Array von Objekten (die Dokumente darstellen) erstellt, die dann nach ihrem „Typ“ (einer alphanumerischen Zeichenfolge) sortiert werden, der innerhalb des Arrays nicht eindeutig sein muss (z. B. könnten zwei Dokumente beide eine Art „Vertrag“ haben). ). In unserer Spezifikation erwarteten wir jedoch, dass Dokumente des gleichen Typs in der gleichen Reihenfolge bleiben, in der sie dem Array hinzugefügt wurden. Auf unseren Linux-Computern und in CI funktionierte dies wie beabsichtigt, auf unseren Macs nicht.

Warum war das Verhalten anders

Das Problem trat in unserer Rails-Anwendung auf. Daher haben wir die Ursache ermittelt, indem wir ein hervorragendes Tool namens Pry ausgeführt haben, um den Quellcode hinter der Ruby-Sortiermethode zu untersuchen. Die Sortierung erfolgt durch einen Funktionsaufruf von qsort C. Unter Mac OS X wird ein schneller Sortieralgorithmus verwendet, wie der Name vermuten lässt, der von Natur aus nicht stabil ist. Im speziellen Fall der Mac OS X-Implementierung (die wiederum von FreeBSD stammt) ist sie instabil.

Wir können diese Instabilität in Aktion sehen, wenn wir das folgende Array betrachten [21, 12, 47, 41, 33, 11, 13, 31, 43]. Wenn wir unter Mac OS X nach der ersten Ziffer sortieren, entweder in C (mit qsort) oder in Ruby (sort oder sort_by), erhalten wir [12, 13, 11, 21, 33, 31, 47, 43, 41] zurück und Obwohl dies tatsächlich nach der ersten Ziffer sortiert ist, sehen wir, dass die 11 im letzten Array auf die 13 folgt, obwohl sie im ursprünglichen Array tatsächlich davor steht. 41 und 43 werden auch im letzten Array vertauscht. Hier ist eine Illustration der Mac OS X-Implementierung für die schnelle Sortierung in Aktion, die genau dieses Verhalten veranschaulicht:

Wir können sehen, dass, wenn die 13 mit den 47 tauschen, sie über die 11 tauschen, die nach der 13 in der endgültigen Anordnung endet.

Ohne auf strenge Beweise für Stabilität / Instabilität einzugehen, werden wir feststellen, dass durch die schnelle Verwendung mehrerer, nicht benachbarter Zeiger zum Vertauschen von Elementen die Möglichkeit besteht, dass sie aus ihrer ursprünglichen Reihenfolge herausfallen und durcheinander geraten.

Anders als der Name vermuten lässt, ist qsort nicht unbedingt auf allen Betriebssystemen eine schnelle Sortierung. Mats Linander hat einen sehr schönen Artikel über die Unterschiede in der Implementierung von qsort in einer Vielzahl von Bibliotheken.

In Bezug auf die Implementierung von GLIBC (die von den meisten Linux-Distributionen verwendet wird) erwähnt er:

Dieses qsort () ist insofern interessant, als es quicksort zugunsten von merge sort meidet.

Ja, da ist das Problem!

Es ist in der Tat interessant, weil Mergesort tatsächlich stabil ist! Wenn wir qsort () (oder in diesem Fall sort_by in ruby) in unserem Beispielarray von zuvor auf einem Linux-Computer ausführen und erneut nur nach der ersten Ziffer und nicht nach der gesamten Zahl sortieren, sehen wir, dass der Algorithmus für unser Beispiel tatsächlich ist stable (es gibt [12, 11, 13, 21, 33, 31, 47, 41, 43] zurück). Unsere Tests haben bestanden, weil unser Array wie erwartet sortiert wurde und unsere Dokumente gruppiert, aber in der ursprünglichen Reihenfolge unter ähnlichen Dokumenten belassen wurde. Merge Sort vergleicht Elemente mit Elementen, die direkt neben ihnen liegen. Daher tritt kein "Sprung" auf, der möglicherweise die ursprüngliche Reihenfolge ändern kann. Hier ist ein illustriertes Beispiel:

GLIBCs

Was wir geändert haben

Code-Verhalten und -Tests sollten so reproduzierbar und deterministisch wie möglich sein. Anstatt fehlerhafte Tests auf unseren Macs zuzulassen, haben wir das Problem behoben. Ruby selbst bietet jedoch keine einfachen Alternativen, um die Sortierstabilität zu gewährleisten. Daher haben wir (wohl) die einfachste Lösung entwickelt.

Wir verwendeten weiterhin Rubys Sortierung, aber anstatt ausschließlich nach unserem nicht eindeutigen Feld zu sortieren, berücksichtigten wir auch den Index jedes Elements im ursprünglichen Array. Auf diese Weise würden zwei Elemente, die während des Sortierens "gebunden" wurden, aufgrund ihrer unterschiedlichen Indizes immer in der Reihenfolge landen, in der sie ursprünglich waren.

Diese Übersicht zeigt die verwendete Lösung. Der Grund, warum ein Array des Elements und seines Index zum Sortieren verwendet wurde, anstatt das Element und den Index zu verketten, ist, dass wir uns keine Gedanken über Auffüllungen machen müssen, wenn verschiedene Elemente unterschiedliche Größe / Länge haben .

Durch eine stabile Sortierung haben wir uns deterministisch verhalten und Tests in all unseren Umgebungen bestanden, genau so, wie es sein sollte.

Hallo zusammen, wir sind store2be, ein Berliner Startup, das einen SaaS-fähigen Marktplatz für kurzfristige Einzelhandelsflächen aufbaut. Wenn Ihnen das, was wir veröffentlichen, gefällt, schauen Sie sich vielleicht die store2be-Tech-Seite an oder folgen Sie unserem Medium-Kanal.