Ich verstehe den Unterschied zwischen geordneten und ungeordneten Mengen und verstehe, warum wir für viele Zwecke keine geordneten Mengen benötigen. Aber alle Mengenoperationen sind immer noch möglich für bestellte Sets, und Sets müssen ohnehin intern mit einer bestimmten Reihenfolge gespeichert werden. Warum werden Sets also nicht standardmäßig bestellt? Ist die Auswirkung der Beibehaltung der Reihenfolge der Mengen auf die Leistung zu groß?
Kommentare
- Beachten Sie, dass die “ Die Reihenfolge “ von Werten in einer ungeordneten Sammlung hängt möglicherweise mehr von der Einfügereihenfolge und weniger (wenn überhaupt) von den Werten selbst ab, was nicht ‚ t eine Reihenfolge in dem üblicherweise verwendeten Sinne (der aus dem mathematischen Begriff stammt).
- Diese Frage kann als nicht thematisch betrachtet werden, da sie nicht ‚ ist Es geht nicht darum, ein bestimmtes Programm zu entwickeln, sondern um ein Sprachdesign.
- @outis Ich war ‚ nicht sicher, welche Unterwebsite richtig ist. Gibt es eine andere, die Sie verwenden? würde vorschlagen?
Antwort
Der Punkt ist nicht, dass der Overhead besonders groß ist, sondern dass er vorhanden ist überhaupt .
Sprachfunktionen müssen immer ein Gleichgewicht zwischen Kosteneffizienz herstellen. Wörterbücher sind für die Python-Programmierung von grundlegender Bedeutung, daher wäre es sehr schlecht, wenn sie noch etwas langsamer wären als nur, um die Einfügereihenfolge beizubehalten, wenn Sie die meiste Zeit keine Bestellung benötigen. Es war die richtige Entscheidung Verwerfen Sie die Einfügereihenfolge als Gegenleistung für einen etwas schnelleren Zugriff und lassen Sie die auftragserhaltende Datenstruktur für spezielle Klassen. Wenn es eine andere Datenstruktur gibt, die alles kann, was ein Diktat kann, und Diktat eine weniger häufig verwendete Falte der Sprache ist, Dinge könnte anders aussehen.
Kommentare
- Mein Gegenargument dazu wäre: Verwenden Sie einen effizienteren ungeordneten Diktat-Datentyp für interne Wörterbücher (genau wie dort) ‚ s
deque, um die Leistung in bestimmten anderen Kontexten zu optimieren), aber lassen Sie den Hauptbenutzer-diktierten Datentyp die Reihenfolge beibehalten.
ch habe auch Recht, wenn ich verstehe, dass die CPython-Implementierung von 3.6 tatsächlich die Einfügereihenfolge für beibehält dicts?
Antwort
Sie haben Recht, dass Artikel intern mit einer bestimmten Reihenfolge gespeichert werden, aber diese interne Reihenfolge ist Wird durch den Hash-Code des Schlüssels bestimmt, wodurch der Abruf so schnell erfolgt. Wenn also ein Satz / Diktat bestellt werden soll, muss dafür eine separate interne Datenstruktur (z. B. eine geordnete Liste von Schlüsseln) verwaltet werden.
Dies würde natürlich die Größe erhöhen. Aber vielleicht noch schlimmer, es wird die Leistung beeinträchtigen. Zum Beispiel ist das Entfernen eines Elements aus einem Satz eine O (1) -Operation, aber wenn es auch den Schlüssel aus einer internen geordneten Liste entfernen muss, wird es zu O (n). Solche Kosten wären für einige Anwendungen katastrophal. Da es ziemlich selten ist, dass Sie einen geordneten Satz benötigen, lohnt sich ein solcher Kompromiss für die Standard-Satz- / Diktat-Typen nicht.
Antwort
Ihre Prämisse ist falsch. Ab Python 3.6 merken sich dict ihre Einfügereihenfolge . Dies war ein Implementierungsdetail und wurde in 3.7 auf die vollständige Sprachfunktion hochgestuft. In 3.6 wird für den speziellen Fall von **kwargs die Beibehaltung der Reihenfolge speziell garantiert.
Kommentare
- Ja, ich war mir ‚ nicht bewusst, als ich die Frage stellte, da ‚ noch keine Sprachfunktion ist, sondern nur eine Implementierung Detail in einer Implementierung. Aber es scheint, dass zumindest Wörterbücher langfristig geordnet werden und hoffentlich auch gesetzt werden.
- @oulenz es ‚ ist kein Implementierungsdetail mehr, es ‚ s erforderlich ab Python 3.7
Antwort
Eine Bestellung set ist nur möglich, wenn die zu speichernden Elemente in erster Linie eine Reihenfolge (dh eine Vergleichsmethode) haben – dies ist jedoch nicht immer gegeben.
Die Standard-Implementierung von set / map ist heutzutage in den meisten Umgebungen basierend auf einer Autoresizing-Hashtabelle, die folgende Vorteile bietet:
- schneller
- verwendet weniger Speicher
- erfordert nicht, dass die Elemente eine Reihenfolge angeben
Sätze müssen ohnehin in einer bestimmten Reihenfolge intern gespeichert werden.
Diese innere Ordnung hat aber nicht unbedingt eine Bedeutung und bleibt auch nicht gleich. In der Tat ist eine Eigenschaft von Hashtabellen, die unerfahrene Entwickler manchmal verwirrt, dass sich die Iterationsreihenfolge, die auf der internen Reihenfolge basiert, vollständig ändern kann, wenn Elemente hinzugefügt werden (dh wenn eine Größenänderung ausgelöst wird) oder zwischen verschiedenen läuft.
Kommentare
- Ich verstehe ‚ Ihre erste Bemerkung nicht. Wir ‚ benötigen keine Vergleichsmethode, die Reihenfolge könnte einfach vererbt werden, z. aus einer Liste oder einem String-Literal
{3, 5, 4}. - @oulenz: Wenn Sie ‚ nichts dagegen haben, ist die Reihenfolge Bedeutungslos und im Laufe der Zeit variierend, wird jeder Satz geordnet, da es eine Iterationsreihenfolge gibt. “ geordnete Menge “ impliziert jedoch, dass die Reihenfolge für die Elemente semantisch ist und dies nicht immer möglich ist. Ich verstehe ‚ nicht wirklich, warum alle Sätze bestellt werden sollen.
- “ Bestellter Satz “ bedeutet nicht, dass die Reihenfolge semantisch ist, nur dass es eine Reihenfolge gibt. Natürlich ist es mir wichtig, dass diese Reihenfolge beibehalten wird, sobald sie geändert wurde, es sei denn, ihr Inhalt wurde geändert.
- Es tut mir leid, ‚ war mir nicht bewusst, dass eine Implikation bestand für einige Leute. Ich dachte einfach an eine linear geordnete Menge aus der Mathematik. de.wikipedia.org/wiki/Total_order
- @jameslarge die Ordnungsbeziehung nicht ‚ Ich muss mir unbekannt sein. Wenn ich einen bestellten Satz aus einer Liste ableite, weiß ich genau, wie er bestellt ist. Wenn ich eine bestimmte Reihenfolge sicherstellen möchte, kann ich das Set sortieren. Wenn Sie ‚ die Bestellung jedoch nicht benötigen, können Sie sie einfach ignorieren.
Antwort
Die allgemeine Idee hinter einem Set oder einem Wörterbuch ist, dass Sie viele Suchvorgänge ausführen möchten. Es wird für diese Suchoperationen optimiert, indem ein Hash verwendet wird, der in den meisten Fällen eine O (1) -Suche ermöglicht.
Die Reihenfolge erfolgt über Arrays oder verknüpfte Listen. Tatsächlich werden Operationen optimiert, bei denen die Reihenfolge wichtig ist für das wie das Anhängen eines Werts am Ende oder am Anfang.
Aufgrund der Art dieser beiden Datenstrukturen ist keine für beide optimiert. Dies bedeutet nicht, dass dies nicht möglich ist, umfasst jedoch beide Datenstrukturen, wenn sowohl Such- als auch auftragsbasierte Vorgänge optimiert werden sollen.
Sie haben also diesen Kompromiss zwischen:
Optimierung von Suchvorgängen < => auftragsbasierten Operationen < => Speichernutzung
Der allgemeine Konsens ist, dass Sie als Programmierer im Allgemeinen für das eine oder andere optimieren möchten, aber nicht für beide, und sicherlich befürwortet niemand, die Speichernutzung zu verdoppeln, wenn Sie sie nur benötigen um einen der beiden zu optimieren.
Das heißt, es gibt Implementierungen mit beiden oder zumindest in Java, insbesondere LinkedHashMap ist sowohl ein Array als auch ein Hash- basiertes Wörterbuch. Manchmal benötigen Sie möglicherweise beides, es wird jedoch empfohlen, ArrayList zu verwenden, wenn Sie nur eine Liste benötigen, und HashMap, wenn Sie nur ein Wörterbuch benötigen .
Kommentare
- Huh? Eine Java LinkedHashMap ist nicht “ sowohl ein Array als auch ein Hash-basiertes Wörterbuch „. ‚ ist im Grunde eine HashMap (dh verwendet ein Array intern), die mit einer verknüpften Liste überlagert ist, um eine Iteration in Einfügereihenfolge zu ermöglichen.
- Lineare Datenstrukturen sind keine ‚ t die einzigen geordneten Datenstrukturen; Es können auch Binärbäume bestellt werden (z. B. Rot-Schwarz- und AVL-Bäume). Eine weitere Operation, die am Kompromiss beteiligt sein kann, ist das Einfügen (Arrays sind in Bezug auf Suche, Iteration und Speichernutzung recht effizient, beim Einfügen jedoch am langsamsten).