Python快速XOR超范围算法 [英] Python fast XOR over range algorithm
问题描述
有一个编程挑战，需要根据序列起始号和间隔长度生成一个 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 ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ strong>
我的解决方案方法
使用递归
import operator
import sys
sys.setrecursionlimit（20000 ）
def答案（开始，长度）：
lst = [range（length + length * n，start + length * n + length）for n in xrange（length）]
return my_reduce（lst，length）
def my_reduce（lst，length）：
如果不是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（开始，长度））
def gen_nums（开始，长度）：
l =长度
而l> 0：
for x in xrange（start，start + l）：
yield x
start = start + length
l = l - 1
问题
我的两种方法运行不够快。
它们对于微不足道的计算，比如示例中的，但是显着更多时间间隔长度大，例如 1000
问题
- 这个挑战正在测试什么计算机科学概念？
- 什么是正确的算法方法？
- 什么是正确的数据结构？
我需要明白为什么我的解决方案表现不佳，算法和数据结构如何适应这个挑战。
我建议对您的解决方案进行简单的优化。
使用此方法进行ge 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⊕⊕⊕⊕⊕⊕⊕⊕⊕⊕⊕⊕⊕⊕⊕⊕⊕⊕⊕⊕⊕⊕⊕⊕⊕⊕⊕⊕⊕⊕⊕⊕⊕⊕⊕⊕⊕⊕⊕⊕⊕⊕⊕ B 可以由f（B）⊕f（A-1）表示，因为x⊕x= 0
现在我们可以很容易地找到，
时间复杂性 - O（1）
There is a programming challenge that requires one to generate an XOR checksum based on sequence start number and an interval length.
It requires you to iterate the sequence based on the interval length and at each iteration keep reducing the number of elements picked for the checksum calculation.
Example:
if the start number is 0 and the interval length is 3, the process would look like this:
0 1 2/
3 4 / 5
6 / 7 8
where the XOR (^) checksum is 0^1^2^3^4^6 == 2
Likewise, if the start is 17 and the interval length 4, the process would look like:
17 18 19 20 /
21 22 23 / 24
25 26 / 27 28
29 / 30 31 32
which produces the checksum 17^18^19^20^21^22^23^25^26^29 == 14
My solutions approach
Using Recursion
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)
Iterative approach using a generator
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
My two approaches do not run fast enough.
They do fine for trivial calculations e.g the ones in the examples but take significantly more time when the interval length is large e.g 1000
Questions
- What computer science concepts are being tested by this challenge?
- What is the right algorithmic approach?
- what are the right data structures to use?
I need to understand why my solution performs poorly and what algorithm and data structures fit this challenge.
I am suggesting a simple optimization over your solution.
Use this method to get the xor of a range[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)
Now for a given interval you can compute XOR checksum in O(n) instead of 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
Explanation
Let us denote f(n)=1⊕2⊕3⊕⋯⊕n, where ⊕ denotes XOR operation then XOR of all numbers between A and B can be represented by f(B)⊕f(A−1), because x⊕x=0
Now we can find out easily that,
Time Complexity - O(1)
这篇关于Python快速XOR超范围算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
