6

我需要创建一个内存对象，该对象具有 9 位整数的键和与每个键关联的布尔值。我一直在使用字典，如下面的简化示例所示：

#!/usr/bin/python
from __future__ import print_function
import sys

myDict = {}
for n in range(56000):
        myDict[n] = True

print('Count:',len(myDict),' Size:', sys.getsizeof(myDict))

我需要能够查找和检索与每个键关联的布尔值。问题是字典的大小。在 64 位 Linux 系统上使用 Python 2.7 和上述示例，根据 sys.getsizeof()，dict 的大小为 3.1 兆字节。（每个条目大约 56 个字节来存储 9 个数字和一个布尔值）

我需要在字典中存储（大约）55.000 个条目的布尔状态。每个 dict 键是一个 9 位整数。我尝试使用整数和 str(theInteger) 作为键，而字典的大小没有变化。

我应该使用其他类型的数据结构或方法来节省如此庞大的数据集的内存吗？

4

5 回答 5

8

如果您使用整数键查找布尔值，并且键的范围从 0 开始并且是连续的，那么确实没有理由不使用列表：

my_list = []
for n in range(56000):
        my_list[n] = True

或更好：

my_list = [True for n in range(5600])

如果这还不够，请尝试该array模块并使用每个布尔值一个字节：

import array
my_array = array.array("b", (True for n in range(56000)))

如果这还不够好，请尝试PyPi 上的 bitarray 模块。

另一个想法是使用set: 假设你有很多False超过True，只需有一个集合：

my_true_numbers = {0, 2323, 23452} # just the True ones

并检查

value = number in my_true_numbers

如果您有True超过False，则反之。

于 2013-09-04T13:32:20.207 回答
3

Python的公认答案：减少字典的内存使用得出的结论是，你无能为力，我同意。字典的整体内存开销很小，但示例中键值对的数量会增加内存占用。

可能有人认为可能：如果键始终是线性的，则可以直接创建布尔值列表，或者更好地使用bitarray。然后，密钥将是隐式的。但是，如果这只是在您的示例中，您将无能为力。

于 2013-09-04T13:24:02.677 回答
2

如果“未找到键”对您来说不是一个重要的状态（即您可以将不在数组中的键视为False），您可以使用 aset来仅存储映射到 的元素True。这需要减少大约 30% 的空间，因为每个条目仅包含两个 64 位量（散列和键）而不是三个量（散列、键、值）。

请记住，它sys.getsizeof(dict)只会告诉您dict自身的大小，而不是其中包含的对象。创建 56000 ints 作为键也将承担其自身的成本：每个整数 24 个字节（类型指针、引用计数、值）。除了字典占用的内存之外，它本身将达到 1.3MB。

为了真正节省空间，您可以使用 NumPy压缩稀疏行矩阵：

from scipy.sparse import lil_matrix # linked-list matrix, used to construct the csr matrix
vals = lil_matrix((1,1000000000), dtype='int8'))
# We will use 0 = no such key, 1 = True, 2 = False
for n in myIndices:
    vals[n] = 1
vals = vals.tocsr()

的内存使用量vals非常小：数据56KB，索引224KB，其他结构不到1KB。因此，总大小小于281KB（比 dict 小 10 倍），没有额外分配的整数。查找元素并更改非零元素非常快（在排序数组中进行二分查找），但插入新的非零值或将现有的非零值归零是昂贵的操作。

于 2013-09-04T13:54:07.350 回答
1

为什么不使用巨大的位域？由于您至少需要三个值：true、false 和 not_init/UB，因此您将数据编码为两位。使用的总内存为55.000*2 bits = 110 000 bits = 13 kBytes.

画得不好的图

此处设置标志是为了确保该值已被用户正确设置（不是必需的），第二位包含该值。

使用64 bit unsigned integers，您只需要203它们来存储整个数组。

然后您可以使用 bit index 访问它：假设您要访问 index 处的值123。您将需要访问位#246ans #247（一个用于设置 bool，另一个用于值）。

既然246和247次于2**64，就存放在 上first uint。要访问它们：

return (( (1<<246) & array[0] ) >> 246 )

要访问任何位：

return (( (1<<n) & array[ n/(2**64) ] ) >> n)

（未测试位访问器）

设置一点：

array[ n/(2**64) ] = array[ n/(2**64) ] | (1<<n)

按位运算很棘手（算术移位与逻辑运算）并且不易调试，但它们可能非常强大。

于 2013-09-04T13:43:46.323 回答
0

根据您的具体需求，您可以使用列表来存储您的值。这只会使用字典使用的大约 16% 的空间，但某些操作（例如查找和插入）会（可能会慢很多）。

values = list(range(56000))

如果您使用该模块并将您的值存储在排序列表中，您的查找仍然会比使用 dict 慢，但比幼稚检查bisect快得多。x in my_list

列表必须始终按排序顺序保存。要检查一个值是否在您的列表中，您可以使用此函数：

def is_in_list(values, x):
    i = bisect_left(values, x)
    return i != len(values) and values[i] == x

像这样工作：

>>> is_in_list([2, 4, 14, 15], 4)
True
>>> is_in_list([2, 4, 14, 15], 1)
False
>>> is_in_list([2, 4, 14, 15], 13)
False

这种方法将显着减少内存使用量，但是 -与 dict 或 set 相比- 查找需要 O(log n) 时间而不是 O(1) 并且插入需要 O(n) 而不是 O(1)。

于 2013-09-04T16:54:04.103 回答