Python - Erstellen Sie eine Liste mit anfänglicher Kapazität

187

Code wie dieser passiert oft:

l = []
while foo:
    #baz
    l.append(bar)
    #qux

Dies ist sehr langsam, wenn Sie Tausende von Elementen an Ihre Liste anhängen möchten, da die Größe der Liste ständig an die neuen Elemente angepasst werden muss.

In Java können Sie eine ArrayList mit einer anfänglichen Kapazität erstellen. Wenn Sie eine Vorstellung davon haben, wie groß Ihre Liste sein wird, ist dies viel effizienter.

Ich verstehe, dass Code wie dieser oft in ein Listenverständnis umgewandelt werden kann. Wenn die for / while-Schleife jedoch sehr kompliziert ist, ist dies nicht möglich. Gibt es ein Äquivalent für uns Python-Programmierer?

Claudiu
quelle
12
Soweit ich weiß, ähneln sie ArrayLists darin, dass sie jedes Mal ihre Größe verdoppeln. Die Amortisationszeit dieser Operation ist konstant. Es ist kein so großer Performance-Hit, wie Sie denken würden.
mmcdole
scheint, als hättest du recht!
Claudiu
10
Vielleicht ist eine Vorinitialisierung für das OP-Szenario nicht unbedingt erforderlich, aber manchmal ist sie definitiv erforderlich: Ich habe eine Reihe von vorindizierten Elementen, die an einem bestimmten Index eingefügt werden müssen, aber nicht in der richtigen Reihenfolge sind. Ich muss die Liste im Voraus erweitern, um IndexErrors zu vermeiden. Danke für diese Frage.
Neil Traft
1
@Claudiu Die akzeptierte Antwort ist irreführend. Der am höchsten bewertete Kommentar darunter erklärt, warum. Würden Sie eine der anderen Antworten akzeptieren?
Neal Gokli

Antworten:

126
def doAppend( size=10000 ):
    result = []
    for i in range(size):
        message= "some unique object %d" % ( i, )
        result.append(message)
    return result

def doAllocate( size=10000 ):
    result=size*[None]
    for i in range(size):
        message= "some unique object %d" % ( i, )
        result[i]= message
    return result

Ergebnisse . (Bewerten Sie jede Funktion 144 Mal und mitteln Sie die Dauer)

simple append 0.0102
pre-allocate  0.0098

Fazit . Es spielt kaum eine Rolle.

Vorzeitige Optimierung ist die Wurzel allen Übels.

S.Lott
quelle
18
Was ist, wenn die Vorbelegungsmethode (Größe * [Keine]) selbst ineffizient ist? Ordnet die Python-VM die Liste tatsächlich sofort zu oder erweitert sie schrittweise, genau wie es append () tun würde?
Haridsv
9
Hallo. Es kann vermutlich in Python ausgedrückt werden, aber noch hat niemand es hier gepostet. Der Punkt von haridsv war, dass wir nur davon ausgehen, dass 'int * list' nicht nur Punkt für Punkt an die Liste angehängt wird. Diese Annahme ist wahrscheinlich gültig, aber Haridsv meinte, wir sollten das überprüfen. Wenn es nicht gültig wäre, würde dies erklären, warum die beiden Funktionen, die Sie gezeigt haben, fast identische Zeiten benötigen - weil sie unter der Decke genau dasselbe tun und daher das Thema dieser Frage nicht wirklich getestet haben. Freundliche Grüße!
Jonathan Hartley
135
Dies ist nicht gültig; Sie formatieren mit jeder Iteration eine Zeichenfolge, die im Vergleich zu dem, was Sie testen möchten, ewig dauert. Angesichts der Tatsache, dass 4% je nach Situation immer noch signifikant sein können und es eine Unterschätzung ist ...
Philip Guin
39
Wie @Philip hervorhebt, ist die Schlussfolgerung hier irreführend. Die Vorbelegung spielt hier keine Rolle, da die Formatierung der Zeichenfolge teuer ist. Ich habe mit einer billigen Operation in der Schleife getestet und festgestellt, dass die Vorbelegung fast doppelt so schnell ist.
Keith
11
Falsche Antworten mit vielen Gegenstimmen sind eine weitere Wurzel allen Übels.
Hashimoto
79

Python-Listen haben keine integrierte Vorbelegung. Wenn Sie wirklich eine Liste erstellen müssen und den Aufwand für das Anhängen vermeiden müssen (und Sie sollten dies überprüfen), können Sie Folgendes tun:

l = [None] * 1000 # Make a list of 1000 None's
for i in xrange(1000):
    # baz
    l[i] = bar
    # qux

Vielleicht könnten Sie die Liste vermeiden, indem Sie stattdessen einen Generator verwenden:

def my_things():
    while foo:
        #baz
        yield bar
        #qux

for thing in my_things():
    # do something with thing

Auf diese Weise wird nicht jede Liste im Speicher gespeichert, sondern nur nach Bedarf generiert.

Ned Batchelder
quelle
7
+1 Generatoren statt Listen. Viele Algorithmen können leicht überarbeitet werden, um mit Generatoren anstelle von vollständig materialisierten Listen zu arbeiten.
S.Lott
Generatoren sind eine gute Idee, stimmt. Ich wollte einen allgemeinen Weg, dies zu tun, abgesehen von der Einstellung vor Ort. Ich denke, der Unterschied ist gering, thoguh.
Claudiu
50

Kurzfassung: verwenden

pre_allocated_list = [None] * size

eine Liste vorab zuzuweisen (dh in der Lage zu sein, 'Größen'-Elemente der Liste zu adressieren, anstatt die Liste schrittweise durch Anhängen zu bilden). Diese Operation ist sehr schnell, selbst auf großen Listen. Das Zuweisen neuer Objekte, die später Listenelementen zugewiesen werden, dauert VIEL länger und ist in Bezug auf die Leistung DER Engpass in Ihrem Programm.

Lange Version:

Ich denke, dass die Initialisierungszeit berücksichtigt werden sollte. Da in Python alles eine Referenz ist, spielt es keine Rolle, ob Sie jedes Element auf None oder eine Zeichenfolge setzen - so oder so ist es nur eine Referenz. Es dauert jedoch länger, wenn Sie für jedes zu referenzierende Element ein neues Objekt erstellen möchten.

Für Python 3.2:

import time
import copy

def print_timing (func):
  def wrapper (*arg):
    t1 = time.time ()
    res = func (*arg)
    t2 = time.time ()
    print ("{} took {} ms".format (func.__name__, (t2 - t1) * 1000.0))
    return res

  return wrapper

@print_timing
def prealloc_array (size, init = None, cp = True, cpmethod=copy.deepcopy, cpargs=(), use_num = False):
  result = [None] * size
  if init is not None:
    if cp:
      for i in range (size):
          result[i] = init
    else:
      if use_num:
        for i in range (size):
            result[i] = cpmethod (i)
      else:
        for i in range (size):
            result[i] = cpmethod (cpargs)
  return result

@print_timing
def prealloc_array_by_appending (size):
  result = []
  for i in range (size):
    result.append (None)
  return result

@print_timing
def prealloc_array_by_extending (size):
  result = []
  none_list = [None]
  for i in range (size):
    result.extend (none_list)
  return result

def main ():
  n = 1000000
  x = prealloc_array_by_appending(n)
  y = prealloc_array_by_extending(n)
  a = prealloc_array(n, None)
  b = prealloc_array(n, "content", True)
  c = prealloc_array(n, "content", False, "some object {}".format, ("blah"), False)
  d = prealloc_array(n, "content", False, "some object {}".format, None, True)
  e = prealloc_array(n, "content", False, copy.deepcopy, "a", False)
  f = prealloc_array(n, "content", False, copy.deepcopy, (), False)
  g = prealloc_array(n, "content", False, copy.deepcopy, [], False)

  print ("x[5] = {}".format (x[5]))
  print ("y[5] = {}".format (y[5]))
  print ("a[5] = {}".format (a[5]))
  print ("b[5] = {}".format (b[5]))
  print ("c[5] = {}".format (c[5]))
  print ("d[5] = {}".format (d[5]))
  print ("e[5] = {}".format (e[5]))
  print ("f[5] = {}".format (f[5]))
  print ("g[5] = {}".format (g[5]))

if __name__ == '__main__':
  main()

Auswertung:

prealloc_array_by_appending took 118.00003051757812 ms
prealloc_array_by_extending took 102.99992561340332 ms
prealloc_array took 3.000020980834961 ms
prealloc_array took 49.00002479553223 ms
prealloc_array took 316.9999122619629 ms
prealloc_array took 473.00004959106445 ms
prealloc_array took 1677.9999732971191 ms
prealloc_array took 2729.999780654907 ms
prealloc_array took 3001.999855041504 ms
x[5] = None
y[5] = None
a[5] = None
b[5] = content
c[5] = some object blah
d[5] = some object 5
e[5] = a
f[5] = []
g[5] = ()

Wie Sie sehen können, dauert es nur sehr wenig, eine große Liste von Verweisen auf dasselbe None-Objekt zu erstellen.

Das Vorrücken oder Erweitern dauert länger (ich habe nichts gemittelt, aber nachdem ich dies einige Male ausgeführt habe, kann ich Ihnen sagen, dass das Erweitern und Anhängen ungefähr dieselbe Zeit dauert).

Zuweisen eines neuen Objekts für jedes Element - das dauert am meisten. Und die Antwort von S.Lott macht das - jedes Mal wird eine neue Zeichenfolge formatiert. Dies ist nicht unbedingt erforderlich. Wenn Sie Speicherplatz vorab zuweisen möchten, erstellen Sie einfach eine Liste mit "Keine" und weisen Sie den Listenelementen nach Belieben Daten zu. In beiden Fällen dauert das Generieren von Daten länger als das Anhängen / Erweitern einer Liste, unabhängig davon, ob Sie sie beim Erstellen der Liste oder danach generieren. Wenn Sie jedoch eine dünn besiedelte Liste wünschen, ist es definitiv schneller, mit einer Liste von None zu beginnen.

LRN
quelle
Hmm, interessant. Die Antwort lautet also: Es spielt keine Rolle, ob Sie eine Operation ausführen, um Elemente in eine Liste aufzunehmen, aber wenn Sie wirklich nur eine große Liste aller Elemente wünschen, sollten Sie den []*Ansatz verwenden
Claudiu
26

Der pythonische Weg dafür ist:

x = [None] * numElements

oder welchen Standardwert Sie vorab bearbeiten möchten, z

bottles = [Beer()] * 99
sea = [Fish()] * many
vegetarianPizzas = [None] * peopleOrderingPizzaNotQuiche

[EDIT: Caveat Emptor Die [Beer()] * 99Syntax erstellt eine Beer und füllt dann ein Array mit 99 Verweisen auf dieselbe einzelne Instanz.]

Der Standardansatz von Python kann ziemlich effizient sein, obwohl diese Effizienz abnimmt, wenn Sie die Anzahl der Elemente erhöhen.

Vergleichen Sie

import time

class Timer(object):
    def __enter__(self):
        self.start = time.time()
        return self

    def __exit__(self, *args):
        end = time.time()
        secs = end - self.start
        msecs = secs * 1000  # millisecs
        print('%fms' % msecs)

Elements   = 100000
Iterations = 144

print('Elements: %d, Iterations: %d' % (Elements, Iterations))


def doAppend():
    result = []
    i = 0
    while i < Elements:
        result.append(i)
        i += 1

def doAllocate():
    result = [None] * Elements
    i = 0
    while i < Elements:
        result[i] = i
        i += 1

def doGenerator():
    return list(i for i in range(Elements))


def test(name, fn):
    print("%s: " % name, end="")
    with Timer() as t:
        x = 0
        while x < Iterations:
            fn()
            x += 1


test('doAppend', doAppend)
test('doAllocate', doAllocate)
test('doGenerator', doGenerator)

mit

#include <vector>
typedef std::vector<unsigned int> Vec;

static const unsigned int Elements = 100000;
static const unsigned int Iterations = 144;

void doAppend()
{
    Vec v;
    for (unsigned int i = 0; i < Elements; ++i) {
        v.push_back(i);
    }
}

void doReserve()
{
    Vec v;
    v.reserve(Elements);
    for (unsigned int i = 0; i < Elements; ++i) {
        v.push_back(i);
    }
}

void doAllocate()
{
    Vec v;
    v.resize(Elements);
    for (unsigned int i = 0; i < Elements; ++i) {
        v[i] = i;
    }
}

#include <iostream>
#include <chrono>
using namespace std;

void test(const char* name, void(*fn)(void))
{
    cout << name << ": ";

    auto start = chrono::high_resolution_clock::now();
    for (unsigned int i = 0; i < Iterations; ++i) {
        fn();
    }
    auto end = chrono::high_resolution_clock::now();

    auto elapsed = end - start;
    cout << chrono::duration<double, milli>(elapsed).count() << "ms\n";
}

int main()
{
    cout << "Elements: " << Elements << ", Iterations: " << Iterations << '\n';

    test("doAppend", doAppend);
    test("doReserve", doReserve);
    test("doAllocate", doAllocate);
}

Auf meinem Windows 7 i7 gibt es 64-Bit-Python

Elements: 100000, Iterations: 144
doAppend: 3587.204933ms
doAllocate: 2701.154947ms
doGenerator: 1721.098185ms

Während C ++ bietet (erstellt mit MSVC, 64-Bit, Optimierungen aktiviert)

Elements: 100000, Iterations: 144
doAppend: 74.0042ms
doReserve: 27.0015ms
doAllocate: 5.0003ms

C ++ - Debugbuild erzeugt:

Elements: 100000, Iterations: 144
doAppend: 2166.12ms
doReserve: 2082.12ms
doAllocate: 273.016ms

Der Punkt hier ist, dass Sie mit Python eine Leistungsverbesserung von 7-8% erzielen können, und wenn Sie denken, dass Sie eine Hochleistungs-App schreiben (oder wenn Sie etwas schreiben, das in einem Webdienst oder etwas verwendet wird), dann Das ist nicht zu übersehen, aber Sie müssen möglicherweise Ihre Sprachwahl überdenken.

Außerdem ist der Python-Code hier nicht wirklich Python-Code. Wenn Sie hier zu wirklich pythoneskem Code wechseln, erhalten Sie eine bessere Leistung:

import time

class Timer(object):
    def __enter__(self):
        self.start = time.time()
        return self

    def __exit__(self, *args):
        end = time.time()
        secs = end - self.start
        msecs = secs * 1000  # millisecs
        print('%fms' % msecs)

Elements   = 100000
Iterations = 144

print('Elements: %d, Iterations: %d' % (Elements, Iterations))


def doAppend():
    for x in range(Iterations):
        result = []
        for i in range(Elements):
            result.append(i)

def doAllocate():
    for x in range(Iterations):
        result = [None] * Elements
        for i in range(Elements):
            result[i] = i

def doGenerator():
    for x in range(Iterations):
        result = list(i for i in range(Elements))


def test(name, fn):
    print("%s: " % name, end="")
    with Timer() as t:
        fn()


test('doAppend', doAppend)
test('doAllocate', doAllocate)
test('doGenerator', doGenerator)

Welches gibt

Elements: 100000, Iterations: 144
doAppend: 2153.122902ms
doAllocate: 1346.076965ms
doGenerator: 1614.092112ms

(In 32-Bit ist doGenerator besser als doAllocate).

Hier ist die Lücke zwischen doAppend und doAllocate deutlich größer.

Offensichtlich gelten die Unterschiede hier wirklich nur, wenn Sie dies mehr als ein paar Mal tun oder wenn Sie dies auf einem stark belasteten System tun, auf dem diese Zahlen um Größenordnungen skaliert werden, oder wenn Sie es zu tun haben erheblich größere Listen.

Der Punkt hier: Machen Sie es auf pythonische Weise für die beste Leistung.

Wenn Sie sich jedoch Sorgen um die allgemeine Leistung auf hohem Niveau machen, ist Python die falsche Sprache. Das grundlegendste Problem besteht darin, dass Python-Funktionsaufrufe aufgrund von Python-Funktionen wie Dekoratoren usw. ( https://wiki.python.org/moin/PythonSpeed/PerformanceTips#Data_Aggregation#Data_Aggregation ) traditionell bis zu 300-mal langsamer waren als andere Sprachen .

kfsone
quelle
@NilsvonBarth C ++ hat nichttimeit
kfsone
Python hat timeit, was Sie verwenden sollten, wenn Sie Ihren Python-Code zeitlich festlegen. Ich spreche natürlich nicht von C ++.
Nils von Barth
4
Dies ist keine richtige Antwort. bottles = [Beer()] * 99erstellt keine 99 Bierobjekte. Erstellt stattdessen ein Beer-Objekt mit 99 Verweisen darauf. Wenn Sie es mutieren würden, würden alle Elemente in der Liste mutiert, Ursache (bottles[i] is bootles[j]) == Truefür jedes i != j. 0<= i, j <= 99.
Erholo
@erhesto Sie haben die Antwort als nicht korrekt beurteilt, weil der Autor Referenzen als Beispiel verwendet hat, um eine Liste zu füllen? Erstens muss niemand 99 Beer-Objekte erstellen (im Vergleich zu einem Objekt und 99 Referenzen). Bei der Vorbevölkerung (worüber er sprach) ist schneller besser, da der Wert später ersetzt wird. Zweitens geht es bei der Antwort überhaupt nicht um Referenzen oder Mutationen. Ihnen fehlt das große Ganze.
Yongwei Wu
@YongweiWu Du hast Recht, eigentlich Recht. Dieses Beispiel macht die gesamte Antwort nicht falsch, es könnte nur irreführend sein und es ist einfach erwähnenswert.
Erholo
8

Wie andere bereits erwähnt haben, ist dies der einfachste Weg, eine Liste vorab zu erstellen NoneType Objekten erstellen.

Davon abgesehen sollten Sie verstehen, wie Python-Listen tatsächlich funktionieren, bevor Sie entscheiden, dass dies notwendig ist. Bei der CPython-Implementierung einer Liste wird das zugrunde liegende Array immer mit Overhead-Raum in zunehmend größeren Größen erstellt ( 4, 8, 16, 25, 35, 46, 58, 72, 88, 106, 126, 148, 173, 201, 233, 269, 309, 354, 405, 462, 526, 598, 679, 771, 874, 990, 1120, etc), sodass die Größe der Liste nicht so häufig geändert wird.

Aufgrund dieses Verhaltens sind die meisten list.append() Funktionen O(1)für Anhänge komplex und weisen nur dann eine erhöhte Komplexität auf, wenn eine dieser Grenzen überschritten wird. An diesem Punkt wird die Komplexität sein O(n). Dieses Verhalten führt zu einer minimalen Verlängerung der Ausführungszeit in S. Lotts Antwort.

Quelle: http://www.laurentluce.com/posts/python-list-implementation/

Russell Troxel
quelle
4

Ich habe den Code von @ s.lott ausgeführt und durch Vorabzuweisung die gleiche Leistungssteigerung von 10% erzielt. Ich habe @ jeremys Idee mit einem Generator ausprobiert und konnte die Leistung des Gens besser sehen als die des doAllocate. Für mein Projekt sind die 10% Verbesserung wichtig, also danke an alle, da dies einem Haufen hilft.

def doAppend( size=10000 ):
    result = []
    for i in range(size):
        message= "some unique object %d" % ( i, )
        result.append(message)
    return result

def doAllocate( size=10000 ):
    result=size*[None]
    for i in range(size):
        message= "some unique object %d" % ( i, )
        result[i]= message
    return result

def doGen( size=10000 ):
    return list("some unique object %d" % ( i, ) for i in xrange(size))

size=1000
@print_timing
def testAppend():
    for i in xrange(size):
        doAppend()

@print_timing
def testAlloc():
    for i in xrange(size):
        doAllocate()

@print_timing
def testGen():
    for i in xrange(size):
        doGen()


testAppend()
testAlloc()
testGen()

testAppend took 14440.000ms
testAlloc took 13580.000ms
testGen took 13430.000ms
Jason Wiener
quelle
5
"Für mein Projekt sind die 10% Verbesserung wichtig"? "Ja wirklich?" Sie können beweisen, dass die Listenzuordnung der Engpass ist? Ich würde gerne mehr darüber sehen. Haben Sie einen Blog, in dem Sie erklären können, wie dies tatsächlich geholfen hat?
S.Lott
2
@ S.Lott versuchen, die Größe um eine Größenordnung zu erhöhen; Die Leistung sinkt um 3 Größenordnungen (im Vergleich zu C ++, wo die Leistung um etwas mehr als eine Größenordnung sinkt).
KFSONE
2
Dies kann der Fall sein, da ein wachsendes Array möglicherweise im Speicher verschoben werden muss. (Denken Sie daran, wie Objekte dort nacheinander gespeichert werden.)
Evgeni Sergeev
3

Bedenken hinsichtlich der Vorbelegung in Python treten auf, wenn Sie mit numpy arbeiten, das mehr C-ähnliche Arrays enthält. In diesem Fall betreffen Bedenken hinsichtlich der Vorzuweisung die Form der Daten und den Standardwert.

Betrachten Sie Numpy, wenn Sie numerische Berechnungen für umfangreiche Listen durchführen und Leistung wünschen.

J450n
quelle
0

Für einige Anwendungen ist ein Wörterbuch möglicherweise das, wonach Sie suchen. In der Methode find_totient fand ich es beispielsweise bequemer, ein Wörterbuch zu verwenden, da ich keinen Nullindex hatte.

def totient(n):
    totient = 0

    if n == 1:
        totient = 1
    else:
        for i in range(1, n):
            if math.gcd(i, n) == 1:
                totient += 1
    return totient

def find_totients(max):
    totients = dict()
    for i in range(1,max+1):
        totients[i] = totient(i)

    print('Totients:')
    for i in range(1,max+1):
        print(i,totients[i])

Dieses Problem könnte auch mit einer vorab zugewiesenen Liste gelöst werden:

def find_totients(max):
    totients = None*(max+1)
    for i in range(1,max+1):
        totients[i] = totient(i)

    print('Totients:')
    for i in range(1,max+1):
        print(i,totients[i])

Ich bin der Meinung, dass dies nicht so elegant und fehleranfällig ist, weil ich None speichere, was eine Ausnahme auslösen könnte, wenn ich sie versehentlich falsch verwende, und weil ich über Randfälle nachdenken muss, die ich auf der Karte vermeiden kann.

Es ist wahr, dass das Wörterbuch nicht so effizient ist, aber wie andere kommentiert haben, sind kleine Geschwindigkeitsunterschiede nicht immer erhebliche Wartungsrisiken wert .

Josiah Yoder
quelle
-1

Soweit ich weiß, sind Python-Listen ArrayLists bereits ziemlich ähnlich. Aber wenn Sie diese Parameter optimieren möchten, fand ich diesen Beitrag im Internet, der interessant sein könnte (im Grunde erstellen Sie einfach Ihre eigene ScalableListErweiterung):

http://mail.python.org/pipermail/python-list/2000-May/035082.html

Piotr Lesnicki
quelle