Python（或 C）中内存高效的字符串到字符串映射

Question

我需要一个内存高效的数据结构来存储大约一百万个键值对，其中键是大约 80 字节的字符串，值是大约 200 字节的字符串，键和值的总大小约为 280MB。我还需要通过键（最好是哈希映射）有效查找值。内存开销应尽可能小，例如，对于 280MB 的有用数据，数据结构不应使用超过 300MB 的虚拟内存（包括 malloc() 开销和其他所有内容）。使用模式如下：我们从一个空数据结构开始，然后逐渐填充它，从不更改键，也从不更改值的长度。作为一个优点，数据结构可以支持更改值的长度，但代价是 100% 的值开销（意味着对于 x 值字节，x 字节可能会暂时浪费在未使用的缓冲区空间中）。

我需要一个纯 Python 模块，或内置 Python 模块，或最好带有 (C)Python 绑定的 C 实现。我希望能够将整个数据结构序列化到磁盘，并非常快速地读回。

为了证明如此小的开销是可能的，我使用开放寻址创建了一个简单的设计，包含 125 万个元素的哈希表，包含指向 1MB 数据块的 4 字节指针，数据块包含的键和值长度为 base-128 变种。这种设计有一个重要的限制：它不允许在不浪费内存区域的情况下删除或更改对。根据我对 100 万个键值对（每个键值对 280 字节）的计算，开销小于 3.6%（10 080 000 字节）。上述限制更为宽松，它们允许 20 000 000 字节的开销。

我刚刚发现 http://www.pytables.org/ ，它提供快速访问和内存效率数据打包。我必须更仔细地检查它，看看它是否适合我的需要。

Answer 1

好的，非常简单的方法。

使用Python字典作为数据结构。我用 100 万个随机键值对填充了一个 Python 字典，其中键为 80 个字符，值为 200 个字符。在我的计算机上，它占用了 360,844 Kb，这超出了不超过 300 MB 的规格，但无论如何我都将其作为解决方案提供，因为它仍然具有相当高的内存效率。

这也满足了您对 C API 的要求。我不确定你为什么需要 C，但由于问题被标记为 Python 并且缺少 C 标记，我将提供纯 Python 来看看它是否符合要求。

关于坚持。使用 cPickle 模块。它非常快，而且非常简单。保存你的字典：

cPickle.dump(mydict, "myfile.pkl")

重新加载你的字典：

mydict = cPickle.load("myfile.pkl")

第二个简单的想法是使用 shelve 模块，它基本上是基于磁盘的 python 字典。内存开销非常低（全部在磁盘上）。但它也慢得多。

Answer 2

Martijn 在评论中提到了这一点（不知道为什么人们会用答案来评论），但我同意：使用 SQLite。您应该尝试一下，看看它是否能满足您的需求。

Answer 3

如果您不打算进行大量删除，那么这并不难。删除会导致碎片。

您还需要承诺固定长度的密钥。你提到了80字节。您的钥匙允许复制吗？如果没有，那就更容易了。

所以，这就是你要做的。

您创建一个数组：

struct {
    char value[80];
    char *data;
} key;

并保持该数组已排序。

如果你的键可以重复，那么你需要：（

struct link {
    char *data;
    link *next;
}

struct {
    char value[80];
    link *data;
} key;

我的C很生锈，但这就是它的要点）后者让每个键都指向一个值的链接列表。

那么查找就是简单的二分查找。 “痛苦”在于维护这个数组和插入/删除键。它并不像听起来那么痛苦，但它节省了大量内存，尤其是在 64 位系统上。

你想要减少的是指针的数量。当您有大量充满指针的结构时，指针的成本很高。在64位系统上，一个指针有8个字节。因此，对于单个指针，需要 8MB 的内存预算。

因此，费用在于构建数组、复制和压缩内存（如果您“知道”您将有一百万行并且可以承诺这一点，那么立即 malloc(1000000 * sizeof(key)) ，它将节省您的时间扩展期间进行一些复制）。

但不要害怕，一旦启动并运行，性能就相当不错了。现代 cpu 实际上非常擅长复制 100M 内存块。

顺便说一句，我刚刚在 Java 中做了类似的事情。在 64 位 JVM 上，具有 25M 条目的 Map 需要 2G RAM。我的解决方案（使用与此类似的技术）大约有 600M）。 Java比C使用更多的指针，但前提是相同的。

Answer 4

您是否尝试过使用简单的字典？您的大部分数据都是字符串，因此开销可能符合您的要求。

Answer 5

您可以使用密钥的 sha1 而不是密钥本身。如果密钥是唯一的，那么密钥的 sha1 哈希值也可能是唯一的。它可以节省内存，以尽量低于您的限制。

from random import choice
from string import letters
from hashlib import sha1

def keygen(length):
    return "".join(choice(letters) for _ in xrange(length))

def gentestdata(n=1000*1000):
    # return dict((sha1(keygen(80)).digest(), keygen(200)) for _ in xrange(n))
    d = {}
    for _ in xrange(n):
        key = sha1(keygen(80)).digest()
        assert key not in d
        value = keygen(200)
        d[key] = value
    return d

if __name__ == '__main__':
    d = gentestdata()

在我的 ubuntu 机器上，内存最高为 304 MB：

2010-10-26 14:26:02 hbrown@hbrown-ubuntu-wks:~$ ps aux | grep python
[...]
hbrown   12082 78.2  7.5 307420 303128 pts/1   S+   14:20   4:47 python

足够接近了吗？它是 python，而不是 C。

---

稍后：另外，如果您的数据有些冗余，您可以对值进行 gzip 压缩。这是时间与空间的权衡。

Answer 6

使用 SQLite 是一个好主意。快速实施可以告诉您是否足够快，只需付出很少的努力。

---

如果您确定必须自己推出，我会建议您执行以下操作：

您可以如何准确地预测对的数量或上限？
您能否准确地预测总数据大小或其上限？

用于字符串和节点的 Arena 分配器。 （通常，您会处理一系列竞技场，因此您不必预测总大小）。

对齐取决于您的算法，原则上您可以将其打包为字节紧的，唯一的开销是您的过度分配，这对您的工作集影响很小。

但是，如果您必须对这些字符串运行任何 cmp/copy 等操作，请记住，通过以下保证，您可以从这些字符串操作中压缩一点或很多：

• 所有元素都是 CPU 字对齐的，
• 所有填充字节都是对齐的（例如) 0
• 只要不跨越

---

索引的 CPU 边界哈希表，您就可以安全地读取“超出”字符串结尾。字典也可以，但只有当潜在的退化/重新散列是一个严重的问题时才有意义。我不知道 C 语言有任何“库存”哈希表实现，但应该有一个，对吧？正确的？只需用对 arena 分配器的调用替换分配即可。

---

内存局部性

如果您可以保证查找永远不会请求映射中不存在的字符串，则应该将键存储在单独的区域中，因为仅在哈希冲突时才需要它们。这可以显着提高内存局部性。 （在这种情况下，如果你有一张“最终”牌桌，你甚至可以将冲突的键复制到一个新的竞技场，并扔掉所有其他键。不过，这样做的好处可能微乎其微。）

分离可能会有所帮助或有害，取决于您的访问模式。如果您通常在每次查找后使用该值一次，那么将它们成对地放在同一区域中就很好了。例如，如果您查找几个键，然后重复使用它们的值，则单独的区域是有意义的。

---

如果您必须支持“有趣的字符”/Unicode，请在存储字符串之前对其进行规范化。

Answer 7

您可以使用 struct 模块来打包二进制数据并在需要时将其解包。
您可以使用这种方法实现内存高效存储。我想访问会很痛苦。

• http://docs.python.org/library/struct.html

Answer 8

Apache Portable Runtime（又名 APR）有一个基于 C 的哈希表。您可以在 http://apr.apache.org/docs/apr/ 查看文档0.9/group_apr_hash.html

使用apr_hash_t，您存储的所有内容都是无效的*。因此，它使您可以完全控制价值观。因此，如果您愿意，您可以存储指向 100 字节块的指针，而不是字符串的实际长度。

Answer 9

Judy 应该节省内存：http://judy.sourceforge.net/
（基准：http://www.nothings.org/computer/judy/，请参阅“数据结构大小”）。
请参阅：http://www.dalkescientific.com/Python/PyJudy.html

另 ，

对于固定大小的键，有 http://panthema.net/2007/stx-btree/< /a> 在 C++ 中（我确信使用自定义 C 包装器可以从 CPython 使用它）。
如果数据集允许，您可以将变长键存储在值中，并使用变长键的哈希或前缀作为固定长度键。

同样的逻辑也适用于 http: //google-opensource.blogspot.ru/2013/01/c-containers-that-save-memory-and-time.html 和 http://code.google.com/p/sparsehash/ - 不要使用繁重的 std::string 作为密钥，而是使用 32 位或 64 位 -位整数密钥，使其以某种方式来自真实的可变长度密钥。

Answer 10

由于我找不到任何现有的解决方案可以紧密地压缩内存，所以我决定自己用 C 语言实现它。请参阅我在问题中使用开放寻址的设计。