加速Python2嵌套循环用异或

Question

The answer of the question this is marked duplicate of is wrong and does not satisfy my needs.

我的代码旨在从一系列数字中计算哈希值。在

矩阵形式的结构更容易理解。如果我有16个从29开始的数字，那么结构将是：（start=29，length=4）

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

给定算法指定哈希将是以粗体显示的数字的异或：

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版
• expat-zlmap，expat-thread，expat-zlp，仅适用于pwmad-thread，expat-zlp，只适用于pwmad-thread，expat-zlp，只适用于pwmap-zl标准端口，只适用于pwmap-zlp标准端口。在
• 计算时间有限。在

当前计算测试参数（我不知道）给我一个超时错误。在

---

如何提高代码的速度以获得更大的值？在

Answer 1

看起来您可以将内部循环替换为：

for j in range(length - i) val^=start+c c+=1 c+=i 当我变大的时候，这样可以节省一些时间

恐怕我现在无法测试，对不起！在

Answer 2

恐怕，用你在answer(2000000000,10**4)中的输入，你永远无法“及时”完成。在

通过改进内部循环，不必每次都更新c变量，并使用xrange而不是{}，这样可以显著提高速度：

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的速度大约是后者的两倍：

^{pr2}$

但是如果你想要大提速（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

在与上述相同的输入参数下，用时不到200毫秒，而不是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

输入58毫秒：

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

Answer 3

在Python fast XOR over range algorithm的可接受答案中，存在一个缺陷：在进行异或计算之前，{a1}的递减需要在之前完成。这是一个修复过的版本，以及一个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倍，但我们可以通过消除这些函数调用使其速度再快一倍（即大约是answer的10倍）：

^{pr2}$

---

正如Mirek Opoka在评论中提到的，% 4相当于{}，它更快，因为按位运算比执行整数除法和丢弃商更快。所以我们可以用

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