python - 通过预分配和 `my_list[x] = y` 作为 `__setitem__` 的语法糖来填充 python 列表。

Question

在对 Python 2.7 中的代码进行一些优化时，我偶然发现了以下现象:

>>> from timeit import timeit
>>> def fill_by_appending():
...     my_list = []
...     for x in xrange(1000000):
...             my_list.append(x)
...     return my_list
...
>>> def fill_preallocated_1():
...     my_list = [0]*1000000
...     for x in xrange(1000000):
...             my_list[x] = x
...     return my_list
...
>>> def fill_preallocated_2():
...     my_list = [0]*1000000
...     for x in xrange(1000000):
...             my_list.__setitem__(x,x)
...     return my_list
...
>>> def fill_by_comprehension():
...     my_list = [x for x in xrange(1000000)]
...     return my_list
...
>>> assert fill_by_appending() == fill_preallocated_1() == fill_preallocated_2() == fill_by_comprehension()
>>> timeit("fill_by_appending()", setup="from __main__ import fill_by_appending", number=100)
5.877948999404907
>>> timeit("fill_preallocated_1()", setup="from __main__ import fill_preallocated_1", number=100)
3.964423894882202
>>> timeit("fill_preallocated_2()", setup="from __main__ import fill_preallocated_2", number=100)
12.38241720199585
>>> timeit("fill_by_comprehension()", setup="from __main__ import fill_by_comprehension", number=100)
2.742932081222534

预分配比附加更快，或者理解比其他任何东西都快，这对我来说并不奇怪，但为什么使用 __setitem__ 比使用 慢三倍>[]？

最初，我有一个理论，即使用 my_list[x] = x 要么只是将 my_list[x] 中存储的引用重新分配给新对象的地址，或者解释器甚至注意到两者都是相同的类型并使用了重载的赋值运算符，而 setitem 调用实际上复制了内存，但一些实验证明我错了:

>>> class MyList(list):
...     def __setitem__(self, x,y):
...             super(MyList, self).__setitem__(x,y**2)
...
>>> ml = MyList([1,2,3,4,5])
>>> ml[2]=10
>>> ml
[1, 2, 100, 4, 5]

有人知道幕后发生了什么吗？

Answer 1

通用方法调度比基于语法的调度有额外的开销；后者can directly call the C level equivalent of the __setitem__ method ，而前者必须重复查找并创建绑定(bind)方法，并通过通用方法调度机制来调度调用(更通用==更慢)。通用调度还意味着构造要传递的参数的元组(其中基于语法的调用只是从 Python 堆栈中读取值，而不构造元组)。

此外，Python 级别名称实际上是一个薄包装器，因此调用 __setitem__ 意味着在到达 C API 之前要额外遍历一层，因为它必须在到达之前再遍历一层sq_ass_item(C 层插槽，是实现分配的最终调用)。 METH_COEXIST can be used to limit the slot wrapper overhead根据文档，但它看起来像 that was only used for __getitem__ on list .

您可以通过存储绑定(bind)方法来消除方法查找和绑定(bind)开销，这可能会节省一些工作，但从根本上来说，对于 CPython，语法胜过方法调用；如果语法同样清晰且不易出错，请使用语法。一个可能减少一些差异的预绑定(bind)示例是:

def fill_preallocated_3():
    my_list = [0]*1000000
    set = my_list.__setitem__
    for x in xrange(1000000):
        set(x,x)
    return my_list