21

受这个好答案的启发，

这是一个基准：

import timeit

def test1():
    a = [1,2,3]
    a.insert(0,1)

def test2():
    a = [1,2,3]
    a[0:0]=[1]

print (timeit.timeit('test1()','from __main__ import test1'))
print (timeit.timeit('test2()','from __main__ import test2'))

对我来说，test2速度稍快（~10%）。为什么会这样？我希望它会慢一些，因为：

  1. 切片分配必须能够接受任何长度的迭代，因此必须更通用。
  2. 在切片分配中，我们需要在右侧创建一个新列表才能使其正常工作。

任何人都可以帮助我理解这一点吗？

（在 OS-X 10.5.8 上使用 python 2.7）

4

1 回答 1

16

您的第一个测试用例必须调用insertlist 上的方法a，而其中的所有操作test2都直接在字节码中处理。注意下面CALL_FUNCTION的反汇编test1。在 Python 中调用函数的成本适中：当然成本足以解释运行时间的几个百分点差异。

>>> import dis
>>> dis.dis(test1)
  2           0 LOAD_CONST               1 (1)
              3 LOAD_CONST               2 (2)
              6 LOAD_CONST               3 (3)
              9 BUILD_LIST               3
             12 STORE_FAST               0 (a)

  3          15 LOAD_FAST                0 (a)
             18 LOAD_ATTR                0 (insert)
             21 LOAD_CONST               4 (0)
             24 LOAD_CONST               1 (1)
             27 CALL_FUNCTION            2
             30 POP_TOP             
             31 LOAD_CONST               0 (None)
             34 RETURN_VALUE        
>>> dis.dis(test2)
  2           0 LOAD_CONST               1 (1)
              3 LOAD_CONST               2 (2)
              6 LOAD_CONST               3 (3)
              9 BUILD_LIST               3
             12 STORE_FAST               0 (a)

  3          15 LOAD_CONST               1 (1)
             18 BUILD_LIST               1
             21 LOAD_FAST                0 (a)
             24 LOAD_CONST               4 (0)
             27 LOAD_CONST               4 (0)
             30 STORE_SLICE+3       
             31 LOAD_CONST               0 (None)
             34 RETURN_VALUE

不好的解释

我先发布了这个，但经过考虑，我认为它是不正确的。我在这里描述的差异只有在需要移动大量数据时才会产生明显的差异，而这里的测试并非如此。即使有很多数据，差异也只有百分之几：

import timeit

def test1():
    a = range(10000000)
    a.insert(1,1)

def test2():
    a = range(10000000)
    a[1:1]=[1]

>>> timeit.timeit(test1, number=10)
6.008707046508789
>>> timeit.timeit(test2, number=10)
5.861173868179321

该方法list.insert由 中的函数ins1实现listobject.c。您会看到它一一复制列表尾部的项目引用：

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

另一方面，切片分配由函数实现，该函数list_ass_slice调用memmove：

memmove(&item[ihigh+d], &item[ihigh],
        (k - ihigh)*sizeof(PyObject *));

所以我认为你的问题的答案是 C 库函数memmove比简单循环更优化。请参阅此处了解 glibc 的实现memmove：我相信，当从中调用时list_ass_slice，最终会调用_wordcopy_bwd_aligned，您可以看到它是经过大量手动优化的。

于 2012-09-21T20:42:05.373 回答