Python - Utwórz listę o początkowej pojemności

Taki kod często się zdarza:

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

Jest to bardzo powolne, jeśli masz zamiar dodać tysiące elementów do listy, ponieważ lista będzie musiała być stale zmieniana, aby dopasować do nowych elementów.

W Javie możesz utworzyć ArrayList o początkowej pojemności. Jeśli masz pojęcie, jak duża będzie Twoja lista, będzie to o wiele bardziej wydajne.

Rozumiem, że taki kod często można przeformułować na listę. Jeśli pętla for / while jest bardzo skomplikowana, jest to niewykonalne. Czy jest jakiś odpowiednik dla nas programistów Python?

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

Wyniki . (oceniaj każdą funkcję 144 razy i średni czas trwania)

simple append 0.0102
pre-allocate  0.0098

Wnioski . To nie ma znaczenia.

Przedwczesna optymalizacja jest źródłem wszelkiego zła.

Listy w języku Python nie mają wbudowanej wstępnej alokacji. Jeśli naprawdę musisz utworzyć listę i uniknąć nakładania się na dołączanie (i powinieneś to zrobić), możesz to zrobić:

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

Być może możesz uniknąć listy, używając zamiast tego generatora:

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

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

W ten sposób lista nie zawsze jest przechowywana w całości w pamięci, a jedynie generowana w razie potrzeby.

Wersja skrócona: użyj

pre_allocated_list = [None] * size

aby wstępnie przydzielić listę (tzn. móc adresować elementy listy o rozmiarze zamiast stopniowo tworzyć listę przez dołączanie). Ta operacja jest BARDZO szybka, nawet na dużych listach. Przydzielanie nowych obiektów, które zostaną później przypisane do elementów listy, zajmie DUŻO więcej i będzie wąskim gardłem w twoim programie, pod względem wydajności.

Długa wersja:

Myślę, że należy wziąć pod uwagę czas inicjalizacji. Ponieważ w Pythonie wszystko jest referencją, nie ma znaczenia, czy ustawisz każdy element na None, czy jakiś ciąg znaków - w każdym razie jest to tylko referencja. Chociaż zajmie to więcej czasu, jeśli chcesz utworzyć nowy obiekt dla każdego elementu, do którego ma się odwoływać.

W przypadku 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()

Ocena:

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] = ()

Jak widać, utworzenie dużej listy odniesień do tego samego obiektu None zajmuje bardzo mało czasu.

Przygotowywanie lub przedłużanie trwa dłużej (nic nie oceniałem, ale po kilkukrotnym uruchomieniu mogę powiedzieć, że rozszerzanie i dodawanie zajmuje mniej więcej ten sam czas).

Przydzielanie nowego obiektu dla każdego elementu - to zajmuje najwięcej czasu. I odpowiedź S.Lott tak robi - za każdym razem formatuje nowy ciąg. Co nie jest bezwzględnie wymagane - jeśli chcesz wstępnie przydzielić trochę miejsca, po prostu utwórz listę Brak, a następnie przypisz dane do elementów listy do woli. Tak czy inaczej, generowanie danych zajmuje więcej czasu niż dodanie / rozszerzenie listy, niezależnie od tego, czy generujesz ją podczas tworzenia listy, czy później. Ale jeśli chcesz mieć słabo zaludnioną listę, rozpoczęcie od listy Brak jest zdecydowanie szybsze.

Pythonicznym sposobem na to jest:

x = [None] * numElements

lub jakąkolwiek wartością domyślną, którą chcesz zastosować, np

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

[Edycja: Zastrzeżenie strzeże[Beer()] * 99 składni tworzy jedną Beer , a następnie wypełnia się tablicę 99 odniesienia do tego samego pojedynczego przykład]

Domyślne podejście Pythona może być dość wydajne, chociaż wydajność maleje wraz ze wzrostem liczby elementów.

Porównać

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)

z

#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);
}

W moim systemie Windows 7 i7 64-bitowy Python daje

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

Podczas gdy C ++ daje (zbudowany z MSVC, 64-bit, włączone optymalizacje)

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

Kompilacja debugowania w C ++ daje:

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

Chodzi o to, że dzięki Python możesz osiągnąć 7-8% poprawę wydajności, a jeśli myślisz, że piszesz aplikację o wysokiej wydajności (lub jeśli piszesz coś, co jest używane w serwisie internetowym lub coś takiego), to nie można tego wąchać, ale może trzeba przemyśleć swój wybór języka.

Poza tym kod Pythona nie jest tak naprawdę kodem Pythona. Przejście na kod naprawdę Pythonesque zapewnia lepszą wydajność:

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)

Co daje

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

(w 32-bitowym programie doGenerator działa lepiej niż doAllocate).

Tutaj różnica między doAppend i doAllocate jest znacznie większa.

Oczywiście różnice tutaj obowiązują tylko wtedy, gdy robisz to więcej niż kilka razy lub jeśli robisz to w mocno obciążonym systemie, w którym liczby te zostaną skalowane o rzędy wielkości, lub jeśli masz do czynienia z znacznie większe listy.

Chodzi o to: zrób to pythonowy sposób, aby uzyskać najlepszą wydajność.

Ale jeśli martwisz się ogólną wydajnością na wysokim poziomie, Python jest niewłaściwym językiem. Najbardziej podstawowym problemem jest to, że wywołania funkcji Pythona tradycyjnie były do ​​300 razy wolniejsze niż w innych językach ze względu na funkcje Pythona, takie jak dekoratory itp. ( Https://wiki.python.org/moin/PythonSpeed/PerformanceTips#Data_Aggregation#Data_Aggregation ).

Jak wspomnieli inni, najprostszy sposób na wstępne zaszczepienie listy NoneTypeobiektami.

To powiedziawszy, powinieneś zrozumieć sposób, w jaki faktycznie działają listy Python, zanim zdecydujesz, że jest to konieczne. W implementacji listy CPython podstawowa tablica jest zawsze tworzona z wykorzystaniem przestrzeni nad głową, w stopniowo rosnących rozmiarach ( 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), tak że zmiana rozmiaru listy nie zdarza się prawie tak często.

Z powodu tego zachowania większość list.append() funkcji jest O(1)złożonością dopisów, posiadając tylko większą złożoność przy przekraczaniu jednej z tych granic, w którym to momencie złożoność będzie O(n). Takie zachowanie prowadzi do minimalnego wydłużenia czasu wykonania w odpowiedzi S. Lott.

Źródło: http://www.laurentluce.com/posts/python-list-implementation/

Uruchomiłem kod @ s.lott i wygenerowałem ten sam 10% wzrost perf przez wstępne przydzielenie. Wypróbowałem pomysł @ Jeremy'ego za pomocą generatora i byłem w stanie zobaczyć perf gen gen lepiej niż doAllocate. Dla mojego pro 10% poprawa ma znaczenie, więc dziękuję wszystkim, ponieważ pomaga to wielu.

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

Obawy dotyczące wstępnej alokacji w Pythonie powstają, jeśli pracujesz z Numpy, która ma więcej tablic podobnych do C. W tym przypadku obawy przed alokacją dotyczą kształtu danych i wartości domyślnej.

Rozważ numpy, jeśli wykonujesz obliczenia numeryczne na ogromnych listach i chcesz wydajności.

W przypadku niektórych aplikacji słownik może być tym, czego szukasz. Na przykład w metodzie find_totient wygodniej było używać słownika, ponieważ nie miałem indeksu zerowego.

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])

Ten problem można również rozwiązać za pomocą wstępnie przydzielonej listy:

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])

Wydaje mi się, że nie jest to tak eleganckie i podatne na błędy, ponieważ przechowuję Żadne, które mogłyby rzucić wyjątek, jeśli przypadkowo użyję ich źle, a także dlatego, że muszę pomyśleć o skrajnych przypadkach, których mapa pozwala mi uniknąć.

To prawda, że ​​słownik nie będzie tak wydajny, ale jak zauważyli inni, niewielkie różnice w prędkości nie zawsze są warte znacznych zagrożeń związanych z konserwacją.

Z tego, co rozumiem, listy python są już dość podobne do ArrayLists. Ale jeśli chcesz poprawić te parametry, znalazłem ten post w sieci, który może być interesujący (po prostu stwórz własne ScalableListrozszerzenie):

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