有没有有效的方法来增加整数数组中整数的相应设置位置?

Question

任何消耗少于O(位长度)时间的解决方案都是受欢迎的。我需要处理大约 1 亿个大整数。

answer = [0 for i in xrange(100)]
def pluginBits(val):
global answer
for j in xrange(len(answer)):
if val <= 0:
break
answer[j] += (val & 1)
val >>= 1

Answer 1

一种更快的方法是使用'{:b}'.format(someval)从整数转换为'1's 和'0's 的字符串。 Python 仍然需要做类似的工作来执行此转换，但在解释器内部的 C 层执行此操作涉及的开销要少得多，对于较大的值。

要转换为整数 1 和 0 的实际list，您可以执行以下操作：

# Done once at top level to make translation table:
import string
bitstr_to_intval = string.maketrans(b'01', b'x00x01')
# Done for each value to convert:
bits = bytearray('{:b}'.format(origint).translate(bitstr_to_intval))

由于bytearray是range(256)迭代实际int值的可变值序列，因此不需要转换为list;它应该可以在99%使用list的地方使用，使用更少的内存，运行速度更快。

这确实会以与代码生成的顺序相反的方式生成值(也就是说，此处bits[-1]与answer[0]相同，bits[-2]是answer[1]等)，并且它是无填充的，但由于您正在对位求和，因此不需要填充，并且反转结果是一个微不足道的反转切片(在末尾添加[::-1])。通过使answer成为一个numpy数组(允许在 C 层进行批量元素添加)，可以更快地对每个输入的位求和，并将它们放在一起得到：

import string
bitstr_to_intval = string.maketrans(b'01', b'x00x01')
answer = numpy.zeros(100, numpy.uint64)
def pluginBits(val):
bits = bytearray('{:b}'.format(val).translate(bitstr_to_intval))[::-1]
answer[:len(bits)] += bits

在本地测试中，pluginBits对于 10,000 个随机输入整数(每个整数 100 位)，对每个位置的位求和需要不到七分之一的时间，并获得相同的结果。