用于一组短字节串的高效存储数据结构

2022-03-31 00:00:00 python data-structures set memory hashtable

问题描述

我正在寻找一种在Python中类似集合的数据结构，它允许对长度约为10的1亿个短字符串(或字节字符串)进行快速查找(集合为O(1))。

在10M字符串的情况下，这已经占用了Python3.7或3.10.2上的750MB内存(如果用字符串替换b字符串，则占用900MB)：

S = set(b"a%09i" % i for i in range(10_000_000))  # { b"a000000000", b"a000000001", ... }
而"；实际数据这里是10字节*10M~100MB。因此，由于集合结构、指针、存储桶，内存消耗系数为7.5倍。(有关列表情况下的研究，请参阅Memory usage of a list of millions of strings in Python的答案)。

在处理短字符串时，在内部结构中有指向字符串的指针(可能需要64位=8字节)可能已经是哈希表的2倍因素，也是哈希表的存储桶结构等。

是否有一些短字符串优化技术允许在Python中使用一组内存高效的短字节串？(或任何其他允许快速查找/成员资格测试的结构)

可能没有指向字符串的指针，但如果字符串长度<；=16个字符等，则直接将字符串存储在数据结构中。

或者使用bisect或排序列表帮助(在O(Logn)中查找可能是可以的)，同时保持较小的内存使用量？(小于7.5倍的系数，如集合)

解决方案

到目前为止，以下是我根据注释测试的方法，它们似乎起作用了。

排序列表+对分搜索(+Bloom Filter)

  • 按排序顺序插入标准列表L、中的所有内容。这比集合占用的内存要少得多。

  • (可选)创建Bloom Filter，here是一段非常小的代码。

  • (可选)首先使用Bloom Filter测试成员身份(快速)。

  • 使用bisect检查真的是否与in_sorted_list()中的快速in_sorted_list()匹配(且不是假阳性)，这比标准查找b"hello" in L快得多。

如果对分搜索足够快，我们甚至可以绕过Bloom Filter(步骤2和3)。它将是O(Log N)。

在我的100M字符串测试中，即使没有布隆过滤器，查找平均也需要2微秒。

sqlite3

正如@tomalak的评论所建议的那样，将所有数据插入到一个sqlite3数据库中非常有效。 在我的8 GB数据库上，即使没有任何索引，查询数据库中是否存在字符串平均只需50微秒。

添加索引使数据库增长到11 GB，但随后查询平均仍在约50微秒内完成，因此此处没有任何收益。

编辑：正如在评论中提到的，使用CREATE TABLE t(s TEXT PRIMARY KEY) WITHOUT ROWID;甚至缩小了数据库：3.3 GB，查询平均仍在约50微秒内完成。Sqlite3(一如既往)真的很棒。

在这种情况下，甚至可以使用How to load existing db file to memory in Python sqlite3?中的方法将其完全加载到RAM中，然后每次查询大约9微秒！

带排序行的文件中的二等分

工作，并且使用非常快的查询(每次查询约35微秒)，而无需将文件加载到内存中！看见 Bisection search in the sorted lines of an opened file (not loaded in memory)

以前缀为键、以后缀串联为值的词典

这是此处介绍的解决方案：Set of 10-char strings in Python is 10 times bigger in RAM as expected。

想法是：我们有一个词典D，对于给定的word，

prefix, suffix = word[:4], word[4:]
D[prefix] +=  suffix + b' '

使用这种方法，使用的RAM空间比实际数据还要小(我测试了30M的平均长度为14的字符串，使用了349MB)，查询速度看起来很快(2us)，但DICT的初始创建时间有点高。

我也尝试了dictValues=后缀列表，但它更消耗内存。

相关文章