Python - Créer une liste avec une capacité initiale

Un code comme celui-ci arrive souvent:

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

C'est vraiment lent si vous êtes sur le point d'ajouter des milliers d'éléments à votre liste, car la liste devra être constamment redimensionnée pour s'adapter aux nouveaux éléments.

En Java, vous pouvez créer une ArrayList avec une capacité initiale. Si vous avez une idée de la taille de votre liste, ce sera beaucoup plus efficace.

Je comprends qu'un code comme celui-ci peut souvent être re-factorisé dans une compréhension de liste. Si la boucle for / while est très compliquée, cependant, c'est irréalisable. Y a-t-il un équivalent pour nous, programmeurs 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

Résultats . (évaluer chaque fonction 144 fois et faire la moyenne de la durée)

simple append 0.0102
pre-allocate  0.0098

Conclusion . Cela n'a guère d'importance.

L'optimisation prématurée est la racine de tout Mal.

Les listes Python n'ont pas de pré-allocation intégrée. Si vous avez vraiment besoin de faire une liste et que vous devez éviter la surcharge de l'ajout (et vous devez vérifier que c'est le cas), vous pouvez le faire:

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

Vous pourriez peut-être éviter la liste en utilisant un générateur à la place:

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

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

De cette façon, la liste n'est pas du tout stockée en mémoire, elle est simplement générée au besoin.

Version courte: utilisation

pre_allocated_list = [None] * size

pour pré-allouer une liste (c'est-à-dire pour pouvoir adresser des éléments de «taille» de la liste au lieu de former progressivement la liste en ajoutant). Cette opération est TRES rapide, même sur de grandes listes. L'allocation de nouveaux objets qui seront ultérieurement affectés à des éléments de liste prendra BEAUCOUP plus de temps et sera LE goulot d'étranglement de votre programme, en termes de performances.

Version longue:

Je pense que le temps d'initialisation doit être pris en compte. Comme en python, tout est une référence, peu importe que vous définissiez chaque élément sur None ou sur une chaîne - de toute façon, ce n'est qu'une référence. Cependant, cela prendra plus de temps si vous souhaitez créer un nouvel objet pour chaque élément à référencer.

Pour 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()

Évaluation:

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

Comme vous pouvez le voir, créer une grande liste de références au même objet None prend très peu de temps.

La prépension ou l'extension prend plus de temps (je n'ai rien fait en moyenne, mais après l'avoir exécuté plusieurs fois, je peux vous dire que l'extension et l'ajout prennent à peu près le même temps).

Allouer un nouvel objet à chaque élément - c'est ce qui prend le plus de temps. Et la réponse de S.Lott fait cela - formate une nouvelle chaîne à chaque fois. Ce qui n'est pas strictement obligatoire - si vous souhaitez pré-allouer de l'espace, créez simplement une liste de Aucun, puis attribuez des données aux éléments de la liste à volonté. Dans tous les cas, il faut plus de temps pour générer des données que pour ajouter / étendre une liste, que vous la génériez lors de la création de la liste ou après cela. Mais si vous voulez une liste peu peuplée, commencer par une liste de Aucun est certainement plus rapide.

La manière pythonique pour cela est:

x = [None] * numElements

ou quelle que soit la valeur par défaut avec laquelle vous souhaitez pré-remplir, par exemple

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

[EDIT: Caveat Emptor La [Beer()] * 99syntaxe en crée un Beer , puis remplit un tableau avec 99 références à la même instance]

L'approche par défaut de Python peut être assez efficace, bien que cette efficacité diminue à mesure que vous augmentez le nombre d'éléments.

Comparer

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)

avec

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

Sur mon Windows 7 i7, Python 64 bits donne

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

Alors que C ++ donne (construit avec MSVC, 64 bits, optimisations activées)

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

La génération de débogage C ++ produit:

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

Le point ici est qu'avec Python, vous pouvez obtenir une amélioration des performances de 7 à 8%, et si vous pensez que vous écrivez une application haute performance (ou si vous écrivez quelque chose qui est utilisé dans un service Web ou autre), alors ce n'est pas à renifler, mais vous devrez peut-être repenser votre choix de langue.

De plus, le code Python ici n'est pas vraiment du code Python. Le passage au code vraiment Pythonesque donne ici de meilleures performances:

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)

Qui donne

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

(en 32 bits, doGenerator fait mieux que doAllocate).

Ici, l'écart entre doAppend et doAllocate est nettement plus grand.

De toute évidence, les différences ici ne s'appliquent vraiment que si vous faites cela plus d'une poignée de fois ou si vous le faites sur un système très chargé où ces nombres vont être réduits par ordre de grandeur, ou si vous avez affaire à listes considérablement plus grandes.

Le point ici: faites-le de manière pythonique pour la meilleure performance.

Mais si vous vous inquiétez des performances générales de haut niveau, Python n'est pas le bon langage. Le problème le plus fondamental est que les appels de fonction Python ont traditionnellement été jusqu'à 300 fois plus lents que les autres langages en raison des fonctionnalités Python telles que les décorateurs, etc. ( https://wiki.python.org/moin/PythonSpeed/PerformanceTips#Data_Aggregation#Data_Aggregation ).

Comme d'autres l'ont mentionné, le moyen le plus simple de pré-amorcer une liste avec NoneType objets.

Cela étant dit, vous devez comprendre le fonctionnement réel des listes Python avant de décider que cela est nécessaire. Dans l'implémentation CPython d'une liste, le tableau sous-jacent est toujours créé avec une surcharge, dans des tailles de plus en plus grandes ( 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), de sorte que le redimensionnement de la liste ne se produit pas aussi souvent.

En raison de ce comportement, la plupart des list.append() fonctions sont O(1)complexes pour les appendices, ayant seulement une complexité accrue lors du franchissement d'une de ces limites, à quel point la complexité sera O(n). Ce comportement est ce qui conduit à l'augmentation minimale du temps d'exécution dans la réponse de S. Lott.

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

J'ai exécuté le code de @ s.lott et produit la même augmentation de 10% des performances en pré-allouant. a essayé l'idée de @ jeremy en utilisant un générateur et a pu voir la performance de la génération mieux que celle du doAllocate. Pour mon projet, l'amélioration de 10% compte, alors merci à tout le monde car cela aide beaucoup.

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

Des problèmes de pré-allocation en Python surviennent si vous travaillez avec numpy, qui a plus de tableaux de type C. Dans ce cas, les problèmes de pré-allocation concernent la forme des données et la valeur par défaut.

Considérez numpy si vous effectuez des calculs numériques sur des listes massives et que vous voulez des performances.

Pour certaines applications, un dictionnaire peut être ce que vous recherchez. Par exemple, dans la méthode find_totient, j'ai trouvé plus pratique d'utiliser un dictionnaire car je n'avais pas d'index zéro.

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

Ce problème pourrait également être résolu avec une liste préallouée:

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

Je pense que ce n'est pas aussi élégant et sujet aux bugs parce que je stocke None qui pourrait lever une exception si je les utilise accidentellement de manière incorrecte, et parce que j'ai besoin de penser aux cas limites que la carte me permet d'éviter.

Il est vrai que le dictionnaire ne sera pas aussi efficace, mais comme d'autres l'ont commenté, de petites différences de vitesse ne valent pas toujours des risques de maintenance importants .

D'après ce que je comprends, les listes Python sont déjà assez similaires aux ArrayLists. Mais si vous voulez modifier ces paramètres, j'ai trouvé cet article sur le net qui peut être intéressant (en gros, créez simplement votre propre ScalableListextension):

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