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

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?

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.

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.

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.

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 .

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/

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

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.

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 .

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