4

我正在研究一种大量使用 int64s 数组的 Python 算法。数组通常是稀疏的，并且不断地被读取和写入。我目前使用的是相对较大的本机数组，性能很好，但内存使用率很高（正如预期的那样）。

我希望能够让数组实现不会为未使用的值浪费空间，并允许索引偏移量不是零。例如，如果我的数字从 1,000,000 开始，我希望能够从 1,000,000 开始索引我的数组，并且不需要用一百万个未使用的值来浪费内存。

数组读取和写入需要快速。扩展到新领域可能会有一点延迟，但如果可能的话，读写应该是 O(1)。

有人知道可以做到这一点的图书馆吗？

谢谢！

更新以提及 int64 作为数据类型。

4

5 回答 5

4

听起来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等）。文档详细说明了每个操作的时间复杂性，因此您应该能够评估它是否满足您的需求。

于 2010-06-09T04:33:32.407 回答
1

您可以将numpy 稀疏矩阵重新映射为稀疏数组 - 或考虑使用哈希表（python 字典）。就偏移而言，只需包装您正在使用的任何存储类并让您拥有自己的插入/查找/删除方法。

于 2010-06-09T04:05:39.300 回答
1

我不知道任何 Python，所以这可能是一个未回答的问题：

在某些语言中，您可以通过将索引空间中的函数定义到数据空间中来模拟稀疏数组。例如（伪代码）：

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

在某些语言（最好的语言）中，数组引用的形式（例如f[3]）看起来就像函数调用的形式（例如f[3]）。当然，这是因为数组定义了从索引空间到数据空间的函数。这种方式也很容易实现更高维的稀疏数组。

于 2010-06-09T08:20:39.580 回答
1

为什么不只使用字典？

sparse = dict()
sparse[100000] = 1234
sparse[123456] = 2345
于 2010-06-09T09:13:48.853 回答
1

另一种选择 - 至少如果您愿意自己实现一个 - 是Page table。这通常在虚拟内存系统中用于将虚拟地址映射到物理地址，如果您的地址空间是稀疏填充的，并且使用的地址是集群的，那么它的效果最好。如果使用的地址是随机分布的，这将不太有效。

页表的基本方法与Trie相同- 递归细分。页表有一些固定的层数，每个节点都是一个固定大小的数组。如果给定子节点的条目为空，则该节点覆盖的所有叶子都为空。页表的主要优点是查找速度很快，只需要一些位移和取消引用。

让我们看一个 2 级页表的简单 Python 实现：

class Pagetable(object):
  def __init__(self, num_bits=8):
    """Creates a new Pagetable with num_bits bits per level.

    Args:
      num_bits: The number of bits per pagetable level.
        A 2 level pagetable will be able to store indexes between 0 and 2^(num_bits*2).
    """
    self.num_bits = num_bits
    self.mask = (1 << num_bits) - 1
    self.root = [None] * (2 ** num_bits)

  def __getitem__(self, idx):
    page = self.root[idx >> self.num_bits]
    return page and page[idx & self.mask]

  def __setitem__(self, idx, val):
    page = self.root[idx >> self.num_bits]
    if not page:
      page = self.root[idx >> self.num_bits] = [None] * (2 ** self.num_bits)
    page[idx & self.mask] = val
于 2010-06-10T09:23:07.450 回答