3

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

我需要一个纯 Python 模块，或者一个内置的 Python 模块，或者一个最好带有 (C)Python 绑定的 C 实现。如果有可能将整个数据结构序列化到磁盘，并且可以非常快速地读回它，我会更喜欢。

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

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

4

10 回答 10

7

好的，简单的方法。

使用 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 字典。内存开销非常低（都在磁盘上）。但它也慢得多。

于 2010-10-26T18:39:08.530 回答
6

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

于 2010-10-26T17:53:40.500 回答
6

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

您还需要提交固定长度的密钥。你提到了 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 多，但前提是一样的。

于 2010-10-26T18:03:27.000 回答
5

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

于 2010-10-26T17:55:34.150 回答
2

您可以使用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使用这些值。这是时间与空间的权衡。

于 2010-10-26T18:28:40.713 回答
2

使用 SQLite 是个好主意。快速实施可以告诉您是否足够快且不费吹灰之力。

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

你能预测成对的数量或上限吗？
你能在多大程度上预测总数据大小或上限？

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

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

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

  • 所有元素都是 CPU 字对齐的
  • 所有填充字节都是（例如）0
  • 只要您不越过 CPU 边界，您就可以安全地阅读“超出”字符串结尾的内容

索引的哈希表。字典也可以，但只有在潜在的降级/重新散列是一个严重问题时才有意义。我不知道 C 的任何“库存”哈希表实现，但应该有一个，对吧？对？只需将分配替换为对 arena 分配器的调用即可。

内存局部性

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

根据您的访问模式，分离可以帮助或伤害。如果您通常在每次查找后使用该值一次，那么将它们成对地放在同一个舞台上是很棒的。如果您例如查找几个键，然后重复使用它们的值，那么单独的竞技场是有意义的。

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

于 2010-10-26T20:10:47.997 回答
1

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

于 2010-10-26T17:45:35.883 回答
1

Apache Portable Runtime (aka APR) 有一个基于 c 的哈希表。您可以在http://apr.apache.org/docs/apr/0.9/group_apr_hash.html查看文档

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

于 2010-10-26T18:01:43.670 回答
1

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

还，

对于固定大小的键，C++ 中有http://panthema.net/2007/stx-btree/（我确信使用自定义 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 位整数密钥，使其以某种方式来自真正的可变长度密钥。

于 2013-02-04T22:10:24.547 回答
0

由于我找不到任何现有的解决方案可以紧紧地打包内存，我决定自己用 C 语言实现它。在问题中查看我的开放寻址设计。

于 2010-11-13T11:12:56.903 回答