barplot - Python: crea una lista con capacidad inicial

pandas plot

Question

Código como este a menudo sucede:

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

Esto es realmente lento si está a punto de agregar miles de elementos a su lista, ya que la lista tendrá que cambiarse de tamaño constantemente para adaptarse a los nuevos elementos.

En Java, puede crear una ArrayList con una capacidad inicial. Si tiene alguna idea de lo grande que será su lista, esto será mucho más eficiente.

Entiendo que el código de este tipo a menudo se puede volver a factorizar en una lista de comprensión. Si el ciclo for / while es muy complicado, sin embargo, esto es inviable. ¿Hay algún equivalente para nosotros los programadores de Python?

Answer 1

Como otros han mencionado, la forma más simple de pre-sembrar una lista con objetos NoneType .

Una vez dicho esto, debes comprender la forma en que funcionan realmente las listas de Python antes de decidir si es necesario. En la implementación de CPython de una lista, la matriz subyacente siempre se crea con una habitación superior, en tamaños progresivamente más 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) , por lo que el cambio de tamaño de la lista no ocurre con tanta frecuencia.

Debido a este comportamiento, la mayoría de las funciones list.append() son O(1) complejidad para los anexos, solo que tienen una mayor complejidad al cruzar uno de estos límites, en cuyo punto la complejidad será O(n) . Este comportamiento es lo que conduce al aumento mínimo del tiempo de ejecución en la respuesta de S. Lott.

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

Answer 2

Ejecuté el código de @ s.lott y obtuve el mismo 10% de aumento de rendimiento mediante la asignación previa. probé la idea de @ jeremy usando un generador y pude ver el rendimiento del gen mejor que el de doAllocate. Para mi proyecto, la mejora del 10% importa, así que gracias a todos, ya que ayuda un montón.

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

Answer 3

La manera Pythonic para esto es:

x = [None] * numElements

o el valor por defecto que prefiera, por ejemplo,

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

El enfoque predeterminado de Python puede ser bastante eficiente, aunque esa eficacia disminuye a medida que aumenta la cantidad 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)

con

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

En mi Windows 7 i7, Python de 64 bits da

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

Mientras que C ++ da (construido con MSVC, optimizaciones de 64 bits habilitadas)

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

La creación de errores de C ++ produce:

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

El punto aquí es que con Python puede lograr una mejora del rendimiento del 7-8%, y si cree que está escribiendo una aplicación de alto rendimiento (o si está escribiendo algo que se usa en un servicio web o algo así), entonces eso no debe ser olido, pero es posible que deba replantearse su elección de idioma.

Además, el código de Python aquí no es realmente el código de Python. El cambio a un código realmente pitón aquí brinda un mejor rendimiento:

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)

Lo que da

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

(En doGenerator de 32 bits es mejor que doAlocate).

Aquí la brecha entre doAppend y doAllocate es significativamente mayor.

Obviamente, las diferencias aquí solo se aplican si lo hace más de una vez o si lo hace en un sistema muy cargado en el que los números se ampliarán por órdenes de magnitud, o si está tratando con listas considerablemente más grandes.

El punto aquí: hazlo de manera pitonica para obtener el mejor rendimiento.

Pero si te preocupa el rendimiento general de alto nivel, Python es el idioma equivocado. El problema más fundamental es que las llamadas a función de Python han sido tradicionalmente hasta 300 veces más lentas que otros lenguajes debido a las características de Python como decoradores, etc. ( https://wiki.python.org/moin/PythonSpeed/PerformanceTips#Data_Aggregation#Data_Aggregation ).

Answer 4

Las listas de Python no tienen una preasignación incorporada. Si realmente necesita hacer una lista, y necesita evitar la sobrecarga de agregar (y debe verificar que lo haga), puede hacer esto:

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

Quizás podrías evitar la lista usando un generador:

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

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

De esta forma, la lista no está almacenada en absoluto en la memoria, simplemente se genera según sea necesario.

Answer 5

Las preocupaciones sobre la preasignación en Python surgen si estás trabajando con numpy, que tiene más matrices en forma de C. En este caso, las preocupaciones previas a la asignación se refieren a la forma de los datos y el valor predeterminado.

Considera numpy si estás haciendo cálculos numéricos en listas masivas y quieres rendimiento.

Answer 6

Para algunas aplicaciones, un diccionario puede ser lo que estás buscando. Por ejemplo, en el método find_totient, me pareció más conveniente usar un diccionario ya que no tenía un índice cero.

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

Este problema también podría resolverse con una lista preasignada:

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

Siento que esto no es tan elegante y propenso a los errores porque estoy almacenando Ninguno, que podría arrojar una excepción si accidentalmente los uso mal, y porque necesito pensar en casos límite que el mapa me permite evitar.

Es cierto que el diccionario no será tan eficiente, pero como otros han comentado, las pequeñas diferencias en la velocidad no siempre merecen riesgos significativos de mantenimiento.

Answer 7

Por lo que entiendo, las listas de Python ya son bastante similares a ArrayLists. Pero si quieres ajustar esos parámetros, encontré esta publicación en la red que puede ser interesante (básicamente, simplemente crea tu propia extensión ScalableList ):

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

Answer 8

Versión corta: uso

pre_allocated_list = [None] * size

para preasignar una lista (es decir, para poder abordar los elementos de ''tamaño'' de la lista en lugar de formar gradualmente la lista al agregar). Esta operación es MUY rápida, incluso en listas grandes. La asignación de nuevos objetos que luego se asignarán a los elementos de la lista tomará MUCHO más tiempo y será EL cuello de botella en su programa, en cuanto al rendimiento.

Versión larga:

Creo que el tiempo de inicialización debe tenerse en cuenta. Como en python todo es una referencia, no importa si configuras cada elemento en None o en alguna cadena, de cualquier forma es solo una referencia. Aunque tomará más tiempo si desea crear un nuevo objeto para cada elemento de referencia.

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

Evaluación:

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 puede ver, solo hacer una gran lista de referencias al mismo objeto None toma muy poco tiempo.

El preaspleo o el alargamiento demoran más (no promedié nada, pero después de ejecutar esto algunas veces puedo decirte que extender y anexar dura aproximadamente el mismo tiempo).

Asignar un nuevo objeto para cada elemento: eso es lo que más tiempo lleva. Y la respuesta de S.Lott lo hace: formatea una nueva cadena cada vez. Lo cual no es estrictamente necesario: si desea asignar previamente espacio, simplemente haga una lista de Ninguno, luego asigne datos a los elementos de la lista a voluntad. De cualquier forma, toma más tiempo generar datos que agregar / ampliar una lista, ya sea que la genere al crear la lista o después de eso. Pero si quieres una lista escasamente poblada, comenzar con una lista de None es definitivamente más rápido.

Answer 9

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 . (evalúa cada función 144 veces y promedia la duración)

simple append 0.0102
pre-allocate  0.0098

Conclusion Apenas importa.

La optimización prematura es la fuente de todos los males.