一种基于XOR表的IDs校验和高效计算方法

Question

当我在google上搜索关于Python列表理解的信息时，有人给我提供了一个googlefoobar挑战，我在过去的几天里一直在慢慢地做这个挑战。最新挑战：

有效地调用生成一个ID列表，忽略每个新行中递增的数字，直到只剩下一个ID为止。然后您应该对id进行异或（^）以生成校验和。我创建了一个输出正确答案的工作程序，但是它的效率不足以在分配的时间内通过所有测试用例（通过6/10）。50000的长度应该在20秒内产生结果，但是需要320秒。在

有人能把我引向正确的方向，但请不要为我做这件事，，我很乐意挑战自己。也许有一种数据结构或算法我可以实现来加快计算时间？在

代码背后的逻辑：

1. 首先，开始的ID和长度在

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

3. 使用for循环对id列表中的所有数字执行xor运算

4. 答案以int形式返回

---

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

既不需要templist也不需要answerlist。让我们检查一下代码，看看如何消除它们。在

1. 首先，让我们将templist的初始化设置为一行代码。这个：

   templist = []
   for y in range (x,x + length):
       templist.append(y)
   

   变成这样：

   templist = list(range(x, x + length))
   

2. 那么让我们对answerlist执行相同的操作。这个：

   for d in range (0,lengthmodified):
       answerlist.append(templist[d])
   

   变成这样：

   answerlist.extend(templist[:lengthmodified])
   

3. 现在让我们来看看它们是如何被使用的。如果我们暂时忽略lengthmodified -= 1和x += length，我们有：

   templist = list(range(x, x + length))
   answerlist.extend(templist[:lengthmodified])
   
   for n in answerlist:
       prestringresult ^= n
   
   answerlist = []
   

   与其扩展answerlist，迭代它，然后清除它，只迭代templist会更快。在

   templist = list(range(x, x + length))
   
   for n in templist[:lengthmodified]:
       prestringresult ^= n
   

   现在也不需要templist，所以让我们跳过构建它。在

   for n in range(x, x + lengthmodified):
       prestringresult ^= n
   

   templist和{}都不见了。

这里唯一缺少的是answerlist.append(int(stringresult))返回。我把这个留给你想办法。在

总的来说，这里的教训是尽可能避免显式的for循环。编写大量迭代容器的for循环是一种C思维方式。在Python中，经常有一些方法可以一次完整地分析集合。这样做可以利用语言的快速内置操作。在

另外，惯用Python也很容易阅读。在

Answer 2

我可以在不使用list的情况下得到一点改进，但是对于大量的数据，它仍然会失败。嵌套循环会降低速度。我认为你需要遵循波希曼的逻辑，因为暴力很少是解决这类问题的方法。在

Answer 3

你可能需要一种不同的方法，而不仅仅是像John那样的小改进。我刚刚在我的电脑上写了一个可以在大约2秒钟内完成answer(0, 50000)的解决方案。我仍然逐行执行，但是我没有对行范围内的所有数字执行xooring，而是一点一点地执行。行中有多少个数字设置了1位？^[*]奇数？然后我把我的答案翻过来。对于2位、4位、8位等，则相同，直到2³⁰-位。因此，对于每一行，它只是31个小计算（而不是实际的xooring数万个数字）。在

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

编辑：既然您要求了另一个提示，下面就介绍如何计算在某个范围（a，b）内设置1位的频率。计算它在范围（0，a）中设置的频率，并从它在范围（0，b）中设置的频率中减去。如果范围从零开始就容易多了。在某个范围（0，c）内设置1位的频率是多少？简单：c//2次。那么在某个范围（a，b）中1位的设置频率是多少？只需b//2 - a//2次。更高的位是相似的，只是稍微复杂一点。在

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