减少大型字典使用的内存

Question

我需要创建一个内存对象，其键为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()函数，字典的大小为3.1兆字节（每个条目大约占用56个字节来存储9个数字和一个布尔值）。

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

是否有其他数据结构或方法可以在处理如此大的数据集时节省内存？

- RoyHB

---

你是真的对三态（True，False，字典中没有该键）感兴趣，还是只对布尔值感兴趣？如果是后者，使用仅包含True值的set更为合适。 - nneonneo

Answer 1

如果您使用整数键查找布尔值，并且键的范围从0开始且连续，那么使用列表真的没有什么不好的地方。

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

或者更好：

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

如果这还不够，尝试使用array模块，并且每个bool值只使用一个字节：

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

如果这还不够好，可以尝试在PyPi上使用 bitarray模块。

另一个想法是使用set：假设你有比True更多的False，只需使用一个集合：

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

并检查

value = number in my_true_numbers

如果您拥有比False更多的True，则要反其道而行之。

- Christian Schramm

---

这个设置的想法很好，取决于分布情况（True 和 False 哪个更多或者相反），集合中的一个值可以表示 True 或 False，哪个更好就用哪个。 - Samy Arous

感谢Christian和其他贡献者。我会尝试使用Christian的set方法。看起来非常有前途。 - RoyHB

使用[ True ] * 56000来创建一个包含56000个True的列表。请注意，虽然同一引用被重复使用了56000次，但由于True是不可变的，所以这并不重要。 - Antti Haapala -- Слава Україні

Answer 2

Python: Reducing memory usage of dictionary的被接受的答案得出一个结论，即没有太多可以做的事情，我同意这个结论。字典的总体内存开销很小，但你的例子中键值对的数量却增加了内存占用。

可能有一种可能性：如果键始终是线性的，您可以直接创建布尔列表或更好地使用bitarray。然后，键将是隐式的。但如果这只是在你的例子中发生的情况，那么你无能为力。

- tea2code

---

感谢您的建议。不幸的是，这些键不是线性的。问题在于，尽管只有56,000个条目，但每个条目的键都是从100,000,000到800,000,000的某个整数，因此我认为我的列表或位数组需要直接访问非键对象中的布尔值，长度为800,000,000个元素。 - RoyHB

有没有一种确定性的方式可以将键减少为线性整数？ - tea2code

很遗憾，我看不到减少整数的方法。每个整数都是设备的唯一标识符，可以向我报告其状态，我无法预测哪个唯一标识符可能会报告。我事先只知道大约有56,000个可能会报告，但我不知道这999,999,999个可能中的哪56,000个会这样做。我可以将唯一ID的列表映射到列表位置，但这将导致需要维护两个列表。我将使用该技术进行实验，并查看结果如何。 - RoyHB

Christian Schramm的想法似乎值得一试。在最坏的情况下，您需要两个集合。一个用于true，另一个用于false，但您不需要存储布尔值。 - tea2code

@tea2code：那会太贵了。与字典相比，set 只能节省 30% 的空间；拥有两个集合将需要比单个字典更多的空间（因为 set 进行了过度分配）。 - nneonneo

Answer 3

如果“key not found”对你来说不是一个重要的状态（即你可以将不在数组中的键视为False），那么你可以使用一个set来存储只映射到True的元素。这样做需要的空间约少30％，因为每个条目仅由两个64位数量（哈希和键）组成，而不是三个数量（哈希、键、值）。

请记住，sys.getsizeof(dict)只告诉您dict本身的大小，而不是其中包含的对象。创建56000个int作为键也会带来自己的代价：每个整数24字节（类型指针、引用计数、值）。这本身就会占用1.3MB的内存，除了字典所占用的内存之外。

要真正节省空间，您可以使用NumPy compressed sparse row矩阵：

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()

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

- nneonneo

Answer 4

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

设置标志位是为了确保值已被用户正确设置（非必需），第二个比特位包含该值。

使用 64位无符号整数，您只需要203个来存储整个数组。

然后，您可以使用位索引访问它：假设您想要访问索引123处的值。您需要访问#246和#247位（一个用于设置布尔值，另一个用于值）。

由于246和247小于2**64，它们存储在第一个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)

位运算比较棘手（算术移位和逻辑移位）且不易调试，但它们可以非常强大。

- lucasg

Answer 5

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

values = list(range(56000))

如果您使用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

这种方法可以显著减少内存使用，但是与字典或集合相比，查找需要O(log n)的时间而不是O(1)，插入需要O(n)的时间而不是O(1)。

- flornquake