What's the idiomatic syntax for prepending to a short python list? What's the idiomatic syntax for prepending to a short python list? python python

What's the idiomatic syntax for prepending to a short python list?


The s.insert(0, x) form is the most common.

Whenever you see it though, it may be time to consider using a collections.deque instead of a list.


If you can go the functional way, the following is pretty clear

new_list = [x] + your_list

Of course you haven't inserted x into your_list, rather you have created a new list with x preprended to it.


What's the idiomatic syntax for prepending to a short python list?

You don't usually want to repetitively prepend to a list in Python.

If the list is short, and you're not doing it a lot... then ok.

list.insert

The list.insert can be used this way.

list.insert(0, x)

But this is inefficient, because in Python, a list is an array of pointers, and Python must now take every pointer in the list and move it down by one to insert the pointer to your object in the first slot, so this is really only efficient for rather short lists, as you ask.

Here's a snippet from the CPython source where this is implemented - and as you can see, we start at the end of the array and move everything down by one for every insertion:

for (i = n; --i >= where; )    items[i+1] = items[i];

If you want a container/list that's efficient at prepending elements, you want a linked list. Python has a doubly linked list, which can insert at the beginning and end quickly - it's called a deque.

deque.appendleft

A collections.deque has many of the methods of a list. list.sort is an exception, making deque definitively not entirely Liskov substitutable for list.

>>> set(dir(list)) - set(dir(deque)){'sort'}

The deque also has an appendleft method (as well as popleft). The deque is a double-ended queue and a doubly-linked list - no matter the length, it always takes the same amount of time to preprend something. In big O notation, O(1) versus the O(n) time for lists. Here's the usage:

>>> import collections>>> d = collections.deque('1234')>>> ddeque(['1', '2', '3', '4'])>>> d.appendleft('0')>>> ddeque(['0', '1', '2', '3', '4'])

deque.extendleft

Also relevant is the deque's extendleft method, which iteratively prepends:

>>> from collections import deque>>> d2 = deque('def')>>> d2.extendleft('cba')>>> d2deque(['a', 'b', 'c', 'd', 'e', 'f'])

Note that each element will be prepended one at a time, thus effectively reversing their order.

Performance of list versus deque

First we setup with some iterative prepending:

import timeitfrom collections import dequedef 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 timedef 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

And a function for analysis, so that we can fairly compare all operations across a range of usages:

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

and performance (adjusting the number of runs per trial down to compensate for longer running times of more prepends - repeat does three trials by default):

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 secondsdeque_appendleft took 1.4702797569334507 secondslist_insert_0 took 1.9417422469705343 secondslist_add took 2.7092894352972507 secondslist_slice_insert took 3.1809083241969347 seconds>>> compare_prepends(100, 100_000)deque_extendleft took 0.1177942156791687 secondsdeque_appendleft took 0.5385235995054245 secondslist_insert_0 took 0.9471780974417925 secondslist_slice_insert took 1.4850486349314451 secondslist_add took 2.1660344172269106 seconds>>> compare_prepends(500, 100_000)deque_extendleft took 0.7309095915406942 secondsdeque_appendleft took 2.895373275503516 secondslist_slice_insert took 8.782583676278591 secondslist_insert_0 took 8.931685039773583 secondslist_add took 30.113558700308204 seconds>>> compare_prepends(2500, 10_000)deque_extendleft took 0.4839253816753626 secondsdeque_appendleft took 1.5615574326366186 secondslist_slice_insert took 6.712615916505456 secondslist_insert_0 took 13.894083382561803 secondslist_add took 72.1727528590709 seconds

The deque is much faster. As the lists get longer, deques perform even better. If you can use deque's extendleft you'll probably get the best performance that way.

If you must use lists, keep in mind that for small lists, list.insert works faster, but for larger lists, inserting using slice notation becomes faster.

Don't prepend to lists

Lists were meant to be appended to, not prepended to. If you have a situation where this kind of prepending is a hurting the performace of your code, either switch to a deque or, if you can reverse your semantics and accomplish the same goal, reverse your list and append instead.

In general, avoid prepending to the built-in Python list object.


matomo