¿Cómo antepongo a una breve lista de Python?
list.append()se añade al final de una lista. Esto explica que list.prepend()no existe debido a problemas de rendimiento para listas grandes. Para obtener una lista breve, ¿cómo antepongo un valor?
La s.insert(0, x)forma es la más común.
Sin embargo, siempre que lo vea, puede que sea el momento de considerar el uso de collections.deque en lugar de una lista. Anteponer a un deque se ejecuta en tiempo constante. Anteponer a una lista se ejecuta en tiempo lineal.
Esto crea una nueva lista con xel prefijo, en lugar de modificar una lista existente:
new_list = [x] + old_list
¿Cuál es la sintaxis idiomática para anteponer una lista corta de Python?
Por lo general, no desea anteponer repetidamente una lista en Python.
Si la lista es corta y no lo haces mucho... entonces está bien.
list.insert
Se list.insertpuede utilizar de esta manera.
list.insert(0, x)
Pero esto es ineficiente, porque en Python, a listes una matriz de punteros, y Python ahora debe tomar cada puntero en la lista y moverlo hacia abajo en uno para insertar el puntero a su objeto en la primera ranura, por lo que esto en realidad solo es eficiente. para listas bastante cortas, como usted pregunta.
Aquí hay un fragmento de la fuente de CPython donde esto se implementa y, como puede ver, comenzamos al final de la matriz y bajamos todo uno por cada inserción:
for (i = n; --i >= where; )
items[i+1] = items[i];
Si desea un contenedor/lista que sea eficiente para anteponer elementos, desea una lista vinculada. Python tiene una lista doblemente enlazada, que se puede insertar al principio y al final rápidamente; se llama deque.
deque.appendleft
A collections.dequetiene muchos de los métodos de una lista. list.sortes una excepción, lo que hace que dequeLiskov definitivamente no sea completamente sustituible por list.
>>> set(dir(list)) - set(dir(deque))
{'sort'}
El dequetambién tiene un appendleftmétodo (así como popleft). Es dequeuna cola de dos extremos y una lista doblemente vinculada: no importa la longitud, siempre lleva la misma cantidad de tiempo preparar algo. En notación O grande, tiempo O(1) versus O(n) para listas. Aquí está el uso:
>>> import collections
>>> d = collections.deque('1234')
>>> d
deque(['1', '2', '3', '4'])
>>> d.appendleft('0')
>>> d
deque(['0', '1', '2', '3', '4'])
deque.extendleft
También es relevante el método deque extendleft, que antepone iterativamente:
>>> from collections import deque
>>> d2 = deque('def')
>>> d2.extendleft('cba')
>>> d2
deque(['a', 'b', 'c', 'd', 'e', 'f'])
Tenga en cuenta que cada elemento se antepondrá uno a la vez, invirtiendo así efectivamente su orden.
Rendimiento de listversusdeque
Primero configuramos con un antecedente iterativo:
import timeit
from collections import deque
def list_insert_0(prepends: int):
l = []
for i in range(prepends):
l.insert(0, i)
def list_slice_insert(prepends):
l = []
for i in range(prepends):
l[:0] = [i] # semantically same as list.insert(0, i)
def list_add(prepends):
l = []
for i in range(prepends):
l = [i] + l # caveat: new list each time
def deque_appendleft(prepends):
d = deque()
for i in range(prepends):
d.appendleft(i) # semantically same as list.insert(0, i)
def deque_extendleft(prepends):
d = deque()
d.extendleft(range(prepends)) # semantically same as deque_appendleft above
Y una función de análisis, para que podamos comparar de manera justa todas las operaciones en una variedad de usos:
def compare_prepends(n, runs_per_trial):
results = {}
for function in (
list_insert_0, list_slice_insert,
list_add, deque_appendleft, deque_extendleft,
):
shortest_time = min(timeit.repeat(
lambda: function(n), number=runs_per_trial))
results[function.__name__] = shortest_time
ranked_methods = sorted(results.items(), key=lambda kv: kv[1])
for name, duration in ranked_methods:
print(f'{name} took {duration} seconds')
y rendimiento (ajustando el número de ejecuciones por prueba para compensar tiempos de ejecución más prolongados de más anteposiciones; repeatrealiza tres pruebas de forma predeterminada):
compare_prepends(20, 1_000_000)
compare_prepends(100, 100_000)
compare_prepends(500, 100_000)
compare_prepends(2500, 10_000)
>>> compare_prepends(20, 1_000_000)
deque_extendleft took 0.6490256823599339 seconds
deque_appendleft took 1.4702797569334507 seconds
list_insert_0 took 1.9417422469705343 seconds
list_add took 2.7092894352972507 seconds
list_slice_insert took 3.1809083241969347 seconds
>>> compare_prepends(100, 100_000)
deque_extendleft took 0.1177942156791687 seconds
deque_appendleft took 0.5385235995054245 seconds
list_insert_0 took 0.9471780974417925 seconds
list_slice_insert took 1.4850486349314451 seconds
list_add took 2.1660344172269106 seconds
>>> compare_prepends(500, 100_000)
deque_extendleft took 0.7309095915406942 seconds
deque_appendleft took 2.895373275503516 seconds
list_slice_insert took 8.782583676278591 seconds
list_insert_0 took 8.931685039773583 seconds
list_add took 30.113558700308204 seconds
>>> compare_prepends(2500, 10_000)
deque_extendleft took 0.4839253816753626 seconds
deque_appendleft took 1.5615574326366186 seconds
list_slice_insert took 6.712615916505456 seconds
list_insert_0 took 13.894083382561803 seconds
list_add took 72.1727528590709 seconds
El deque es mucho más rápido. A medida que las listas se hacen más largas, los deques funcionan aún mejor. Si puede utilizar deque, extendleftprobablemente obtendrá el mejor rendimiento de esa manera.
Si debe usar listas, tenga en cuenta que para listas pequeñas, list.insertfunciona más rápido, pero para listas más grandes, la inserción usando notación de sectores se vuelve más rápida.
No antepongas a las listas
Las listas estaban destinadas a ser añadidas, no antepuestas. Si tiene una situación en la que este tipo de anteposición perjudica el rendimiento de su código, cambie a una deque o, si puede revertir su semántica y lograr el mismo objetivo, invierta su lista y agregue en su lugar.
En general, evite anteponer el objeto Python integrado list.
