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

StackOverflow https://stackoverflow.com/questions/4026359

题

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

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

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

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

有帮助吗？

解决方案 10

因为我找不到任何现有的解决方案，这将紧紧包的记忆，我已经决定要实现它的下自己。看到我设计的开放地址中的问题。

其他提示

确定，污垢简单的方法。

使用一个python字典的数据结构。我填一个Python字典100万随机键值对，其中关键是80个字符和值200个字符。花了360844 KB我的电脑，这是你的不超过300 MB的规范之外，但我给它作为一个解决方案呢，因为它仍然是相当的内存效率。

这也失败的具有C API的要求。我不知道为什么你需要C，但因为这个问题被标记Python和缺少一个C标签，我会提供纯Python，看它是否只是可能适合该法案。

关于持久性。使用cPickle的模块。它的速度非常快，并再次，污垢简单。为了节省您的字典：

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

要重新加载您的词典：

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

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

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

如果你不打算有大量的删除，那么这并不难。删除导致碎裂。

您还需要承诺一个固定长度密钥。你提到的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（键））向右走，这是会节省你在膨胀过程中一些复制）。

但不要害怕，一旦它的启动和运行，表现相当不错。现代CPU实际上是相当擅长围绕复制的存储器100M块。

正如顺便说一句，我只是做了一件喜欢这个在Java中。在64位JVM，地图与25M的条目是2G的内存。我的解决方案（使用类似的技术来此）在600M左右）。 Java使用比C更多的指针，但前提是相同的。

您是否尝试过使用一个简单的字典？大部分数据是字符串，所以开销可能适合你的要求的范围内。

您可以使用键而不是密钥本身的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

关闭足够？它的蟒，而不是C

后来：同样，如果你的数据是有些多余，你可以gzip值。这是一个时间与空间的权衡。

使用源码是个好主意。一个快的执行可以告诉你，如果你是 不够快 与少的努力。

如果你确定你有推出自己的，我会建议如下：

如何可以预测的数量的对，或上限是什么？
如何可以预测的总数据的大小，或上限是什么？

竞技场分配 为串和节点。(通常，你想工作上的一个列表中的领域，所以你不必预测的总额大小)。

对准取决于你的算法，在原则上你可以包字节的密，只有开销是你的超限量，其中只有少会影响你的工作组。

但是，如果你有任何cmp/复制等。操作这些字符串中，请记住，有以下保证，你可以挤一点或是从这些字符串行动：

  • 所有的元素都是CPU字对齐
  • 所有垫字节(例如)0
  • 你可以放心地阅读"超越"一字符串结束，因为只要你不跨越边界的CPU

哈希表 对于该指数。一个典会的工作，但这才有意义，如果潜在的退化/重复将是一个严重的问题。我不知道任何"证券"hashtable实现C，但是应该有一个，对吗？对吗?只是替换的拨款要求的舞台上，分配器。

记忆的地方

如果你可以保证，查询将不会请求的一串，不在地图，你应该商店的钥匙在一个单独的竞技场，因为它们需要只在哈希冲突。这可以改善的存储地点明显。(在这种情况下，如果你曾经有一个"最终"的表格，你甚至可以复制的碰撞键到一个新的竞技场，而且抛弃所有其他人。惠益可能微不足道，虽然。)

分离可能帮助或损害，这取决于你访问的模式。如果你通常使用的价值一旦后，每个查找，具有它们对在相同的竞技场是巨大的。如果你如看起来几键，然后使用他们的价值观反复，单独的领域有意义的。

如果你要支持"有趣的人物"/Unicode，恢复正常你的琴弦之前，存放它们。

你可以使用的结构模块组的二进制数据以及解开它的时候需要。你可以实现一个高效率的存储器储存使用这种方法。我想访问将是一个痛苦。

Apache可移植运行时（又名APR）具有c基于哈希表。您可以在 http://apr.apache.org/docs/apr/看到文档0.9 / GROUP_ 的apr _hash.html

使用apr_hash_t你存储为void *。因此，它可以让你值完全控制。因此，如果你想你可以存储指向一个100字节块而不是字符串的实际长度。

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

还，

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

许可以下： CC-BY-SA 和 归因
不隶属于 StackOverflow
scroll top