python - 基于 ID 列表有效计算 XOR(^) 校验和的方法

Question

当我在谷歌上搜索有关 Python 列表理解的信息时，我收到了一个 google foobar 挑战，过去几天我一直在慢慢地研究它以获得乐趣。最新挑战:

有效地要求生成一个 ID 列表，忽略每一行中不断增加的数字，直到剩下一个 ID。然后你应该对 ID 进行 XOR(^) 以产生校验和。我创建了一个输出正确答案的工作程序，但是它的效率不足以在分配的时间内通过所有测试用例(通过 6/10)。 50,000 的长度应该在 20 秒内产生结果，但它需要 320。

有人可以引导我朝着正确的方向前进，但请不要为我做这件事，我很乐意通过这个挑战来插入自己。也许我可以实现一种数据结构或算法来加快计算时间？

代码背后的逻辑:

1. 首先取起始ID和长度

2. 生成一个 ID 列表，忽略每一行中越来越多的 ID，从忽略第一行的 0 开始。

3. 使用 for 循环对 IDS 列表中的所有数字进行异或运算

4. 答案以整数形式返回

---

import timeit
def answer(start,length):
    x = start
    lengthmodified = length
    answerlist = []
    for i in range (0,lengthmodified): #Outter for loop runs an amount of times equal to the variable "length".
        prestringresult = 0
        templist = []
        for y in range (x,x + length): #Fills list with ids for new line
            templist.append(y)
        for d in range (0,lengthmodified): #Ignores an id from each line, increasing by one with each line, and starting with 0 for the first
            answerlist.append(templist[d])
        lengthmodified -= 1
        x += length    
        for n in answerlist: #XORs all of the numbers in the list via a loop and saves to prestringresult
            prestringresult ^= n
        stringresult = str(prestringresult) 
        answerlist = [] #Emptys list
        answerlist.append(int(stringresult)) #Adds the result of XORing all of the numbers in the list to the answer list
    #print(answerlist[0]) #Print statement allows value that's being returned to be checked, just uncomment it
    return (answerlist[0]) #Returns Answer



#start = timeit.default_timer()
answer(17,4)
#stop = timeit.default_timer()
#print (stop - start) 

Answer 1

您可能需要一种不同的方法，而不仅仅是像 John 那样的小改进。我刚刚编写了一个解决方案，可以在我的 PC 上大约 2 秒内完成 answer(0, 50000)。我仍然逐行进行，但不是对行范围内的所有数字进行异或运算，而是逐位进行。行中有多少个数字设置了 1 位？^[*] 奇数个数字？然后我翻转答案的 1 位。然后与 2 位、4 位、8 位等相同，直至 2³⁰ 位。所以对于每一行，它只是 31 次小计算(而不是实际对数万个数字进行异或)。

[*] 可以从范围的开始/停止开始在恒定时间内快速计算。

编辑: 由于您要求提供另一个提示，下面介绍如何计算在某个范围 (a, b) 中设置 1 位的频率。计算它在范围 (0, a) 中设置的频率，并从它在范围 (0, b) 中设置的频率中减去该值。如果范围从零开始会更容易。在某个范围(0，c)中设置 1 位的频率是多少？简单:c//2 次。那么在某个范围(a，b)中设置 1 位的频率是多少？只需 b//2 - a//2 次。高位类似，只是稍微复杂一点。

编辑 2: 哦，等等，我刚想起来...有一种简单的方法可以计算某个范围 (a, b) 内所有数字的异或。再次将工作分成 range(0, a) 和 range(0, b)。某个范围 (0, c) 中所有数字的异或很容易，因为有一个很好的模式(如果你对从 0 到比方说 30 的所有 c 都这样做，你就会看到它)。使用它，我现在在大约 0.04 秒 内解决了 answer(0, 50000)。