一组短字节串的内存高效数据结构
Memory-efficient data structure for a set of short bytes-strings
我正在 Python 中寻找类似集合的数据结构，它允许快速查找（集合的 O(1)），长度为 1 亿个短字符串（或字节字符串） ~ 10.
对于 10M 字符串，这已经在 Python 3.7 或 3.10.2 上占用 750 MB RAM（如果我们用字符串替换 b 字符串，则需要 900 MB）：
S = set(b"a%09i" % i for i in range(10_000_000)) # { b"a000000000", b"a000000001", ... }
而这里的“真实数据”是10字节*10M~100MB。所以有一个7.5倍的内存消耗因子，因为set结构，指针，buckets...（关于列表情况下的研究，参见的答案）。
当使用“短”字符串时，在内部结构中有指向字符串的指针（可能占用 64 位 = 8 字节）可能已经是一个 2x 因子，以及散列的桶结构-table,等等
是否有一些“短字符串优化”技术允许在 Python 中拥有一组内存高效的短字节字符串？（或任何其他结构允许快速 lookup/membership 测试)
可能没有指向字符串的指针，而是在字符串长度 <= 16 个字符等情况下直接将字符串存储在数据结构中
或者使用 bisect 或排序列表会有所帮助（在 O(log n) 中查找可能没问题），同时保持较小的内存使用量？ （小于一组的 7.5 倍）
Maybe without pointers to strings, but rather storing the strings directly in the data structure if string length <= 16 characters, etc.
虽然不是集合 data-structure 而是列表，但我认为 pyarrow 有一种非常优化的方式来存储大量小字符串。还有一个 pandas 集成，应该可以很容易地试用它：
https://pythonspeed.com/articles/pandas-string-dtype-memory/
到目前为止，这是我根据评论测试的方法，似乎有效。
排序列表 + 二分搜索（+ 布隆过滤器）
将所有内容插入标准列表L，按排序顺序。这比一组占用的内存少得多。
（可选）创建一个布隆过滤器，here是一个非常小的代码来完成它。
（可选）第一次使用 Bloom 过滤器测试成员资格（快速）。
检查它是否真的与来自this answer的快速in_sorted_list()匹配（而不是误报）使用bisect，比标准查找 b"hello" in L.
快得多
如果二分搜索足够快，我们甚至可以绕过布隆过滤器（步骤 2 和 3）。它将是 O(log n)。
在我对 100M 字符串的测试中，即使没有布隆过滤器，查找平均也需要 2 微秒。
Sqlite3
正如@tomalak 的评论所建议的那样，将所有数据插入到 Sqlite3 数据库中效果很好。
在我的 8 GB 数据库上查询数据库中是否存在字符串平均需要 50 微秒，即使没有任何索引。
添加索引使数据库增长到 11 GB，但查询仍然平均在 ~50 µs 内完成，所以这里没有收益。
编辑：如评论中所述，使用 CREATE TABLE t(s TEXT PRIMARY KEY) WITHOUT ROWID; 甚至使数据库更小：3.3 GB，并且查询平均仍可在 ~50 µs 内完成。 Sqlite3（一如既往）真的很棒。
在这种情况下，甚至可以使用 How to load existing db file to memory in Python sqlite3? 中的方法将其完全加载到 RAM 中，然后每个查询大约需要 9 微秒！
文件中的二等分行
工作正常，查询速度非常快（每次查询约 35 微秒），无需将文件加载到内存中！看
字典以前缀为键，后缀连接为值
这是此处描述的解决方案：。
想法是：我们有一个字典 D 并且，对于给定的 word，
prefix, suffix = word[:4], word[4:]
D[prefix] += suffix + b' '
使用这种方法，使用的内存space比实际数据还要小（我测试了30M的平均长度为14的字符串，使用了349MB），查询速度非常快（2 µs), 但是dict的初始创建时间有点高
我也尝试过使用 dict values = list of suffixes，但它更多 RAM-consuming。
我正在 Python 中寻找类似集合的数据结构，它允许快速查找（集合的 O(1)），长度为 1 亿个短字符串（或字节字符串） ~ 10.
对于 10M 字符串，这已经在 Python 3.7 或 3.10.2 上占用 750 MB RAM（如果我们用字符串替换 b 字符串，则需要 900 MB）：
S = set(b"a%09i" % i for i in range(10_000_000)) # { b"a000000000", b"a000000001", ... }
而这里的“真实数据”是10字节*10M~100MB。所以有一个7.5倍的内存消耗因子，因为set结构，指针，buckets...（关于列表情况下的研究，参见
当使用“短”字符串时，在内部结构中有指向字符串的指针（可能占用 64 位 = 8 字节）可能已经是一个 2x 因子，以及散列的桶结构-table,等等
是否有一些“短字符串优化”技术允许在 Python 中拥有一组内存高效的短字节字符串？（或任何其他结构允许快速 lookup/membership 测试)
可能没有指向字符串的指针，而是在字符串长度 <= 16 个字符等情况下直接将字符串存储在数据结构中
或者使用 bisect 或排序列表会有所帮助（在 O(log n) 中查找可能没问题），同时保持较小的内存使用量？ （小于一组的 7.5 倍）
Maybe without pointers to strings, but rather storing the strings directly in the data structure if string length <= 16 characters, etc.
虽然不是集合 data-structure 而是列表，但我认为 pyarrow 有一种非常优化的方式来存储大量小字符串。还有一个 pandas 集成，应该可以很容易地试用它： https://pythonspeed.com/articles/pandas-string-dtype-memory/
到目前为止，这是我根据评论测试的方法，似乎有效。
排序列表 + 二分搜索（+ 布隆过滤器）
将所有内容插入标准列表
L，按排序顺序。这比一组占用的内存少得多。（可选）创建一个布隆过滤器，here是一个非常小的代码来完成它。
（可选）第一次使用 Bloom 过滤器测试成员资格（快速）。
检查它是否真的与来自this answer的快速
快得多in_sorted_list()匹配（而不是误报）使用bisect，比标准查找b"hello" in L.
如果二分搜索足够快，我们甚至可以绕过布隆过滤器（步骤 2 和 3）。它将是 O(log n)。
在我对 100M 字符串的测试中，即使没有布隆过滤器，查找平均也需要 2 微秒。
Sqlite3
正如@tomalak 的评论所建议的那样，将所有数据插入到 Sqlite3 数据库中效果很好。 在我的 8 GB 数据库上查询数据库中是否存在字符串平均需要 50 微秒，即使没有任何索引。
添加索引使数据库增长到 11 GB，但查询仍然平均在 ~50 µs 内完成，所以这里没有收益。
编辑：如评论中所述，使用 CREATE TABLE t(s TEXT PRIMARY KEY) WITHOUT ROWID; 甚至使数据库更小：3.3 GB，并且查询平均仍可在 ~50 µs 内完成。 Sqlite3（一如既往）真的很棒。
在这种情况下，甚至可以使用 How to load existing db file to memory in Python sqlite3? 中的方法将其完全加载到 RAM 中，然后每个查询大约需要 9 微秒！
文件中的二等分行
工作正常，查询速度非常快（每次查询约 35 微秒），无需将文件加载到内存中！看
字典以前缀为键，后缀连接为值
这是此处描述的解决方案：
想法是：我们有一个字典 D 并且，对于给定的 word，
prefix, suffix = word[:4], word[4:]
D[prefix] += suffix + b' '
使用这种方法，使用的内存space比实际数据还要小（我测试了30M的平均长度为14的字符串，使用了349MB），查询速度非常快（2 µs), 但是dict的初始创建时间有点高
我也尝试过使用 dict values = list of suffixes，但它更多 RAM-consuming。