Python中的长索引数组

Question

我正在尝试通过在一个布尔数组中用索引来引用10亿个连续的整数，从而减少内存的使用。简单来说，我需要创建一个包含100亿个元素的数组，但这已经超出了“长整型”的范围。当我试图引用一个超过sys.maxint的数组索引时，数组就崩溃了：

x = [False] * 10000000000
Traceback (most recent call last):
  File "", line 1, in 
    x = [0] * 10000000000
OverflowError: cannot fit 'long' into an index-sized integer

我有什么办法可以解决这个问题吗？我在网上找不到其他人遇到过这个问题……大概答案是“python处理不了超过20亿的数组。”

Answer 1

密集位向量是可行的，但如果你不知道元素数量不会超过大约 10**10，而且这些元素都聚集在一起，且分布比较随机的话，它就不是最优的选择。如果你的元素分布不同，那么使用其他结构会更好。

比如说，如果你知道在这个范围内 [0,10**10) 只有少量元素存在，那就可以使用 set()。反之，如果几乎每个元素都存在，只有少数几个缺失，那就可以使用一个反向集合，也就是 element not in mySet。

如果你的元素倾向于聚集在小范围内，可以使用一种叫做游程编码的方法，比如 [xrange(0,10),xrange(10,15),xrange(15,100)]。你可以通过二分查找来找到匹配的范围，如果找到的索引是偶数，那么这个元素就在集合里。插入和删除操作则需要稍微调整一下这些范围。

如果你的元素分布确实很密集，但你需要的内存超过了可用内存（这在实际中很常见），那么可以使用 mmap 来管理内存，并用一个适配器包装映射的文件，这个适配器使用类似于之前提到的 array('I') 的机制。

想要了解你的数据能压缩到什么程度，可以尝试先构建一个包含合理数据的普通文件，然后应用一个通用的压缩算法（比如 gzip）来看看能减少多少空间。如果压缩效果明显，那你在代码中也可以考虑使用某种空间优化的方法。

Answer 2

bitarray这个包看起来可能是另一个有用的选择。

Answer 3

在32位的地址空间里，任何编程语言都很难处理这么大的数组。还有一个问题就是你电脑里实际有多少内存。

如果你想要一个包含10亿个元素的数组，每个元素表示真或假，可以使用array.array('I', ...) ...

container = array.array('I', [0]) * ((10000000000 + 31) // 32)

这样你就可以用常规的位掩码和位移操作来设置和清除这些位。

另一种选择：

如果只有少量的元素为真，或者只有少量的元素为假，你可以使用集合（set）来节省内存，或者使用字典（dict）来方便编程。