通過預先分配和將`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

通用方法分派擁有基於語法派遣額外的開銷;後者必須反覆查找並創建一個綁定方法，並通過通用方法調度機制調用該調用（更一般的==較慢）。通用調度還意味着構造要傳遞的參數的tuple（其中基於語法的調用只是從Python堆棧讀取值而不構建tuple）。

此外，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。

您可以通過存儲綁定方法來消除方法查找和綁定開銷，這可能會節省一些工作量，但對於CPython而言，基本上，語法會節省方法調用;如果語法同樣清晰且不易出錯，請使用語法。可能會降低一些差異的預綁定的例子是：

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

Answer 2

你有額外的屬性查詢+第二函數的函數調用：

def fill_preallocated_1():

  ... 
     32 LOAD_FAST    1 (x) 
     35 LOAD_FAST    0 (my_list) 
     38 LOAD_FAST    1 (x) 
     41 STORE_SUBSCR   
     ... 

def fill_preallocated_2():

  ... 
     32 LOAD_FAST    0 (my_list) 
     35 LOAD_ATTR    1 (__setitem__) 
     38 LOAD_FAST    1 (x) 
     41 LOAD_FAST    1 (x) 
     44 CALL_FUNCTION   2 
     ...