Python(或C)中的内存高效字符串到字符串映射

好吧,简单的方法。

对数据结构使用python字典。我在python字典中填充了100万个随机键值对,其中键是80个字符,值是200个字符。我的电脑占用了360844kb,这超出了你不超过300mb的规格,但我还是提供了一个解决方案,因为它仍然非常节省内存。

关于坚持。使用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(key))将立即在扩展期间为您节省一些复制)。

但不要害怕,一旦它启动运行,性能相当不错。现代的CPU实际上非常擅长复制100万块左右的内存。

作为旁白,我在Java中做了类似的事情。在64位JVM上,具有25M条目的映射是2G的RAM。我的解决方案(使用与此类似的技术)大约有600米。Java使用的指针比C多,但前提是相同的。

你试过用直截了当的口述吗?大多数数据都是字符串,因此开销可能符合您的要求。

sha1 而不是钥匙本身。如果密钥是唯一的,则 沙阿1 密钥的散列也很可能。它提供了一个内存节省,试图在您的限制下吱吱叫。

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盒子里,这是304mb的内存:

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 价值观。这是一个时间与空间的权衡。

足够快 不费吹灰之力。

你能多好地预测成对的数目,或是一个上限?
你能多好地预测总数据量,或是它的上限?

Arena allocator 用于字符串和节点。(通常,你会在竞技场列表上工作,因此不必预测总规模)。

对齐取决于你的算法,原则上你可以把它压缩成字节,唯一的开销是你的过度分配,这只会对你的工作集产生最小的影响。

但是,如果必须对这些字符串运行任何cmp/copy等操作,请记住,有了以下保证,您可以从这些字符串操作中挤出一点或很多:

• 所有pad字节都是(例如)0
• 只要不越过CPU边界,就可以安全地读取字符串末尾的“beyond”

哈希表

记忆局部性

如果可以保证查找永远不会请求不在映射中的字符串,则应将密钥存储在单独的竞技场中,因为只有在散列冲突时才需要它们。这能显著改善记忆的局部性。(在这种情况下,如果你有一张“最终”的桌子,你甚至可以把碰撞的钥匙复制到一个新的竞技场,然后扔掉所有其他的。不过,这样做的好处可能微乎其微。)

分离可以帮助也可以伤害,这取决于您的访问模式。如果您通常在每次查找后使用一次该值,那么让它们在同一竞技场中成对使用是很好的。例如,如果您查找几个键,然后重复使用它们的值,则可以使用单独的arenas。

如果必须支持“有趣的字符/Unicode”,请在存储字符串之前将其规范化。

使用这种方法可以实现内存高效的存储。我想进入会很痛苦。

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

Apache可移植运行时(aka APR)有一个基于c的哈希表。您可以在 http://apr.apache.org/docs/apr/0.9/group_ apr _hash.html

有了apr_hash_t,你所储存的一切都是空的*。所以它能让你完全控制价值观。因此,如果需要,可以存储指向100字节块的指针,而不是字符串的实际长度。

朱迪应该有记忆力: 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/ -istead使用一个重std::string作为键,使用一个32位或64位整数键,使其以某种方式从实际的可变长度键。

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