标签归档:prepend

简短的python列表之前的惯用语法是什么?

问题:简短的python列表之前的惯用语法是什么?

list.append()是添加到列表末尾的明显选择。这是有关失踪人员的合理解释list.prepend()。假设我的清单很短并且对性能的关注可以忽略不计,

list.insert(0, x)

要么

list[0:0] = [x]

惯用的?

list.append() is the obvious choice for adding to the end of a list. Here’s a reasonable explanation for the missing list.prepend(). Assuming my list is short and performance concerns are negligible, is

list.insert(0, x)

or

list[0:0] = [x]

idiomatic?


回答 0

s.insert(0, x)形式是最常见的。

但是,无论何时看到它,都可能是时候考虑使用collections.deque而不是列表了。

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.


回答 1

如果可以使用功能性方法,则以下内容很清楚

new_list = [x] + your_list

当然,你还没有插入xyour_list,而你已经创建了一个新的列表xpreprended它。

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.


回答 2

简短的python列表之前的惯用语法是什么?

通常,您不想在Python中重复地放在列表之前。

如果它很,并且您没有做很多…那么就可以了。

list.insert

list.insert可以采用这种方式。

list.insert(0, x)

但这是无效的,因为在Python中,a list是一个指针数组,并且Python现在必须获取列表中的每个指针并将其向下移动一个,以将指向对象的指针插入第一个插槽中,因此,这实际上仅是有效的根据您的要求列出较短的清单。

这是实现该功能的CPython源代码的一个片段-如您所见,我们从数组的末尾开始,每次插入将所有内容向下移动一位:

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

如果您希望容器/列表能够高效地添加元素,则需要一个链表。Python有一个双向链表,可以在开头和结尾快速插入-称为a deque

deque.appendleft

A collections.deque具有列表的许多方法。list.sort是一个exceptions,deque绝对不能完全用Liskov代替list

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

deque还有一个appendleft方法(以及popleft)。它deque是一个双端队列和一个双向链接的列表-不管长度如何,总是需要花费相同的时间来准备某些东西。在大O表示法中,列表的O(1)与O(n)时间。这是用法:

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

deque.extendleft

与此相关的还有双端队列的extendleft方法,该方法反复进行:

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

请注意,每个元素将一次添加一个,从而有效地颠倒了它们的顺序。

listvs的表现deque

首先,我们设置一些迭代的前缀:

import timeit
from collections import deque

def list_insert_0():
    l = []
    for i in range(20):
        l.insert(0, i)

def list_slice_insert():
    l = []
    for i in range(20):
        l[:0] = [i]      # semantically same as list.insert(0, i)

def list_add():
    l = []
    for i in range(20):
        l = [i] + l      # caveat: new list each time

def deque_appendleft():
    d = deque()
    for i in range(20):
        d.appendleft(i)  # semantically same as list.insert(0, i)

def deque_extendleft():
    d = deque()
    d.extendleft(range(20)) # semantically same as deque_appendleft above

和性能:

>>> min(timeit.repeat(list_insert_0))
2.8267281929729506
>>> min(timeit.repeat(list_slice_insert))
2.5210217320127413
>>> min(timeit.repeat(list_add))
2.0641671380144544
>>> min(timeit.repeat(deque_appendleft))
1.5863927800091915
>>> min(timeit.repeat(deque_extendleft))
0.5352169770048931

双端队列更快。随着列表的增加,我希望双端队列的性能更好。如果您可以使用双端队列,则extendleft可能会以这种方式获得最佳性能。

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 it’s 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')
>>> d
deque(['1', '2', '3', '4'])
>>> d.appendleft('0')
>>> d
deque(['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')
>>> d2
deque(['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 timeit
from collections import deque

def list_insert_0():
    l = []
    for i in range(20):
        l.insert(0, i)

def list_slice_insert():
    l = []
    for i in range(20):
        l[:0] = [i]      # semantically same as list.insert(0, i)

def list_add():
    l = []
    for i in range(20):
        l = [i] + l      # caveat: new list each time

def deque_appendleft():
    d = deque()
    for i in range(20):
        d.appendleft(i)  # semantically same as list.insert(0, i)

def deque_extendleft():
    d = deque()
    d.extendleft(range(20)) # semantically same as deque_appendleft above

and performance:

>>> min(timeit.repeat(list_insert_0))
2.8267281929729506
>>> min(timeit.repeat(list_slice_insert))
2.5210217320127413
>>> min(timeit.repeat(list_add))
2.0641671380144544
>>> min(timeit.repeat(deque_appendleft))
1.5863927800091915
>>> min(timeit.repeat(deque_extendleft))
0.5352169770048931

The deque is much faster. As the lists get longer, I would expect a deque to perform even better. If you can use deque’s extendleft you’ll probably get the best performance that way.


回答 3

如果有人像我一样发现这个问题,这是我对建议方法的性能测试:

Python 2.7.8

In [1]: %timeit ([1]*1000000).insert(0, 0)
100 loops, best of 3: 4.62 ms per loop

In [2]: %timeit ([1]*1000000)[0:0] = [0]
100 loops, best of 3: 4.55 ms per loop

In [3]: %timeit [0] + [1]*1000000
100 loops, best of 3: 8.04 ms per loop

如您所见,insert切片分配几乎是显式添加速度的两倍,并且结果非常接近。正如Raymond Hettinger指出的那样,这insert是更常见的选择,我个人更喜欢这种方式优先列出。

If someone finds this question like me, here are my performance tests of proposed methods:

Python 2.7.8

In [1]: %timeit ([1]*1000000).insert(0, 0)
100 loops, best of 3: 4.62 ms per loop

In [2]: %timeit ([1]*1000000)[0:0] = [0]
100 loops, best of 3: 4.55 ms per loop

In [3]: %timeit [0] + [1]*1000000
100 loops, best of 3: 8.04 ms per loop

As you can see, insert and slice assignment are as almost twice as fast than explicit adding and are very close in results. As Raymond Hettinger noted insert is more common option and I, personally prefer this way to prepend to list.