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

[Phishion]

字典大概是下面这样的结构，我粗跑了一下，大概 100W 条数据，占用 400M 内存

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

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

[ZhangZisu]

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

[Phishion]

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

[ZhangZisu]

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

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

或者直接上 redis

[yuelang85]

上 redis，用 redis 的字典功能

[Phishion]

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

[ZhangZisu]

直接用 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]

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

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

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

[kxjhlele]

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

[BiggerLonger]

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

[crclz]

关系型数据库

[yuelang85]

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

[ericls]

拿时间换 存个 list 就 8M ？

[ericls]

jk

[no1xsyzy]

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

[DevRoss]

lmdb

[cmdOptionKana]

sqlite yyds

[love]

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

[yangyaofei]

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

[eason1874]

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

[rrfeng]

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