有没有好的Python稀疏一维数组库推荐？

Question

我正在用Python开发一个算法，这个算法大量使用了int64类型的数组。这些数组通常是稀疏的，也就是里面有很多空的地方，而且我需要频繁地读取和写入这些数组。目前我使用的是比较大的原生数组，性能还不错，但内存使用量很高（这也是预料之中的）。

我希望能有一种数组实现方式，不会浪费那些没有用到的值的空间，并且可以让数组的索引从零以外的地方开始。举个例子，如果我的数字是从1,000,000开始的，我希望能从1,000,000开始索引我的数组，而不是浪费一百万个未使用的值的内存。

数组的读取和写入速度需要快。虽然扩展到新的区域可能会有一点延迟，但如果可能的话，读取和写入的时间应该是O(1)，也就是常数时间。

有没有人知道有什么库可以做到这一点？

谢谢！

更新说明数据类型是int64。

Answer 1

我对Python不太了解，所以这可能不是个答案：

在某些编程语言中，你可以通过定义一个函数，把你的索引空间（也就是你想要访问的数组位置）映射到你的数据空间（也就是实际存储的数据）来模拟稀疏数组。比如说（伪代码）：

f[1000000] = 32;
f[2000000] = 51;

在一些语言中（最好的那些语言），数组的引用形式（比如 f[3]）看起来就像函数调用的形式（比如 f[3]）。这当然是因为数组实际上定义了一个从索引空间到数据空间的函数。用这种方式实现更高维度的稀疏数组也非常简单。

Answer 2

你可以把一个 numpy 稀疏矩阵 转换成一个稀疏数组，或者考虑使用哈希表（也就是 Python 的字典）。关于偏移量，你只需要把你正在使用的存储类包裹起来，然后自己写插入、查找和删除的方法就可以了。

Answer 3

听起来你可能正需要 blist 这种类型（文档, 下载），顺便说一下，我就是这个的作者。它的使用方式和 Python 的 list 一模一样，所以你不用担心学习新东西，但它的性能表现却有所不同。特别是，在很多情况下，它能高效处理稀疏列表。下面是一个示例，创建了一个包含 2**29 个元素的列表，速度几乎是瞬间完成的。以这种方式创建的稀疏列表使用的空间是 O(log n)。

>>> from blist import *
>>> x = blist([0])             # x is a blist with one element
>>> x *= 2**29                 # x is a blist with > 500 million elements
>>> x.append(5)                # append to x
>>> y = x[4:-234234]           # Take a 500 million element slice from x
>>> del x[3:1024]              # Delete a few thousand elements from x

不过，遍历整个列表的操作仍然需要 O(n) 的时间，比如 remove、reverse、count 等等。文档中详细说明了每个操作的时间复杂度，所以你可以判断它是否能满足你的需求。