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

当谷歌搜索有关Python列表理解的信息时,我获得了一个google foobar挑战,我在过去的几天里一直在慢慢地工作以获得乐趣.最新挑战:

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

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

代码背后的逻辑:

首先,获取起始ID和长度

生成ID列表,忽略来自每个新行的ID越来越多的ID,从忽略第一行的0开始.

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

答案以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) 

Stefan Pochm.. 5

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

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

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

编辑2:哦等等,我记得......有一种简单的方法来计算某些范围内所有数字的xor(a,b).再次将工作分为做范围(0,a)和范围(0,b).某些范围(0,c)中所有数字的xor都很容易,因为有一个很好的模式(如果你从0开始为所有c做这个,那就说30).使用这个,我现在解决answer(0, 50000)大约0.04秒.

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

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

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

编辑2:哦等等,我记得......有一种简单的方法来计算某些范围内所有数字的xor(a,b).再次将工作分为做范围(0,a)和范围(0,b).某些范围(0,c)中所有数字的xor都很容易,因为有一个很好的模式(如果你从0开始为所有c做这个,那就说30).使用这个,我现在解决answer(0, 50000)大约0.04秒.