Python快速XOR超范围算法

Question

存在编程挑战,需要基于序列起始编号和间隔长度生成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)时会花费更多的时间

问题

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

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

Answer 1

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

使用此方法获取范围的xor [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,其中⊕表示XOR运算,然后A和B之间所有数字的XOR 可以用f(B)⊕f(A-1)表示,因为x ⊕x= 0

现在我们可以很容易地发现,

时间复杂度 - O(1)

参考

参考二