Antwort diese Frage Ich sah eine interessante Situation 2 ähnlicher Code Snippets haben sich ganz anders verhalten. Ich frage hier nur, um den Grund dafür zu verstehen und meine Intuition für solche Fälle zu verbessern.
Ich werde Code-Snippets für Python 2.7 anpassen (in Python 3 sind die Leistungsunterschiede gleich).
%Vor%Ausgabe:
%Vor% Die erste Lösung muss Suchen in OrderedDictionary durchführen, um value für jede key zu erhalten. Die zweite Lösung iteriert nur durch OrderedDictionary Schlüssel-Wert-Paare, die in Tupel gepackt werden müssen.
Die zweite Lösung ist 2 mal langsamer.
Warum ist das so?
Ich habe kürzlich dieses Video angeschaut, wo Raymond Hettinger sagt, dass Python tendiert Tupel wiederverwenden, also keine zusätzlichen Zuweisungen.
Also, was macht dieses Leistungsproblem aus?
Ich möchte ein wenig darauf eingehen, warum ich frage.
Die erste Lösung hat Dictionary-Lookup. Es impliziert, dass key hash genommen wird, dann nach Bin durch diesen Hash gesucht wird, dann Schlüssel aus diesem Bin abgerufen wird (hoffentlich wird es keine Schlüsselkollisionen geben) und dann Wert mit diesem Schlüssel assoziiert bekommen.
Die zweite Lösung durchläuft einfach alle Bins und liefert alle Schlüssel in diesen Bins. Es geht durch alle Behälter eins nach dem anderen ohne einen Rechenaufwand, den ich zu nehmen habe. Ja, es muss auf Werte zugreifen, die diesen Schlüsseln zugeordnet sind, aber der Wert ist nur einen Schritt vom Schlüssel entfernt, während die erste Lösung die Hash-Bin-Schlüssel-Wert-Kette durchlaufen muss, um den Wert zu erhalten, wenn er benötigt wird. Jede Lösung muss den Wert erhalten, der erste bekommt sie durch die Hash-Bin-Schlüssel-Wert-Kette, der zweite bekommt sie beim Zugriff auf den Schlüssel einen weiteren Zeiger folgen. Der einzige Overhead der zweiten Lösung ist, dass dieser Wert zusammen mit dem Schlüssel im temporären Tupel gespeichert werden muss. Es stellt sich heraus, dass diese Speicherung der Hauptgrund für den Overhead ist. Dennoch verstehe ich nicht ganz, warum es so ist, angesichts der Tatsache, dass es eine sogenannte "Tupel-Wiederverwendung" gibt (siehe das oben erwähnte Video).
Meiner Meinung nach muss die zweite Lösung zusammen mit dem Schlüssel Wert sparen, aber es vermeidet, dass wir Hash-Bin-Key-Berechnungen und Zugriffe durchführen müssen, um Wert für diesen Schlüssel zu erhalten.
Die Leistungsunterschiede werden hauptsächlich von OrderedDict verursacht.
OrderedDict verwendet dict 's get und __getitem__ , hat aber seine eigene __iter__ und iteritems .
Schauen Sie sich an, was wir gefunden haben: self[k] .
Ihre zweite Lösung hat uns nicht dabei geholfen, die Hash-Bin-Key-Berechnung zu vermeiden.
Während der Iterator von dict generiert wird, genauer gesagt, items.iteritems().next() Wenn items ein dict ist, wird diese Berechnung nicht durchgeführt.
Außerdem ist iteritems auch teurer.
Ausgabe
%Vor% Vergleichen mit iterkeys ' dictiter_iternextkey und itervalues ' dictiter_iternextvalue , iteritems ' dictiter_iternextitem enthält zusätzliche Teile.
Ich denke, dass Tupel-Erstellung die Leistung verringern könnte.
Tatsächlich neigt Python dazu, Tupel wiederzuverwenden.
tupleobject.c zeigt
Diese Optimierung bedeutet nur, dass Python einige Tupel nicht von Grund auf neu erstellt. Aber es gibt noch viel zu tun.
Wenn OrderedDict durch dict ersetzt wird, denke ich, dass die zweite Lösung im Allgemeinen etwas besser ist.
Python-Wörterbücher werden mithilfe von Hashtabellen implementiert. Die Suche ist also schnell. Die durchschnittliche Zeitkomplexität der Suche ist O (1), während die schlechteste O (n) <1> ist.
Die durchschnittliche Zeitkomplexität Ihrer ersten Lösung entspricht der zeitlichen Komplexität Ihrer zweiten Lösung. Sie sind beide O (n).
Daher hat die zweite Lösung keine Vorteile oder ist sogar manchmal langsamer, insbesondere wenn die Eingabedaten klein sind.
In diesem Fall konnten die durch iteritems verursachten zusätzlichen Kosten nicht kompensiert werden.
Ausgabe
%Vor% Ersetzen Sie dann N und xs durch
Ausgabe
%Vor% Ersetzen Sie nun N und xs durch
Ausgabe
%Vor%Schließlich beginnt die zweite Lösung zu scheinen.
Der schlimmste Fall für die erste Lösung: Hash-Kollision
Lassen Sie
%Vor%Ausgabe
%Vor%1 Die für dict-Objekte aufgeführten Average-Case-Zeiten setzen voraus, dass die Hash-Funktion für die Objekte ausreichend robust ist, um Kollisionen zu vermeiden. Der Average Case geht davon aus, dass die in den Parametern verwendeten Schlüssel gleichmäßig aus der Menge aller Schlüssel ausgewählt werden. Siehe TimeComplexity .
Für Tupelwiederverwendung glaube ich es nicht:
%Vor%Sie können von int oder string sehen:
%Vor%bearbeiten:
Für dict sind Ihre beiden Methoden ähnlich. Lass es uns versuchen:
Obwohl sich die Zeit ändern kann, sind sie im Allgemeinen korrekt. Die Verwendung von iteritems und itemgetter ist so schnell wie get .
Aber für OrderedDict , versuchen wir es noch einmal:
Sie können sehen, dass für OrderedDict , verwenden Sie get und die eine iterator und itemgetter zeitlich variieren.
Also, ich denke der Zeitunterschied liegt an der Implementierung von OrderedDict . Tut mir leid, ich weiß nicht warum.
Wie Sie selbst erwähnt haben, gibt es einen Unterschied zwischen den Funktionen.
Wo die erste Funktion über eine Liste von Strings iteriert, geht sie für jede Zeichenkette zum Wörterbuch und sucht nach dem Wert, dann findet sie das Minimum und kehrt zurück.
Die zweite Funktion iteriert über Tupel von string / int-Paaren. und dann greift es für jedes auf das zweite Element (den int / value) zu und findet dann das Minimum (in diesem Fall ein Tupel) und gibt dann das erste Element zurück.
Die zweite Funktion macht viel mehr Arbeit an Objekten, die viel mehr Verarbeitung benötigen (Tupel & gt; Strings) und dann (Tupel & gt; ints), plus dem zusätzlichen Gegenstandsabruf.
Warum sind Sie überrascht?
Um auf meine vorherige Antwort zu erweitern. Um eine bessere Übersicht über die Vorgänge zu erhalten, können Sie immer das Modul dis verwenden.
Wie Sie sehen, ist in f2 noch viel mehr passiert (und deshalb wäre es logisch, dass es langsamer ist)
Sie können immer das Modul dis verwenden, um alles in Python zu überprüfen ein guter Hinweis darauf, was besser funktioniert.
Man kann immer das Modul timeit verwenden, um das Timing oder die Leistung bestimmter Methoden zu überprüfen Funktionen, die sie für bestimmte Eingabearten ausführen, aber manchmal kann das Timing deaktiviert sein, da der verwendete Beispieldatensatz für eine bestimmte Funktion besser geeignet ist als für eine andere, z. B. beim Sortieren einer Sortierfunktion würde bereits eine bestimmte Art von Funktion gegenüber einer anderen bevorzugen, die schneller eine weniger sortierte Liste sortieren kann, aber keine von diesen berücksichtigt verschiedene Arten von Daten, die sich möglicherweise in den Listen selbst befinden. Die Verwendung des dis -Moduls vermeidet die meisten davon, indem man direkt sehen kann, was Python hinter dem Vorhang (oder unter der Haube), der einen viel klareren Hinweis darauf gibt, welche Methode am besten geeignet ist, bestimmte Aufgaben auszuführen.
Tags und Links python python-2.7