在這個itertools配方中定義seen_add = seen.add有什麼意義？

Question

我讀了itertools recipe for unique_everseen：

def unique_everseen(iterable, key=None): 
    "List unique elements, preserving order. Remember all elements ever seen." 
    # unique_everseen('AAAABBBCCDAABBB') --> A B C D 
    # unique_everseen('ABBCcAD', str.lower) --> A B C D 
    seen = set() 
    seen_add = seen.add 
    if key is None: 
     for element in filterfalse(seen.__contains__, iterable): 
      seen_add(element) 
      yield element 
    else: 
     for element in iterable: 
      k = key(element) 
      if k not in seen: 
       seen_add(k) 
       yield element 

什麼是在上面的代碼定義seen_add = seen.add的地步？

Answer 1

表現。使用本地名字取消引用該方法不是屬性查找快得多（其具有到每個時間綁定一個新的方法的對象）：

>>> import timeit 
>>> timeit.timeit('s.add', 's = set()', number=10**7) 
0.4227792940218933 
>>> timeit.timeit('seen_add', 's = set(); seen_add = s.add', number=10**7) 
0.15441945398924872 

使用本地參考幾乎3倍的速度。因爲在循環中使用了set.add，所以值得優化掉屬性查找。

Answer 2

這是一項名爲"hoisting" or "Loop-invariant code motion"的技術。實質上，你做了一個多次執行的操作，但總是在循環外部而不是循環體中返回相同的值。

在這種情況下，循環將重複查找seen集合的add屬性並創建「綁定方法」。這實際上非常快，但仍然是一個在循環內執行多次的操作，並始終給出相同的結果。所以你可以一次查找屬性（在這種情況下是綁定方法）並將其存儲在變量中以獲得一些性能。

請注意，雖然這提供了加速，但這絕不是「太多」。我刪除了第二支爲這個時機，使代碼更短：

from itertools import filterfalse 

def unique_everseen(iterable): 
    seen = set() 
    seen_add = seen.add 
    for element in filterfalse(seen.__contains__, iterable): 
     seen_add(element) 
     yield element 

def unique_everseen_without(iterable): 
    seen = set() 
    for element in filterfalse(seen.__contains__, iterable): 
     seen.add(element) 
     yield element 

一些exemplaric計時：

# no duplicates 
a = list(range(10000)) 
%timeit list(unique_everseen(a)) 
# 5.73 ms ± 279 µs per loop (mean ± std. dev. of 7 runs, 100 loops each) 
%timeit list(unique_everseen_without(a)) 
# 6.81 ms ± 396 µs per loop (mean ± std. dev. of 7 runs, 100 loops each) 

# some duplicates 
import random 
a = [random.randint(0, 100) for _ in range(10000)] 
%timeit list(unique_everseen(a)) 
# 1.64 ms ± 12.8 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each) 
%timeit list(unique_everseen_without(a)) 
# 1.66 ms ± 16.1 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each) 

# only duplicates 
a = [1]*10000 
%timeit list(unique_everseen(a)) 
# 1.64 ms ± 78.5 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each) 
%timeit list(unique_everseen_without(a)) 
# 1.63 ms ± 24.1 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each) 

所以，當你拿到〜10％的增速在沒有重複情況下，它實際上是在幾乎無用你有很多重複的情況。

其實這個配方顯示了另一個「吊裝」的例子，更具體的filterfalse(seen.__contains__, iterable)。這會查詢您的seen的__contains__方法設置一次，並在filterfalse內反覆調用它。

也許外賣應該是：吊裝方法查找是一個微型優化。它減少了循環的常量因子。在某些操作中加速可能是值得的，但個人而言，我認爲它應該謹慎使用，並且只能與分析/基準結合使用。