Python 中的低内存索引列表

Question

我有以下代码：

l = []
for i in range(A):
    for j in range(B):
        if predicate(i,j): 
            l.append((i, j))

我们假设 A 和 B 是非常非常大数 [~10e7]，所以 l 在最坏的情况下可能有 A * B 的巨大规模。假设函数 predicate 是一个决定是否取元组 (i,j).

的通用函数

我想要一个解决方案：

减少保存所需的内存量l
允许高效随机取消引用 l 中的元素，即：我们在 range(len(l)) 和 [= 中选择一个随机索引 k 53=] l[k] 快点。
构建列表 l 相当快（也许 append 不是正确的函数？）

我只是很清楚 (1)、(2) 和 (3) 可能会发生冲突，也许 python list 不是正确的方法。谁能提供不同的方法？

谢谢！！

Answer 1

而不是元组和重复 i，您可以主要只存储 j 值：

l = []
prefixsum = [0]
for i in range(A):
    J = [j for j in range(B) if predicate(i,j)]
    l.append(J)
    prefixsum.append(prefixsum[-1]) + len(J))

然后对于给定的 k，在 prefixsum 中进行二进制搜索以得到 i，然后在列表中查找 j。

此外，除了 int 对象的列表，您还可以使用 Python arrays 的 4 字节整数（或 3 字节整数，需要一些额外的工作）。 NumPy 数组，这也可能使整个计算更快。

粗略测试，忽略一些开销，在 64 位 Python:

# A list of 100 tuples takes 888 bytes (just the list object)
> l = [(10**6, 10**6 + j) for j in range(100)]
> l = [(10**l.__sizeof__()
888

# The tuples take 4000 bytes
> l = [(10**sum(t.__sizeof__() for t in l)
4000

# The i-value takes 28 bytes
> l[0][0].__sizeof__()
28

# The j-values take 2800 bytes
sum(j.__sizeof__() for _, j in l)
2800

因此，对于包含 2 个整数的 100 个元组的列表，这是 7716 个字节。现在是 j 值的 array：

> a = array.array('I', (j for i, j in l))
> a = array.a.__sizeof__()
472

内存减少了 16 倍。

Python 中的低内存索引列表

Low Memory Index List in Python

python

out-of-memory