爲什麼while循環比for循環更有效率？

我正在研究Eratosthenes的Sieve，我正在分析如何從候選人範圍過濾非素數。爲什麼while循環比for循環更有效率？

爲了測試，我使用這個命令：

import timeit 
print timeit.timeit(stmt="sieve(1000)", setup='from sieve import sieve', number=1000)

這是我目前有：

def sieve(limit): 
    primes = [2] 
    pRange = range(3, limit, 2) 
    while pRange: 
     p = pRange.pop(0) 
     filter_range = range(p**2, limit, p << 1) 
     pRange = filter(lambda x: x not in filter_range, pRange) 
     primes.append(p) 
    return primes

秒=>5.42698788643

轉念一想，如果我是要從範圍中彈出第一個元素，我可能想要這樣寫：

def sieve(limit): 
    primes = [2] 
    pRange = range(3, limit, 2) 
    for p in pRange: 
     filter_range = range(p**2, limit, p << 1) 
     pRange = filter(lambda x: x not in filter_range, pRange) 
     primes.append(p) 
    return primes

但事實證明，在15.7085180283秒慢得多。

這是怎麼發生的？ for循環遍歷pRange的初始值並且不更新？

來源

2014-11-23 Kevin Engle

你確定第二個返回正確的結果嗎？因爲你正在改變'pRange'的值，'for'正在迭代... – 2014-11-23 18:49:35

你沒有改變for循環中的pRange，而是創建一個新的列表。當然，它不會影響循環。 – Daniel 2014-11-23 18:50:09

** for循環遍歷pRange的初始值並且不更新？**：是 – 2014-11-23 18:50:18

for p in pRange:

此評估pRange，通過該範圍中的物品將其變成一個列表（Python的2）或發電機（Python 3中），然後進行迭代。 它不重新評估pRange。

無論哪種方式都會產生比循環更多的循環迭代，因爲後者每次都通過循環重新評估範圍。

請記住，在Python中，變量是全部引用。即使像a = 5這樣的意思是「設置a來指代值爲5的整數常量」。同樣，pRange = filter(...)的意思是「以filter(...)返回的對象爲參照，並設置pRange來引用它。釋放引用爲pRange用於指代的任何值（如果沒有指向它，可能會進行垃圾回收）。」

來源

2014-11-23 18:53:21

爲什麼while循環比for循環更有效率？

回答

相關問題