我想维护一个大型字典，有没有什么省内存的方法

{'dn0pFVBjQGwRYKCO2Ix45ibo6r9kW3Zedn0pFVBjQGwRYKCO2Ix45ibo6r9kW3Ze': 1, 'XuYRUn50f7j9zG2k8EZvoaWmeAdqTVrQXuYRUn50f7j9zG2k8EZvoaWmeAdqTVrQ': 2, 
....
't2n9wLoU53ql4hPMHi7pFaIEkCRxNuf0t2n9wLoU53ql4hPMHi7pFaIEkCRxNuf0',1000000}

有没有方法能大幅度减少内存的占用？

字典

内存

占用

大概

50 条回复 • 2021-05-24 17:26:11 +08:00

ZhangZisu

2021-05-23 16:56:46 +08:00

理论只要 (64+4)*1000000/1024/1024~=64M
考虑直接 c 手写 trie 实现。若为 base64，前 2 位建树，挂链表。时间复杂度 O(64)，占用空间比 64m 大个 2m （ 64*64*64*8/1024/1024 ）

Phishion

2021-05-23 16:59:16 +08:00

@ZhangZisu 有点高级，有适合新手的什么经过优化的包之类的么？大概 100 多 M 我就非常能接受了

ZhangZisu

2021-05-23 17:12:57 +08:00

@ZhangZisu 说错了，应该是用前三个字符建树，复杂度是 O(64*3)(平均链表长度为 3 ）。

不过直接用 C++的 hashmap 应该就够了。（或者 map ）

或者直接上 redis

yuelang85

2021-05-23 17:23:28 +08:00

上 redis，用 redis 的字典功能

Phishion

2021-05-23 17:25:37 +08:00

@yuelang85 我就为这事儿跑一个 redis 感觉划不来啊，这东西本身也有资源开销吧？

ZhangZisu

2021-05-23 17:39:43 +08:00

直接用 stl 就够了。

C++ unordered_map: 150MB
C++ map: 155MB
```cpp
std::unordered_map<std::string, int> hmap;
// std::map<std::string, int> hmap;

const char *charset = "1234567890abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ+=";

int main()
{
for (int i = 0; i < 1000000; i++)
{
std::string str;
for (int j = 0; j < 64; j++)
str += charset[(int)(1. * rand() / RAND_MAX * 64)];
int val = rand();
hmap[str] = val;
}
int mem = getValue();
printf("Total memory in KB: %d\n", mem);
return 0;
}

```

yuelang85

2021-05-23 17:40:39 +08:00

@Phishion 确实是有资源开销，你可以先开一个大点儿的 redis，看看你的这些数据占用多少内存，然后再把 redis 库上限改小。

可以对比下二者哪个合适。我以前 python 维护过大的多层级 dict，占用内存很多的，不知道你这个一层结构会怎样。

python 的字典维护的不是单纯的数据，而是对象。python 所有数据类型都是对象

kxjhlele

2021-05-23 17:40:41 +08:00 via Android

要是我的话直接用 map，字典又不需要频繁更新，用 kv 有点浪费

BiggerLonger

2021-05-23 17:42:52 +08:00

尝试一下 nametuple 或者 data class, 应该能缩减个两三倍()

crclz

2021-05-23 17:57:44 +08:00

关系型数据库

yuelang85

2021-05-23 18:00:58 +08:00

@Phishion 哦哦，抱歉，我看到你说字典，就默认认为是 python 下了。

ericls

2021-05-23 18:02:36 +08:00

拿时间换存个 list 就 8M ？

ericls

2021-05-23 18:02:57 +08:00

no1xsyzy

2021-05-23 18:04:55 +08:00

写 C 扩展拿时间换，每次都额外进行一次 PyString -> c_string 的解包和 int -> PyInt 的回流。
优化到语言提供的基础类型就行了，再大就是各种数据库

DevRoss

2021-05-23 18:06:29 +08:00 via Android

lmdb

cmdOptionKana

2021-05-23 18:10:29 +08:00

sqlite yyds

love

2021-05-23 18:10:48 +08:00

字串比较长啊，可以用压缩技术压一下会省很多了

yangyaofei

2021-05-23 20:01:55 +08:00

输出是数字? 直接写个神经网络训练一下呢?

eason1874

2021-05-23 20:18:52 +08:00

用时间换空间+1，内存放不下干脆不放了，就用文件。如果可以分冷热就把热的部分放内存。

rrfeng

2021-05-23 20:26:43 +08:00

只能 trie 了，如果生成后没有修改只有查询，可以试试 slimtrie，可能是最省空间的了。

levelworm

2021-05-23 21:08:19 +08:00

小白求问：
1. 32 位可以吗？
2. 如果用 binary 可以吗？

Phishion

2021-05-23 21:57:01 +08:00

谢谢大伙儿，我研究研究

mattx

2021-05-23 23:21:42 +08:00

@cmdOptionKana
@DevRoss
@no1xsyzy
@ZhangZisu 使用文件数据库是否内存会更少，leveldb lmdb sqlite 之类的。

lujjjh

2021-05-23 23:44:34 +08:00

看要根据 key 查 value，还是需要遍历，如果只需要根据 key 查 value：
1. 用 md5(s) 代替 s，碰撞理论上可忽略，64 bytes → 16 bytes (binary)
2. map<md5(s), int> 变成 [md5(s), int]，按照 md5(s) 排序，100 万条数据二分查找 20 次以内

lujjjh

2021-05-23 23:47:13 +08:00

更正 [md5(s), int] → [(md5(s), int)]，或者写成 list<(md5(s), int)>

no1xsyzy

2021-05-24 00:30:17 +08:00

突然想到
>>> sys.getsizeof("")
49
>>> sys.getsizeof(1)
28
这个开销本身就有点高啊，单建立对象的开销就比你要存的内容高了……

@ericls 你是不是直接 sys.getsizeof([...big list...]) 了？ Python 下对容器对象用这个方法只会计算容器本身和其中存储的引用的大小，而不包括被引用对象的大小。
>>> sys.getsizeof(["a"*2**10])
64
>>> sys.getsizeof("a"*2**10)
1073

no1xsyzy

2021-05-24 00:37:43 +08:00

@mattx 显然的，就是进一步用时间换空间了，你不嫌慢放对象存储甚至冷存储都没关系（

ipwx

2021-05-24 00:59:59 +08:00

@ZhangZisu 我觉得楼主这个需求，trie 树不太好用。因为楼主的字符串是真随机，trie 树每层都会分出一堆节点，基本是个满 K 叉树，比一个大哈希表用更多内存

ericls

2021-05-24 03:47:22 +08:00 via iPhone

@no1xsyzy TIL. Thanks!

aijam

2021-05-24 04:37:47 +08:00

可以试试这个
https://github.com/google/pygtrie

```
>>> t = pygtrie.CharTrie()
>>> t['dn0pFVBjQGwRYKCO2Ix45ibo6r9kW3Zedn0pFVBjQGwRYKCO2Ix45ibo6r9kW3Ze'] = 1
>>> t['XuYRUn50f7j9zG2k8EZvoaWmeAdqTVrQXuYRUn50f7j9zG2k8EZvoaWmeAdqTVrQ'] = 2
>>> t['dn0pFVBjQGwRYKCO2Ix45ibo6r9kW3Zedn0pFVBjQGwRYKCO2Ix45ibo6r9kW3Ze']
1
>>> t['XuYRUn50f7j9zG2k8EZvoaWmeAdqTVrQXuYRUn50f7j9zG2k8EZvoaWmeAdqTVrQ']
2
```

ZhangZisu

2021-05-24 07:38:39 +08:00

@ipwx 对，是一个大哈希表更好。

如果完整建 trie 是难以承受的。如果只建前几层，后面挂链表遍历，空间时间权衡一下应该也还行。

ericguo

2021-05-24 08:01:45 +08:00

这不就是 GDBM 的作用么。。https://cloud.tencent.com/developer/section/1366972

des

2021-05-24 09:11:56 +08:00 via iPhone

@ZhangZisu 后边挂链表的话，前面还是用 hashcode 比较好
因为如果字符串不随机的话，有可能会出现超长链表

wellsc

2021-05-24 09:15:39 +08:00

@Phishion 肯定比 Python 的字典省资源，还有 redis 自己的高可用方案

jorneyr

2021-05-24 09:22:01 +08:00

自己实现一个 LRU 缓存算法，不需要一次把所有的都加入内存

ipwx

2021-05-24 10:16:06 +08:00

@ZhangZisu 但其实哈希表用平方探测不是只要两倍内存就基本能保证性能么。。而且两倍的是哈希表节点而不是字符串。用上 StringPool + string_view 咱觉得基本就是最好的方案了。

@Phishion 咱多少觉得，楼主有种 XY Problem 的感觉。到底什么场景下 400MB 的表都会 concern ？是不是和多进程有关？ Linux fork 的话，因为内存使用是 COW 的，所以可以主进程创建完整个表，然后子进程就不用创建第二份了。

那如果是设备内存太小，或者本身楼主要处理的不是 400MB 而是 40GB 这种场景，那可能就需要使用 disk-backend 的数据结构了。比如 B-Tree 。

MoYi123

2021-05-24 10:53:12 +08:00

用 karp-rabin 怎么样? 一个字符串可以压成 int32. 缺点是会丢失原始字符串.

kksco

2021-05-24 11:10:14 +08:00

用 go 。。python 分配一个变量就 24 byte 打底了，太恐怖了

leimao

2021-05-24 12:21:47 +08:00 via iPhone

这。。。query complexity 和 memory complexity 你鱼和熊掌想要兼得是不可能的。memory 用的最少的就是一个 list，只不过你 query 起来很慢。你想要追求一个平衡点，那你就自己写个 hash table 手动把这个 hash table 的 size 弄的小一些，这样 hash conflicts 几率就高了，牺牲了 query 效率换取了部分内存。

leimao

2021-05-24 12:26:00 +08:00 via iPhone

我自己虽然在 Python 和 C++都没写过，但印象中 C++可以自己写 hash，你可以查查相关资料。最简单的就是你这个 hash table size 只有 1，直接退化成 list 。

leimao

2021-05-24 12:29:07 +08:00 via iPhone

反正我觉得讨论这个怪怪的，可能我平时不做这方面的东西不 care 这个吧

lujjjh

2021-05-24 12:34:40 +08:00

既然没有人贴代码，我就先抛砖引玉了。19 MB，二分查找。

https://gist.github.com/lujjjh/fecf55f6827cce011bb71682e9b8594a

leimao

2021-05-24 12:37:37 +08:00

@lujjjh 一楼计算过最少 64MB，你 19MB 怎么出来的？

lujjjh

2021-05-24 13:05:55 +08:00

@leimao 思路在 #24 。虽然楼主并没有把需求描述清楚（只是要根据 key 查 value，还是也需要遍历），但是 100 万的量级显然可以假设是不需要遍历的，那么 key 就不需要存原始的字符串，存 hash 就可以了。

如果需要遍历，又要让内存小于 64 MB，就需要在 key 和 value 的编码方式上做手脚了。当然，楼主不介意 64 MB，只需要把我代码里对 key 做 MD5 的逻辑删除即可。

tairan2006

2021-05-24 13:38:42 +08:00

用时间换空间…

那你直接存 sqlite 里不就完了…

ipwx

2021-05-24 14:34:18 +08:00

@lujjjh 哈希只能是概率性不冲突啊，虽然概率小，但是不能保证程序**一定**正确不是么？

楼主没有讲可以概率性正确，你这就加上这个条件，这不好。

est

2021-05-24 14:45:44 +08:00

这字符一看就是 base64 转成二进制还能更小

lujjjh

2021-05-24 15:50:52 +08:00

@ipwx 没法保证程序**一定**正确，内存也有概率出错 :doge:

如果没有算错，任意一个字符串 MD5 跟这 100 万中至少一个发生冲突的概率大概在 2^(-108)，工程上基本没什么问题，即便安全性弱如 MD5，依旧很难找出特例。

当然，肯定是有场景不满足于这个概率的，但这种场景我想不会在意 64 MB 内存的。

ipwx

2021-05-24 17:09:02 +08:00

@lujjjh 虽然你说的对，这个场景的冲突概率很低，但是并没有低到 2^(-128)。这是典型的生日问题，因为你的问题不是给定某个特定川，表里面有川和它冲突的概率，而是表里面有任意两个串冲突的概率。

https://en.wikipedia.org/wiki/Birthday_problem#Probability_table

这里写出来结论了，超过 p=0.001 有任意两个串冲突，表里面需要有 8*10^17 个元素就行。

lujjjh

2021-05-24 17:26:11 +08:00

@ipwx 不同量级的数据解决方案是不同的，8*10^17 跟 10^6 量级相差巨大，最优的解决方案也不一样。

另外这里不适合直接套用生日问题的结论，因为表里的数据是已知的，表里面是否有冲突在建表的时候就可以知道。我计算的是在保证表里面的数据不存在冲突的情况下，查询任何一个 key'，其 hash(key') ∈ T 且 key' ≠ key 的概率。