Angenommen, Sie möchten eine Funktion schreiben, die eine Liste von Objekten liefert, und Sie wissen im Voraus die Länge n einer solchen Liste.
In Python unterstützt die Liste den indizierten Zugriff in O (1), daher ist es wohl eine gute Idee, die Liste vorzubelegen und mit Indizes darauf zuzugreifen, anstatt eine leere Liste zuzuweisen und die Methode append() zu verwenden. Dies liegt daran, dass wir die Last vermeiden, die gesamte Liste zu erweitern, wenn der Platz nicht ausreicht.
Wenn ich Python verwende, sind die Performances wahrscheinlich nicht so relevant, aber was ist der beste Weg, eine Liste vorzubelegen?
Ich kenne diese möglichen Kandidaten:
[None] * n → Zuweisung von zwei Listen [None for x in range(n)] - oder xrange in python2 → ein anderes Objekt erstellen Ist einer deutlich besser als der andere?
Was ist, wenn wir im Fall n = len(input) sind? Da input bereits existiert, hätte [None for x in input] bessere Leistungen w.r.t. [None] * len(input) ?
Zwischen diesen beiden Optionen ist die erste deutlich besser, da keine Python-for-Schleife beteiligt ist.
%Vor%Aktualisierung:
Und list.append hat auch eine O(1) -Komplexität , es könnte also eine bessere Wahl sein als Erstellen einer Liste, wenn Sie die Methode list.append einer Variablen zuweisen.
Wenn Sie ein Element an eine Liste anhängen, überlagert Python diese, finden Sie in der Quelle -code des Listenobjekts. Dies bedeutet, dass zum Beispiel beim Hinzufügen von 1 Gegenstand zu einer Liste von 8 Gegenständen tatsächlich Platz für 8 neue Gegenstände geschaffen wird und nur der erste Gegenstand verwendet wird. Die nächsten 7 Anhänge sind dann 'kostenlos'.
In vielen Sprachen (z. B. Matlab) wird Ihnen immer gesagt, dass Sie Ihre Vektoren vorab zuordnen müssen, da das Hinzufügen während einer Schleife sehr teuer ist. Im schlimmsten Fall kann das Anhängen eines einzelnen Elements an eine Liste mit der Länge n O(n) time kosten, da Sie möglicherweise eine größere Liste erstellen und alle vorhandenen Elemente kopieren müssen. Sie müssen dies bei jeder Iteration tun. Daher sind die Gesamtkosten für das Hinzufügen von n -Elementen O(n^2) , autsch. Pythons Vorverteilungsschema verteilt die Kosten für das Anwachsen des Arrays über viele einzelne Anhänge (siehe amortisierte Kosten ), wodurch effektiv Kosten entstehen eines einzelnen Anhangs O(1) und die Gesamtkosten des Hinzufügens von n Elemente O(n) .
In Python ist der Overhead des restlichen Codes normalerweise so groß, dass die winzige Beschleunigung, die durch die Vorbelegung erreicht werden kann, unbedeutend ist. Vergessen Sie also in den meisten Fällen die Vorbelegung nicht, es sei denn, Ihr Profiler teilt Ihnen mit, dass das Hinzufügen zu einer Liste ein Flaschenhals ist.
Die anderen Antworten zeigen ein Profiling der Listenvorbelegung selbst, aber das ist nutzlos. Das einzige, was zählt, ist das Profilieren Ihres vollständigen Codes mit all Ihren Berechnungen innerhalb Ihrer Schleife, mit und ohne Vorbelegung. Wenn meine Vorhersage richtig ist, ist der Unterschied so klein, dass die Rechenzeit, die du gewinnst, durch die Zeit, die du damit verbracht hast, darüber nachzudenken, die zusätzlichen Zeilen zu schreiben und zu verwalten, in den Schatten gestellt wird.
Offensichtlich die erste Version. Lass mich erklären warum.
Wenn Sie [None] * n erstellen, erstellt Python intern ein Listenobjekt der Größe n und es kopiert das gleiche Objekt (hier None ) ( das ist der Grund, Sie sollten diese Methode nur verwenden, wenn Sie mit unveränderlichen Objekten für alle Speicherorte arbeiten. Die Speicherzuweisung erfolgt also nur einmal. Danach eine einzelne Iteration durch die Liste, um das Objekt auf alle Elemente zu kopieren. list_repeat ist die Funktion, die dieser Art der Listenerstellung entspricht.
Wenn Sie ein Listenverständnis verwenden, um eine Liste zu erstellen, kann Python die tatsächliche Größe der zu erstellenden Liste nicht kennen, daher weist es zuerst einen Teil des Speichers und eine frische Kopie des Objekt wird in der Liste gespeichert. Wenn die Liste über die zugewiesene Länge hinaus wächst, muss sie den Speicher erneut zuordnen und mit der Erstellung des neuen Objekts fortfahren und das in der Liste speichern.
Tags und Links python design-patterns performance list python-3.x