V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
推荐学习书目
Learn Python the Hard Way
Python Sites
PyPI - Python Package Index
http://diveintopython.org/toc/index.html
Pocoo
值得关注的项目
PyPy
Celery
Jinja2
Read the Docs
gevent
pyenv
virtualenv
Stackless Python
Beautiful Soup
结巴中文分词
Green Unicorn
Sentry
Shovel
Pyflakes
pytest
Python 编程
pep8 Checker
Styles
PEP 8
Google Python Style Guide
Code Style from The Hitchhiker's Guide
Phishion
V2EX  ›  Python

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

  •  
  •   Phishion · 2021-05-23 16:45:49 +08:00 · 8073 次点击
    这是一个创建于 1040 天前的主题,其中的信息可能已经有所发展或是发生改变。

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

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

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

    50 条回复    2021-05-24 17:26:11 +08:00
    ZhangZisu
        1
    ZhangZisu  
       2021-05-23 16:56:46 +08:00   ❤️ 3
    理论只要 (64+4)*1000000/1024/1024~=64M
    考虑直接 c 手写 trie 实现。若为 base64,前 2 位建树,挂链表。时间复杂度 O(64),占用空间比 64m 大个 2m ( 64*64*64*8/1024/1024 )
    Phishion
        2
    Phishion  
    OP
       2021-05-23 16:59:16 +08:00
    @ZhangZisu 有点高级,有适合新手的什么经过优化的包之类的么?大概 100 多 M 我就非常能接受了
    ZhangZisu
        3
    ZhangZisu  
       2021-05-23 17:12:57 +08:00
    @ZhangZisu 说错了,应该是用前三个字符建树,复杂度是 O(64*3)(平均链表长度为 3 )。

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

    或者直接上 redis
    yuelang85
        4
    yuelang85  
       2021-05-23 17:23:28 +08:00
    上 redis,用 redis 的字典功能
    Phishion
        5
    Phishion  
    OP
       2021-05-23 17:25:37 +08:00
    @yuelang85 我就为这事儿跑一个 redis 感觉划不来啊,这东西本身也有资源开销吧?
    ZhangZisu
        6
    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
        7
    yuelang85  
       2021-05-23 17:40:39 +08:00
    @Phishion 确实是有资源开销,你可以先开一个大点儿的 redis,看看你的这些数据占用多少内存,然后再把 redis 库上限改小。

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

    python 的字典维护的不是单纯的数据,而是对象。python 所有数据类型都是对象
    kxjhlele
        8
    kxjhlele  
       2021-05-23 17:40:41 +08:00 via Android
    要是我的话 直接用 map,字典又不需要频繁更新,用 kv 有点浪费
    BiggerLonger
        9
    BiggerLonger  
       2021-05-23 17:42:52 +08:00
    尝试一下 nametuple 或者 data class, 应该能缩减个两三倍()
    crclz
        10
    crclz  
       2021-05-23 17:57:44 +08:00
    关系型数据库
    yuelang85
        11
    yuelang85  
       2021-05-23 18:00:58 +08:00
    @Phishion 哦哦,抱歉,我看到你说字典,就默认认为是 python 下了。
    ericls
        12
    ericls  
       2021-05-23 18:02:36 +08:00
    拿时间换 存个 list 就 8M ?
    ericls
        13
    ericls  
       2021-05-23 18:02:57 +08:00
    jk
    no1xsyzy
        14
    no1xsyzy  
       2021-05-23 18:04:55 +08:00
    写 C 扩展拿时间换,每次都额外进行一次 PyString -> c_string 的解包和 int -> PyInt 的回流。
    优化到语言提供的基础类型就行了,再大就是各种数据库
    DevRoss
        15
    DevRoss  
       2021-05-23 18:06:29 +08:00 via Android
    lmdb
    cmdOptionKana
        16
    cmdOptionKana  
       2021-05-23 18:10:29 +08:00
    sqlite yyds
    love
        17
    love  
       2021-05-23 18:10:48 +08:00
    字串比较长啊,可以用压缩技术压一下会省很多了
    yangyaofei
        18
    yangyaofei  
       2021-05-23 20:01:55 +08:00
    输出是数字? 直接写个神经网络训练一下呢?
    eason1874
        19
    eason1874  
       2021-05-23 20:18:52 +08:00
    用时间换空间+1,内存放不下干脆不放了,就用文件。如果可以分冷热就把热的部分放内存。
    rrfeng
        20
    rrfeng  
       2021-05-23 20:26:43 +08:00
    只能 trie 了,如果生成后没有修改只有查询,可以试试 slimtrie,可能是最省空间的了。
    levelworm
        21
    levelworm  
       2021-05-23 21:08:19 +08:00
    小白求问:
    1. 32 位可以吗?
    2. 如果用 binary 可以吗?
    Phishion
        22
    Phishion  
    OP
       2021-05-23 21:57:01 +08:00
    谢谢大伙儿,我研究研究
    mattx
        23
    mattx  
       2021-05-23 23:21:42 +08:00
    @cmdOptionKana
    @DevRoss
    @no1xsyzy
    @ZhangZisu 使用 文件数据库是否内存会更少,leveldb lmdb sqlite 之类的。
    lujjjh
        24
    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
        25
    lujjjh  
       2021-05-23 23:47:13 +08:00
    更正 [md5(s), int] → [(md5(s), int)],或者写成 list<(md5(s), int)>
    no1xsyzy
        26
    no1xsyzy  
       2021-05-24 00:30:17 +08:00   ❤️ 1
    突然想到
    >>> 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
        27
    no1xsyzy  
       2021-05-24 00:37:43 +08:00
    @mattx 显然的,就是进一步用时间换空间了,你不嫌慢放对象存储甚至冷存储都没关系(
    ipwx
        28
    ipwx  
       2021-05-24 00:59:59 +08:00   ❤️ 4
    @ZhangZisu 我觉得楼主这个需求,trie 树不太好用。因为楼主的字符串是真随机,trie 树每层都会分出一堆节点,基本是个满 K 叉树,比一个大哈希表用更多内存
    ericls
        29
    ericls  
       2021-05-24 03:47:22 +08:00 via iPhone
    @no1xsyzy TIL. Thanks!
    aijam
        30
    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
        31
    ZhangZisu  
       2021-05-24 07:38:39 +08:00
    @ipwx 对,是一个大哈希表更好。

    如果完整建 trie 是难以承受的。如果只建前几层,后面挂链表遍历,空间时间权衡一下应该也还行。
    ericguo
        32
    ericguo  
       2021-05-24 08:01:45 +08:00   ❤️ 2
    这不就是 GDBM 的作用么。。https://cloud.tencent.com/developer/section/1366972
    des
        33
    des  
       2021-05-24 09:11:56 +08:00 via iPhone
    @ZhangZisu 后边挂链表的话,前面还是用 hashcode 比较好
    因为如果字符串不随机的话,有可能会出现超长链表
    wellsc
        34
    wellsc  
       2021-05-24 09:15:39 +08:00
    @Phishion 肯定比 Python 的字典省资源,还有 redis 自己的高可用方案
    jorneyr
        35
    jorneyr  
       2021-05-24 09:22:01 +08:00
    自己实现一个 LRU 缓存算法,不需要一次把所有的都加入内存
    ipwx
        36
    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
        37
    MoYi123  
       2021-05-24 10:53:12 +08:00
    用 karp-rabin 怎么样? 一个字符串可以压成 int32. 缺点是会丢失原始字符串.
    kksco
        38
    kksco  
       2021-05-24 11:10:14 +08:00
    用 go 。。python 分配一个变量就 24 byte 打底了,太恐怖了
    leimao
        39
    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
        40
    leimao  
       2021-05-24 12:26:00 +08:00 via iPhone
    我自己虽然在 Python 和 C++都没写过,但印象中 C++可以自己写 hash,你可以查查相关资料。最简单的就是你这个 hash table size 只有 1,直接退化成 list 。
    leimao
        41
    leimao  
       2021-05-24 12:29:07 +08:00 via iPhone
    反正我觉得讨论这个怪怪的,可能我平时不做这方面的东西不 care 这个吧
    lujjjh
        42
    lujjjh  
       2021-05-24 12:34:40 +08:00   ❤️ 1
    既然没有人贴代码,我就先抛砖引玉了。19 MB,二分查找。

    https://gist.github.com/lujjjh/fecf55f6827cce011bb71682e9b8594a
    leimao
        43
    leimao  
       2021-05-24 12:37:37 +08:00
    @lujjjh 一楼计算过最少 64MB,你 19MB 怎么出来的?
    lujjjh
        44
    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
        45
    tairan2006  
       2021-05-24 13:38:42 +08:00   ❤️ 1
    用时间换空间…

    那你直接存 sqlite 里不就完了…
    ipwx
        46
    ipwx  
       2021-05-24 14:34:18 +08:00
    @lujjjh 哈希只能是概率性不冲突啊,虽然概率小,但是不能保证程序**一定**正确不是么?

    楼主没有讲可以概率性正确,你这就加上这个条件,这不好。
    est
        47
    est  
       2021-05-24 14:45:44 +08:00
    这字符一看就是 base64 转成二进制还能更小
    lujjjh
        48
    lujjjh  
       2021-05-24 15:50:52 +08:00
    @ipwx 没法保证程序**一定**正确,内存也有概率出错 :doge:

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

    当然,肯定是有场景不满足于这个概率的,但这种场景我想不会在意 64 MB 内存的。
    ipwx
        49
    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
        50
    lujjjh  
       2021-05-24 17:26:11 +08:00
    @ipwx 不同量级的数据解决方案是不同的,8*10^17 跟 10^6 量级相差巨大,最优的解决方案也不一样。

    另外这里不适合直接套用生日问题的结论,因为表里的数据是已知的,表里面是否有冲突在建表的时候就可以知道。我计算的是在保证表里面的数据不存在冲突的情况下,查询任何一个 key',其 hash(key') ∈ T 且 key' ≠ key 的概率。
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   955 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 32ms · UTC 21:47 · PVG 05:47 · LAX 14:47 · JFK 17:47
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.