python - 提高我的 XOR 程序的时间和空间效率

Question

这是一个众所周知的问题，其他地方已经提供了整体解决方案，但如果可以的话，我正在努力寻找自己的解决方案。下面的代码在 10 秒内给我带来了解决方案，这很慢但参数非常大 - 我正在创建一个 numpy 数组并使用 reduce 函数，所以我很想听听其他让它更快的想法。

我认为我遇到了一个更大的问题，即我的长度参数不能比这大得多而不会遇到内存问题 - 我已经在 10,000 时尝试过并崩溃 - 所以我怀疑我可能不得不取消数组呢？

import numpy as np
import timeit

def solution(start, length):
  checkArray = []
  for j in range(length):
    checkArray += [i for i in range(start, start+length)]
    start = start + length + j
    length -= 1
  checkArray = np.array(checkArray)
  checksum = np.bitwise_xor.reduce(checkArray)
  return checksum


start = timeit.default_timer()
solution(1500000000,9500)
stop = timeit.default_timer()

Answer 1

您不需要构建整个数组来计算 XOR。这就是导致内存问题的原因。下面的解决方案在不构建任何中间数组的情况下给出了相同的结果(range 不是数组或列表，而是定义了一个 Generator)，并且(在我的机器上)更快( ~2.5 对您的示例输入的 5.33 秒)。

这对于任何输入也不应该有任何内存问题，并且不需要任何外部库。

def new_solution(start, length):
    a = 0
    for j in range(length):
        for x in range(start, start + length - j):
            a ^= x
        start += length
    return a