Python快速XOR范围算法

Question

Python快速XOR范围算法

algorithmpython-2.7data-structures

5

这是一个编程挑战，需要根据序列起始数和间隔长度生成XOR校验和。

它要求您基于间隔长度迭代序列，并在每次迭代时保持减少选用的元素数进行校验计算。

例如：

如果起始数字为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

问题

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

它们对于一些简单的计算，例如例子中的计算，表现良好，但当区间长度较大时（例如1000），它们需要显著更多的时间。

问题

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

我需要理解为什么我的解决方案性能不佳，以及哪种算法和数据结构适合这个挑战。

- mattgathu

任何逐项评估的解决方案都需要O（length²）次操作。您不需要任何实际数据结构。尝试理解[dd2的答案]（https://dev59.com/Vpvga4cB1Zd3GeqP2Xej#39941113）。尝试使用该算法处理的术语重复该过程。 - greybeard

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- v78 · Accepted Answer

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

使用这种方法来获取范围[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)

现在，你可以在O(n)而不是O(n^2)的时间复杂度下计算给定区间的XOR校验和。

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来表示，其中⊕表示XOR操作。在A和B之间的所有数字的XOR可以表示为f(B)⊕f(A−1)，因为x⊕x=0。

现在我们可以很容易地找出：

时间复杂度 - O(1)

参考

第二个参考