webentwicklung-frage-antwort-db.com.de

Python - Erstelle eine Liste mit anfänglicher Kapazität

Code wie dieser kommt häufig vor:

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 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 wesentlich effizienter.

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

175
Claudiu
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. (bewerte jede Funktion 144 mal und mittle die Dauer)

simple append 0.0102
pre-allocate  0.0098

Fazit. Es spielt kaum eine Rolle.

Vorzeitige Optimierung ist die Wurzel allen Übels.

119
S.Lott

Python-Listen haben keine eingebaute Vorbelegung. Wenn Sie wirklich eine Liste erstellen und den Aufwand für das Anhängen vermeiden müssen (und dies überprüfen sollten), können Sie dies 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 umgehen, 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 die Liste nicht vollständig gespeichert, sondern nur nach Bedarf erstellt.

73
Ned Batchelder

Kurzversion: verwenden

pre_allocated_list = [None] * size

zuweisen einer Liste im Voraus (d. h. Adressieren von Größenelementen der Liste, anstatt die Liste schrittweise durch Anhängen zu erstellen). Diese Operation ist SEHR schnell, selbst bei 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 ein Verweis ist, spielt es keine Rolle, ob Sie jedes Element in "None" oder in einen String setzen - in beiden Fällen handelt es sich nur um einen Verweis. Es dauert jedoch länger, wenn Sie einen Verweis erstellen möchten Neues Objekt für jedes zu referenzierende Element.

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 __== '__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, dauert es nur sehr kurz, eine große Liste von Verweisen auf dasselbe None-Objekt zu erstellen.

Das Vorbereiten 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 das Anhängen ungefähr die gleiche Zeit dauern).

Jedem Element ein neues Objekt zuweisen - das ist der Punkt, der am meisten Zeit in Anspruch nimmt. Und die Antwort von S.Lott geht so: Jedes Mal wird eine neue Zeichenfolge formatiert. Dies ist nicht unbedingt erforderlich. Wenn Sie vorab Speicherplatz zuweisen möchten, erstellen Sie einfach eine Liste mit "Keine" und ordnen Sie die Daten den Listenelementen nach Belieben 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 der Liste None zu beginnen.

45
LRN

Der pythonische Weg dafür ist:

x = [None] * numElements

oder einen beliebigen Standardwert, den Sie vorab einfügen möchten, z.

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

[EDIT: Caveat Emptor Die [Beer()] * 99 -Syntax erzeugt eine Beer und füllt dann ein Array mit 99 Referenzen 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 64-Bit Python

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

Während C++ gibt (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 glauben, dass Sie eine Hochleistungs-App schreiben (oder wenn Sie etwas schreiben, das ist verwendet in einem Web-Service oder etwas), dann ist das nicht zu riechen, aber Sie müssen möglicherweise Ihre Wahl der Sprache überdenken.

Außerdem ist der Python Code hier nicht wirklich Python Code. Wenn Sie hier auf echten Pythonesque-Code umschalten, 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-Version ist doGenerator besser als doAllocate).

Hier ist der Abstand zwischen doAppend und doAllocate deutlich größer.

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

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

Wenn Sie sich jedoch über die allgemeine Leistung auf hoher Ebene Gedanken machen, ist Python die falsche Sprache. Das grundlegendste Problem ist, dass Python Funktionsaufrufe traditionell nur bis zu 300x langsamer als andere Sprachen aufgrund von Python Funktionen wie Dekoratoren usw. ( https://wiki.python.org/moin/PythonSpeed/PerformanceTips#Data_Aggregation#Data_Aggregation ).

22
kfsone

Wie bereits erwähnt, ist dies der einfachste Weg, eine Liste mit NoneType Objekten vorzubereiten.

Allerdings sollten Sie wissen, wie Python -Listen tatsächlich funktionieren, bevor Sie entscheiden, dass dies erforderlich ist. In der CPython-Implementierung einer Liste wird das zugrunde liegende Array immer mit Overhead-Speicher erstellt, und zwar in progressiv größeren Formaten ( 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), So dass das Ändern der Listengröße seltener vorkommt.

Aufgrund dieses Verhaltens sind die meisten list.append() Funktionen O(1) Komplexität für Anhänge, nur mit erhöhter Komplexität beim Überqueren eine dieser Grenzen, an welcher Stelle die Komplexität O(n) sein wird. Dieses Verhalten führt zu einer minimalen Verlängerung der Ausführungszeit in der Antwort von S. Lott.

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

8
Russell Troxel

ich habe @ s.lotts Code ausgeführt und durch Vorab-Zuweisung die gleiche Leistungssteigerung von 10% erzielt. Ich habe @ Jeremy's Idee mit einem Generator ausprobiert und konnte die Perfektion des Gens besser erkennen als die des doAllocate. Für mein Projekt sind die 10% Verbesserung wichtig, also danke an alle, da dies ein 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
4
Jason Wiener

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

Betrachten Sie numpy, wenn Sie numerische Berechnungen auf umfangreichen Listen durchführen und Leistung wünschen.

3
J450n

Für einige Anwendungen ist ein Wörterbuch möglicherweise das, wonach Sie suchen. Zum Beispiel fand ich es in der find_totient-Methode 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 keine speichere, die eine Ausnahme auslösen könnten, wenn ich sie versehentlich falsch verwende, und weil ich über Edge-Fälle nachdenken muss, die ich mit 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 wert bedeutende Wartungsrisiken.

0
Josiah Yoder