Python - Crie uma lista com capacidade inicial

Código como esse geralmente acontece:

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

Isso é muito lento se você estiver prestes a anexar milhares de elementos à sua lista, pois a lista precisará ser constantemente redimensionada para se ajustar aos novos elementos.

Em Java, você pode criar um ArrayList com uma capacidade inicial. Se você tem alguma idéia de quão grande será sua lista, isso será muito mais eficiente.

Entendo que códigos como esse geralmente podem ser redefinidos em uma compreensão de lista. Se o loop for / while for muito complicado, isso é inviável. Existe algum equivalente para nós programadores 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

Resultados . (avalie cada função 144 vezes e calcule a média da duração)

simple append 0.0102
pre-allocate  0.0098

Conclusão . Isso quase não importa.

Otimização prematura é a raiz de todo o mal.

As listas Python não têm pré-alocação embutida. Se você realmente precisa fazer uma lista e evitar a sobrecarga de anexar (e deve verificar se o faz), faça o seguinte:

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

Talvez você possa evitar a lista usando um gerador:

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

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

Dessa forma, a lista nem todos são armazenados na memória, apenas gerados conforme necessário.

Versão curta: use

pre_allocated_list = [None] * size

pré-alocar uma lista (ou seja, poder endereçar elementos de 'tamanho' da lista em vez de gradualmente formar a lista anexando). Esta operação é MUITO rápida, mesmo em grandes listas. A alocação de novos objetos que serão atribuídos posteriormente aos elementos da lista levará MUITO mais tempo e será o gargalo no seu programa, em termos de desempenho.

Versão longa:

Eu acho que o tempo de inicialização deve ser levado em consideração. Como no python tudo é uma referência, não importa se você define cada elemento como None ou alguma string - de qualquer forma, é apenas uma referência. Embora demore mais tempo, se você deseja criar um novo objeto para cada elemento a ser referenciado.

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

Avaliação:

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

Como você pode ver, apenas fazer uma grande lista de referências ao mesmo objeto None leva muito pouco tempo.

Anexar ou estender leva mais tempo (não calculei a média de nada, mas depois de executar isso algumas vezes, posso dizer que estender e anexar levam aproximadamente o mesmo tempo).

Alocar novo objeto para cada elemento - é isso que leva mais tempo. E a resposta de S.Lott faz isso - formata uma nova string sempre. O que não é estritamente necessário - se você quiser pré-alocar algum espaço, faça uma lista de Nenhum e atribua dados aos elementos da lista à vontade. De qualquer maneira, leva mais tempo para gerar dados do que anexar / estender uma lista, seja você gerada durante a criação da lista ou depois disso. Mas se você deseja uma lista pouco povoada, começar com uma lista de Nenhum é definitivamente mais rápido.

O caminho pitônico para isso é:

x = [None] * numElements

ou qualquer valor padrão com o qual você deseja pré-pop-up, por exemplo

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

[EDIT: Caveat Emptor A [Beer()] * 99sintaxe cria uma Beer e preenche uma matriz com 99 referências à mesma instância única]

A abordagem padrão do Python pode ser bastante eficiente, embora essa eficiência decaia à medida que você aumenta o número de elementos.

Comparar

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)

com

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

No meu Windows 7 i7, o Python de 64 bits oferece

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

Enquanto o C ++ fornece (construído com MSVC, 64 bits, otimizações ativadas)

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

A compilação de depuração do C ++ produz:

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

O ponto aqui é que, com o Python, você pode obter uma melhoria de desempenho de 7 a 8%; se você acha que está escrevendo um aplicativo de alto desempenho (ou se está escrevendo algo que é usado em um serviço da Web ou algo assim), então isso não deve ser desprezado, mas pode ser necessário repensar sua escolha de idioma.

Além disso, o código Python aqui não é realmente um código Python. Mudar para o código verdadeiramente Pythonesque aqui oferece melhor desempenho:

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)

Que dá

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

(no doGenerator de 32 bits é melhor que doAllAllate).

Aqui, a diferença entre doAppend e doAllocate é significativamente maior.

Obviamente, as diferenças aqui realmente se aplicam apenas se você estiver fazendo isso mais do que algumas vezes ou se estiver fazendo isso em um sistema muito carregado, em que esses números serão redimensionados por ordens de magnitude ou se você estiver lidando com listas consideravelmente maiores.

O ponto aqui: faça da maneira pitônica o melhor desempenho.

Mas se você está preocupado com o desempenho geral de alto nível, o Python é a linguagem errada. O problema mais fundamental é que as chamadas de função do Python tradicionalmente são até 300 vezes mais lentas que outras linguagens devido a recursos do Python, como decoradores etc. ( https://wiki.python.org/moin/PythonSpeed/PerformanceTips#Data_Aggregation#Data_Aggregation ).

Como outros mencionaram, a maneira mais simples de pré-propagar uma lista com NoneTypeobjetos.

Dito isto, você deve entender como as listas Python realmente funcionam antes de decidir que isso é necessário. Na implementação de uma lista do CPython, a matriz subjacente é sempre criada com espaço para sobrecarga, em tamanhos progressivamente maiores ( 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), para que o redimensionamento da lista não ocorra com tanta frequência.

Devido a esse comportamento, a maioria das list.append() funções é de O(1)complexidade para anexos, tendo apenas uma complexidade aumentada ao cruzar um desses limites, momento em que a complexidade será O(n). Esse comportamento é o que leva ao aumento mínimo no tempo de execução na resposta de S. Lott.

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

Corri o código do @ s.lott e produzi o mesmo aumento de 10% no perf pré-alocando. tentou a idéia de @ jeremy usando um gerador e foi capaz de ver o desempenho do gen melhor do que o do doAllocate. Para o meu projeto, a melhoria de 10% é importante, portanto, obrigado a todos, pois isso ajuda bastante.

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

As preocupações com a pré-alocação no Python surgem se você estiver trabalhando com o numpy, que possui mais matrizes do tipo C. Nesse caso, as preocupações de pré-alocação são sobre a forma dos dados e o valor padrão.

Considere entorpecido se estiver fazendo cálculos numéricos em listas massivas e desejar desempenho.

Para alguns aplicativos, um dicionário pode ser o que você está procurando. Por exemplo, no método find_totient, achei mais conveniente usar um dicionário, pois não tinha um índice zero.

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

Esse problema também pode ser resolvido com uma lista pré-alocada:

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

Sinto que isso não é tão elegante e propenso a erros, porque estou armazenando o None, o que poderia gerar uma exceção se eu acidentalmente os usar incorretamente e porque preciso pensar em casos extremos que o mapa me permita evitar.

É verdade que o dicionário não será tão eficiente, mas como outros comentaram, pequenas diferenças de velocidade nem sempre valem riscos significativos de manutenção.

Pelo que entendi, as listas python já são bastante semelhantes às ArrayLists. Mas se você quiser ajustar esses parâmetros, achei este post na rede que pode ser interessante (basicamente, basta criar sua própria ScalableListextensão):

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