Pre-asignación de una lista de Ninguno

Supongamos que desea escribir una función que produzca una lista de objetos y conozca anticipadamente la longitud n de dicha lista.

En Python, la lista admite el acceso indexado en O (1), por lo que es una buena idea pre-asignar la lista y acceder a ella con índices en lugar de asignar una lista vacía y usar el método append() . Esto se debe a que evitamos la carga de expandir la lista completa si el espacio no es suficiente.

Si estoy usando python, es probable que las interpretaciones no sean tan relevantes en cualquier caso, pero ¿cuál es la mejor manera de preasignar una lista?

Conozco a estos posibles candidatos:

  • [None] * n → asignando dos listas
  • [None for x in range(n)] – o xrange en python2 → construyendo otro objeto

¿Es uno significativamente mejor que el otro?

¿Qué pasa si estamos en el caso n = len(input) ? Dado que la input ya existe, ¿tendría [None for x in input] mejores rendimientos wrt [None] * len(input) ?

Entre esas dos opciones, la primera es claramente mejor, ya que no hay Python for loop involucrado.

 >>> %timeit [None] * 100 1000000 loops, best of 3: 469 ns per loop >>> %timeit [None for x in range(100)] 100000 loops, best of 3: 4.8 us per loop 

Actualizar:

Y list.append tiene una complejidad O(1) , podría ser una mejor opción que crear una lista previa si asigna el método list.append a una variable.

 >>> n = 10**3 >>> %%timeit lis = [None]*n for _ in range(n): lis[_] = _ ... 10000 loops, best of 3: 73.2 us per loop >>> %%timeit lis = [] for _ in range(n): lis.append(_) ... 10000 loops, best of 3: 92.2 us per loop >>> %%timeit lis = [];app = lis.append for _ in range(n): app(_) ... 10000 loops, best of 3: 59.4 us per loop >>> n = 10**6 >>> %%timeit lis = [None]*n for _ in range(n): lis[_] = _ ... 10 loops, best of 3: 106 ms per loop >>> %%timeit lis = [] for _ in range(n): lis.append(_) ... 10 loops, best of 3: 122 ms per loop >>> %%timeit lis = [];app = lis.append for _ in range(n): app(_) ... 10 loops, best of 3: 91.8 ms per loop 

Cuando agrega un elemento a una lista, Python ‘sobre-asigna’, vea el código fuente del objeto de la lista. Esto significa que, por ejemplo, al agregar 1 elemento a una lista de 8 elementos, en realidad deja espacio para 8 elementos nuevos y utiliza solo el primero de ellos. Los siguientes 7 apéndices son entonces ‘gratis’.

En muchos idiomas (por ejemplo, Matlab) siempre se le dice que necesita asignar previamente sus vectores, ya que agregarlos durante un ciclo es muy costoso. En el peor de los casos, agregar un solo elemento a una lista de longitud n puede costar O(n) tiempo, ya que es posible que tenga que crear una lista más grande y copiar todos los elementos existentes. Debe hacer esto en cada iteración, por lo que el costo general de agregar n artículos es O(n^2) , ouch. El esquema de asignación previa de Python distribuye el costo de hacer crecer la matriz en muchos apéndices individuales (ver costos amortizados ), haciendo que el costo de un apéndice único O(1) y el costo total de agregar n artículos O(n) sean efectivos.

En Python, la sobrecarga del rest de su código suele ser tan grande, que la pequeña aceleración que puede obtenerse mediante la asignación previa es insignificante. Por lo tanto, en la mayoría de los casos, simplemente olvídese de la asignación previa, a menos que su generador de perfiles le indique que agregarse a una lista es un cuello de botella.

Las otras respuestas muestran algunos perfiles de la lista de preasignaciones en sí, pero esto es inútil. Lo único que importa es perfilar su código completo, con todos sus cálculos dentro de su bucle, con y sin asignación previa. Si mi predicción es correcta, la diferencia es tan pequeña que el tiempo de cómputo que gana se ve empañado por el tiempo dedicado a pensar, escribir y mantener las líneas adicionales para preasignar su lista.

Obviamente, la primera versión. Déjame explicarte por qué.

  1. Cuando haces [None] * n , Python crea internamente una lista de objetos de tamaño n y copia el mismo objeto (aquí None ) ( esta es la razón, debes usar este método solo cuando estés tratando con objetos inmutables ) para Todas las ubicaciones de memoria. Así que la asignación de memoria se realiza una sola vez. Después de eso, una única iteración a través de la lista para copiar el objeto a todos los elementos. list_repeat es la función que corresponde a este tipo de creación de lista.

     # Creates the list of specified size np = (PyListObject *) PyList_New(size); .... ... items = np->ob_item; if (Py_SIZE(a) == 1) { elem = a->ob_item[0]; for (i = 0; i < n; i++) { items[i] = elem; // Copies the same item Py_INCREF(elem); } return (PyObject *) np; } 
  2. Cuando utiliza una comprensión de lista para crear una lista, Python no puede saber el tamaño real de la lista que se está creando, por lo que inicialmente asigna una porción de memoria y una copia nueva del objeto se almacena en la lista. Cuando la lista crece más allá de la longitud asignada, tiene que volver a asignar la memoria y continuar con la creación del nuevo objeto y almacenarlo en la lista.