python - Python中的10个字符组成的字符串集在RAM中的大小比预期的大10倍

Question

我正在RAM中创建一个Python set，其中包含1000万个10字符的字符串（每个char都可以在0-255内表示，比这更复杂，没有UTF8非ASCII复杂字符）。

我认为它应该使用大约〜10M * 10 = 100 MB，也许+ 50％用于数据结构，即最大150 MB。但是相反，该过程使用了... 993 MB！

（作为比较，当我使用10个元素而不是10 * 1000 * 1000运行同一脚本时，该进程仅在RAM中使用4 MB。）

如何使打火机在RAM中的10个字符组成字符串集？

import random

def randstr():  # random string of length 10
    return ''.join(random.choice('abcdefghijklmnopqrstruvwxyz') for i in range(10))

s = set()

for i in range(10*1000*1000):
    s.add(randstr())

注意：如果可能的话，我想保留一个set()而不是另一个数据库（例如SQLite），因为它的成员查找速度非常快。

注意：我使用的是Python 2.7 64位

注意：在我的真实程序中，实际上是100-5亿个项目，这就是为什么我要节省内存。

Answer 1

使用标准集合/字符串，这就是您所能获得的，因为Python中存在大量开销。但是您可以使用其他数据结构。在这里，我提出一种方案，它不仅比原始数据占用更多的空间，而且实际上比原始数据占用更少的空间，而且相当快速和简单。

新数据结构

在先前的评论中，您说过“我唯一需要的设置操作是成员资格查找"test" in s”，并且“对于100M项目集，我希望每次查找<50微秒”。

所以这是一个主意：将每个字符串分成长度为prefix的p和长度为10- suffix的p。并将您的数据放入字典suffixes映射前缀，该前缀映射到以空格分隔的后缀。因此，例如，如果您使用p = 4且只有两个字符串"abcdefghij"和"abcdklmnop"，则您的字典将是{'abcd': 'efghij klmnop'}。然后用word[p:] in suffixes[word[:p]]查找字符串。

空间

我建议p = 4。然后，您有264 = 456976前缀，并且有5亿个字符串，每个前缀大约有1094个后缀。

具有一千万个字符串和p = 4：

25 MB for the dict itself
18 MB for the dict keys (i.e., the prefixes)
86 MB for the dict values (i.e., the suffixes)
130 MB total

具有2000万个字符串和p = 4：

25 MB for the dict itself
18 MB for the dict keys (i.e., the prefixes)
156 MB for the dict values (i.e., the suffixes)
200 MB total

不出所料，字典本身的大小及其键=前缀没有变化，但值=后缀的大小增加了70 MB。应当这样，因为每个前缀都添加了七个字节（六个字母加上一个空格），所以我们增加了一千万。

=>对于5亿个字符串，预期为3560 MB，即每个字符串7.12字节。因此，甚至少于您期望的每个字符串10个字节。

时间

我无法测试5亿个单词，因此我使用了n = 739645和p = 2并将随机数的长度设为8。这给了我739645/262 = 1094个后缀，每个前缀的长度为6，与完整测试相同。然后，我测量了查找一百万个随机单词的时间。在repl.it（使用64位Python）上，每次查找花费了12微秒。在我的PC（使用32位Python）上，每次查找花费2.1微秒。因此，我估计您每次查找大约需要5微秒，大约是您所需速度的10倍。

最佳化

通过不使用空格分隔后缀，而使用CamelCase，可以使其变得更小，更快。因此，对于上面的小示例，您将具有{'abcd': 'EfghijKlmnop'}。然后，每个字符串将有6.12字节，并且查找速度应提高7/6倍。

您还可以利用小字母。使用六个字母，您有266种可能，只需要log256（266）≈3.53字节。因此，您可以将每个六个字母的后缀转换为仅四个字节。 CamelCase将不再起作用，但是使用空格分隔，每个后缀仍只存储五个字节，因此每个字符串总共5.12字节。与最初的想法相比，已经转换的后缀的查找速度应提高7/5倍，尽管现在转换可能会花费大量时间。

嗯，实际上，p = 5可能更好。总的来说，它应该占用大约相同的内存量，并且要快得多，因为您将只对42个后缀进行分组，而不是对1094个后缀进行分组，而搜索这些后缀组字符串通常需要花费很多时间。对于5亿个字符串，我认为总大小将从3560 MB增加到大约4180。在我的PC上，平均查找时间为0.32微秒（模拟长度为8的739645字符串，并使用p = 3）。并且由于五个字母适合三个字节，因此您可以在密钥上节省1000 MB，在后缀上节省1000 MB，最后总共2180 MB，即每个字符串4.36字节。尽管转换为三字节字符串可能比实际查找花费更长的时间。您可以创建另一个表来存储转换，以便您可以查找它们，这虽然很快，但是又要花费大量的额外内存。另一个想法：keys = prefix可以转换为从0到265的整数。这应该节省大约200 MB，并且速度可能很快。

测试码

我用来产生以上输出的测试代码：

import random
from collections import defaultdict
from sys import getsizeof as sizeof
from timeit import timeit

# Settings: Number of strings and prefix length
n = 10*1000*1000
p = 4

def randstr():  # random string of length 10
    return ''.join(random.choice('abcdefghijklmnopqrstruvwxyz') for i in range(10))

# Build and store the test data (n random strings)
suffixes = defaultdict(str)
for i in xrange(n):
    word = randstr()
    prefix, suffix = word[:p], word[p:]
    suffixes[prefix] += suffix + ' '

# Show the sizes
dict_size = sizeof(suffixes)
keys_size = sum(map(sizeof, suffixes.keys()))
values_size = sum(map(sizeof, suffixes.values()))
print dict_size / 10**6, 'MB for the dict itself'
print keys_size / 10**6, 'MB for the dict keys (i.e., the prefixes)'
print values_size / 10**6, 'MB for the dict values (i.e., the suffixes)'
print (dict_size + keys_size + values_size) / 10**6, 'MB total'

# Speed test
words = [randstr() for _ in xrange(10**6)]
t = timeit(lambda: sum(word[p:] in suffixes[word[:p]] for word in words), number=1)
print '%.2f microseconds per lookup' % t