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

Question

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

我需要一个纯Python模块,或一个内置的Python模块,或一个C实现,最好是(C)Python绑定.我更喜欢是否可以将整个数据结构序列化到磁盘,并且可以非常快速地将其读回.

为了证明这么小的开销是可能的,我创建了一个带有开放寻址的简单设计,包含1个数据块的4字节指针的125万个元素的哈希表,包含密钥和值长度的数据块作为基础-128 varints.这种设计有一个重要的限制:它不允许在不浪费存储区域的情况下移除或更换线对.根据我的计算,有100万个密钥值对,每个280字节,开销小于3.6%(10 080 000字节).上述限制更加慷慨,它们允许20 000 000字节的开销.

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

Answer 1

好的,简单的方法.

使用python字典表示数据结构.我用一百万个随机键值对填充了一个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条目的映射是2G的RAM.我的解决方案(使用类似的技术)大约600M).Java使用的指针多于C,但前提是相同的.

Answer 4

你尝试过使用简单的词典吗？您的大部分数据都是字符串,因此开销可能符合您的要求.