algorithm - Python快速异或超范围算法

Question

有一项编程挑战要求根据序列起始编号和间隔长度生成XOR 校验和。

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

示例:

---

如果起始编号为0，间隔长度为3，则流程如下所示:

0 1 2/

3 4/5

6/7 8

异或 (^) 校验和为 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

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

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

现在我们很容易发现，

时间复杂度 - O(1)

reference

reference two