Python快速异或超范围算法

有一个编程挑战，需要生成一个XOR基于序列起始号和间隔长度的校验和。

它要求您根据间隔长度迭代序列，并在每次迭代时不断减少为校验和计算选取的元素数量。

Example:

如果起始编号是0间隔长度为3，该过程将如下所示：

0 1 2/

3 4 / 5

6 / 7 8

其中 XOR (^) 校验和是0^1^2^3^4^6 == 2

同样，如果开始是17和间隔长度4，该过程将如下所示：

17 18 19 20 /

21 22 23 / 24

25 26 / 27 28

29/ 30 31 32

产生校验和17^18^19^20^21^22^23^25^26^29 == 14

我的解决方法

使用递归

import operator
import sys

sys.setrecursionlimit(20000)

def answer(start, length):
    lst = [range(start+length*n, start+length*n+length) for n in xrange(length)]
    return my_reduce(lst, length)

def my_reduce(lst, length):
    if not lst: return 0
    l = lst.pop(0)
    return reduce(operator.xor, l[:length], 0) ^ my_reduce(lst, length-1)

使用生成器的迭代方法

def answer(start, length):
    return reduce(operator.xor, gen_nums(start, length))


def gen_nums(start, length):
    l = length
    while l > 0:
        for x in xrange(start, start+l):
            yield x
        start = start + length
        l = l - 1

Problem

我的两种方法运行得不够快。

它们对于琐碎的计算（例如示例中的计算）做得很好，但当间隔长度很大时，它们会花费更多的时间，例如1000

问题

• 这项挑战正在测试哪些计算机科学概念？
• 什么是正确的算法方法？
• 正确使用的数据结构是什么？

我需要了解为什么我的解决方案表现不佳以及哪些算法和数据结构适合这一挑战。

我建议对您的解决方案进行简单的优化。

使用此方法获取范围 [a,b] 的异或

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

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

现在，对于给定的时间间隔，您可以计算 XOR 校验和O(n)代替O(n^2).

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

解释

让我们表示f(n)=1⊕2⊕3⊕⋯⊕n, where ⊕表示异或运算。之间所有数字的异或A and B可以表示为f(B)⊕f(A−1)， 因为x⊕x=0

现在我们不难发现，

时间复杂度 - O(1)

参考 https://stackoverflow.com/questions/10670379/find-xor-of-all-numbers-in-a-given-range

参考二 https://discuss.codechef.com/questions/84803/how-to-find-xor-of-all-the-elements-in-given-range