加快Python2與XOR的嵌套循環

Question

The answer這個問題被標記爲重複的是錯誤的，並不能滿足我的需求。

我的代碼旨在計算一系列數字中的散列值。

以矩陣的形式來理解結構比較容易。如果我有從29開始16個數字的結構將是：（起始= 29，長度= 4）

29，30，31，32，
33，34，35，36，
37，38， 39，40，
41，42，43，44

給定的算法指定的哈希會以粗體給出的數字的XOR：

29，30，31，32，//，
33,34,35, //， 36，
37，38， //，39，40，
41， //，42，43，44

哈希= 29^30^31^32^33^34^35^37^38^39 = 54

---

我的代碼是：

def answer(start, length): 
    val=0 
    c=0 
    for i in range(length): 
     for j in range(length): 
      if j < length-i: 
       val^=start+c 
      c+=1 
    return val 

計算大數值所需的時間，如answer(2000000000,10**4)太方便了。

---

約束：

• Py2.7.6
• 只有標準庫除了BZ2，隱窩，的fcntl，MMAP，PWD，pyexpat，選擇，信號，termios的，線程，時間，unicodedata， zipimport，zlib。
• 有限的計算時間。

當前計算測試參數（我不知道）給我一個超時錯誤。

---

對於更大的值，我的代碼的速度如何提高？

Answer 1

有是在接受答案Python fast XOR over range algorithm了一個錯誤：遞減l需要的XOR運算之前完成。這裏有一個修復後的版本，以及一個assert測試，以驗證它的結果與樸素算法相同。

def f(a): 
    return (a, 1, a + 1, 0)[a % 4] 

def getXor(a, b): 
    return f(b)^f(a-1) 

def gen_nums(start, length): 
    l = length 
    ans = 0 
    while l > 0: 
     l = l - 1 
     ans ^= getXor(start, start + l) 
     start += length 
    return ans 

def answer(start, length): 
    c = val = 0 
    for i in xrange(length): 
     for j in xrange(length - i): 
      n = start + c + j 
      #print '%d,' % n, 
      val ^= n 
     #print 
     c += length 
    return val 

for start in xrange(50): 
    for length in xrange(100): 
     a = answer(start, length) 
     b = gen_nums(start, length) 
     assert a == b, (start, length, a, b) 

過的start和length這些範圍，gen_nums比answer快約5倍，但我們可以大致兩倍的速度再次讓它（即約10倍的速度answer）通過消除這些函數調用：

def gen_nums(start, length): 
    ans = 0 
    for l in xrange(length - 1, -1, -1): 
     b = start + l 
     ans ^= (b, 1, b + 1, 0)[b % 4]^(0, start - 1, 1, start, 0)[start % 4] 
     start += length 
    return ans 

---

由於米雷克Opoka在評論中提到，% 4相當於& 3，而且速度更快，因爲按位AR算術比執行整數除法和丟掉商更快。所以我們可以用

ans ^= (b, 1, b + 1, 0)[b & 3]^(0, start - 1, 1, start, 0)[start & 3] 

Answer 2

看起來你可以取代內部循環，如果搭配：

for j in range(length - i) val^=start+c c+=1 c+=i 這應該節省一些時間，當我變得更大

恐怕我現在不能測試此權利，對不起！

Answer 3

恐怕，在answer(2000000000,10**4)的輸入中，你永遠不會「及時完成」。

您可以通過改善內循環，在c變量每次不更新，並使用xrange代替range，這樣得到相當顯著加快：

def answer(start, length): 
    val=0 
    c=0 
    for i in range(length): 
     for j in range(length): 
      if j < length-i: 
       val^=start+c 
      c+=1 
    return val 


def answer_fast(start, length): 
    val = 0 
    c = 0 
    for i in xrange(length): 
     for j in xrange(length - i): 
      if j < length - i: 
       val ^= start + c + j 
     c += length 
    return val 


# print answer(10, 20000) 
print answer_fast(10, 20000) 

探查表明，answer_fast約兩倍儘快：

> python -m cProfile script.py 
366359392 
     20004 function calls in 46.696 seconds 

Ordered by: standard name 

ncalls tottime percall cumtime percall filename:lineno(function) 
     1 0.000 0.000 46.696 46.696 script.py:1(<module>) 
     1 44.357 44.357 46.696 46.696 script.py:1(answer) 
     1 0.000 0.000 0.000 0.000 {method 'disable' of '_lsprof.Profiler' objects} 
    20001 2.339 0.000 2.339 0.000 {range} 

> python -m cProfile script.py 
366359392 
     3 function calls in 26.274 seconds 

Ordered by: standard name 

ncalls tottime percall cumtime percall filename:lineno(function) 
     1 0.000 0.000 26.274 26.274 script.py:1(<module>) 
     1 26.274 26.274 26.274 26.274 script.py:12(answer_fast) 
     1 0.000 0.000 0.000 0.000 {method 'disable' of '_lsprof.Profiler' objects} 

但是，如果你想要主要的加速（magnitute訂單），你應該考慮在Cython中重寫你的函數。

這裏是它的「cythonized」版本：

def answer(int start, int length): 
    cdef int val = 0, c = 0, i, j 
    for i in xrange(length): 
     for j in xrange(length - i): 
      if j < length - i: 
       val ^= start + c + j 
     c += length 
    return val 

隨着與上述相同的輸入參數，它需要小於200ms insted的20+秒，這是一個100倍的加速。

> ipython 

In [1]: import pyximport; pyximport.install() 
Out[1]: (None, <pyximport.pyximport.PyxImporter at 0x7f3fed983150>) 

In [2]: import script2 

In [3]: timeit script2.answer(10, 20000) 
10 loops, best of 3: 188 ms per loop 

隨着你的輸入參數，它需要58ms：

In [5]: timeit script2.answer(2000000000,10**4) 
10 loops, best of 3: 58.2 ms per loop