Ist pythons sortierte() Funktion garantiert stabil?

Die documentation übernimmt keine Garantie dafür. Gibt es einen anderen Ort, an dem es dokumentiert ist?Ist pythons sortierte() Funktion garantiert stabil?

Ich denke, es könnte stabil sein, da die Sortiermethode auf Listen guaranteed to be stable ist (Hinweise 9. Punkt: "beginnend mit Python 2.3 ist die sort() -Methode garantiert stabil"), und sortiert ist funktionell ähnlich. Ich finde jedoch keine definitive Quelle, die das sagt.

Zweck: Ich muss auf Basis eines Primärschlüssels und auch eines Sekundärschlüssels in Fällen sortieren, in denen der Primärschlüssel in beiden Datensätzen gleich ist. Wenn sorted() garantiert stabil ist, kann ich nach dem Sekundärschlüssel sortieren, dann nach dem Primärschlüssel sortieren und das Ergebnis erhalten, das ich brauche.

PS: Um jede Verwirrung zu vermeiden, verwende ich stabil im Sinne von "eine Sorte ist stabil, wenn es garantiert, die relative Reihenfolge der Elemente nicht zu ändern, die gleich vergleichen".

Quelle

2009-12-16 sundar

Ja, die Absicht des Handbuchs ist in der Tat zu garantieren, dass sorted ist stabil und in der Tat, dass es genau den gleichen Algorithmus wie die sort Methode verwendet. Ich bin mir bewusst, dass die Dokumente zu dieser Identität nicht hundertprozentig klar sind; Doc-Patches werden immer gerne angenommen!

Quelle

2009-12-16 15:36:08

Ich habe festgestellt, dass, wenn ich Tupel oder Listen sortiere, wenn die "primären" Sortierschlüssel gleich sind, es am Ende sortiert nach dem "sekundären" Schlüssel. Zum Beispiel gibt 'sorted ([(1, 2), (1, 1)]) 'zurück' [(1, 1), (1, 2)]', anstatt die ursprüngliche Eingabe in der gleichen Reihenfolge/Reihenfolge zurückzugeben. Sollte die Garantie der Stabilität nicht bedeuten, dass sie den ursprünglichen "[(1, 2), (1, 1)]" Input zurückgibt? In diesem Fall müssen Sie explizit sein und sagen 'sortierte ([(1, 2), (1, 1)], Schlüssel = Lambda t: t [0])' – ray

Ist das nicht, was in diesem Fall erwartet wird? Python wird Tupel standardmäßig mit allen Elementen vergleichen, nicht nur mit dem ersten "primären". Wenn Sie nur nach dem ersten Element sortieren möchten, können Sie den Parameter 'key' explizit übergeben. –

Die "What's New" docs for Python 2.4 effektiv machen den Punkt, dass sorted() erstellt zuerst eine Liste, dann ruft sort() auf, bietet Ihnen die Garantie, die Sie benötigen, aber nicht in der "offiziellen" Dokumente. Sie können auch einfach die Quelle überprüfen, wenn Sie wirklich besorgt sind.

Quelle

2009-12-16 15:38:39

Kannst du darauf hinweisen, wo es so steht? Es sagt sorted() "funktioniert wie die In-Place-List.sort()" und "eine neu gebildete Kopie ist sortiert", aber ich sehe es nicht sagen, dass es intern sort() verwendet. – sundar

Die "Kopie", die gebildet wird, ist eine Liste (das ist, was Sie als Rückgabewert erhalten), und .sort() wird in dieser Liste vor der Rückkehr aufgerufen. QED. Nein, es ist kein unanfechtbarer Beweis, aber bis Python einen offiziellen Standard hat, werden Sie das nicht bekommen. –

Sie sind stable. Sie müssen zwar nicht wissen, ob die Sortierung und Sortierung stabil ist, da Sie bei mehreren Schlüsseln nicht in zwei Schritten sortieren müssen.

Zum Beispiel, wenn Sie Objekte sortieren möchten auf der Grundlage ihrer last_name, first_name Attribute können Sie:

sorted_list= sorted(
    your_sequence_of_items, 
    key= lambda item: (item.last_name, item.first_name))

Vorteil Tupel Vergleich nehmen.

Diese Antwort, wie sie ist, deckt die ursprüngliche Frage ab. Für weitere sortierbezogene Fragen gibt es die Python Sorting How-To.

Quelle

2009-12-28 22:42:14 tzot

Dies kann unerwünschte Auswirkungen haben, wenn Sie die Sortierung umkehren möchten. Zum Beispiel, wenn Sie nach Produkten sortieren, möchten Sie vielleicht zuerst die Bewertung (aufsteigend) und dann den Preis (auch aufsteigend) sortieren. Wenn Sie dies umkehren, möchten Sie die Bewertung in absteigender Reihenfolge, aber aufsteigend nach Preis sortieren. Dies funktioniert nicht mit dieser Lösung. –

@RemcoWendt: Es gab keine Anforderung für das, was Sie beschreiben. Berücksichtigen Sie in jedem Fall 'key = lambda item: (-item.rating, item.price)' oder ein 'cmp' anstelle eines' key'-Arguments. Ich bin mir immer noch nicht sicher über den Zweck Ihres Kommentars. – tzot

In der Tat war es keine Voraussetzung, sondern wollte auf diesen feinen Unterschied hinweisen, wenn andere Leute dies lesen und eine Entscheidung zwischen Ihrer Lösung oder Pythons stabiler Sortierfunktion treffen. –

Es wahrscheinlich in der Zwischenzeit aber die aktuelle Dokumentation von sorted ausdrücklich garantuees es geändert:

Die eingebauten in sorted() Funktion stabil sein garantiert. Eine Sortierung ist stabil, wenn sichergestellt wird, dass die relative Reihenfolge der Elemente, die mit "Gleich" verglichen werden, nicht geändert wird. Dies ist hilfreich bei der Sortierung in mehreren Durchgängen (z. B. nach Abteilung und Gehaltsstufe).

Quelle

2017-05-16 22:49:52 MSeifert

Ist pythons sortierte() Funktion garantiert stabil?

Antwort

Verwandte Themen