V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
shikimoon
V2EX  ›  程序员

有上亿的词算词频怎么算比较快

  •  
  •   shikimoon · 2022-05-14 16:51:54 +08:00 · 2935 次点击
    这是一个创建于 795 天前的主题,其中的信息可能已经有所发展或是发生改变。

    有上亿的词算词频怎么算比较快,内存跟 cpu 都不是问题的话。现在就是一个大字典,词是 key ,词频是 value 。想用词的长度多加一层散列但感觉也提升不大,这些词的长度基本都在 1-5 之间

    20 条回复    2022-05-15 19:08:26 +08:00
    ipwx
        1
    ipwx  
       2022-05-14 17:11:39 +08:00
    Trie Tree 可能会快一点,但你要用 C++ 来极限优化,不然反而比 hash 更慢。
    Jooooooooo
        2
    Jooooooooo  
       2022-05-14 17:13:51 +08:00
    cpu 不是问题, 分成好多个小文件并发的去算呗.
    ipwx
        3
    ipwx  
       2022-05-14 17:14:05 +08:00   ❤️ 2
    比如,如果都是英文字母,不需要区分大小写,那你的符号表就只有 26 个字符。为了速度可以取 32 。

    既然长度都在 1~5 之间,那你用三层 Trie tree 就能有效压缩深度。每一层是 1024 个格子,取格子只要位移操作不用乘法。相当于分层快速哈希,而且必然没有冲突了。
    ipwx
        4
    ipwx  
       2022-05-14 17:15:08 +08:00
    上述操作必须用指针在那里魔法计算。。。不要用 STL 容器。不然速度还是提不上去
    shikimoon
        5
    shikimoon  
    OP
       2022-05-14 17:17:10 +08:00
    @ipwx 都是中文,trie 树应该作用不大。
    nulIptr
        6
    nulIptr  
       2022-05-14 17:17:38 +08:00
    一个字符 3 字节,一个单词 10 个字符,10 亿字符串也不到 30g 。。。我觉得字典够用
    learningman
        7
    learningman  
       2022-05-14 17:18:25 +08:00
    中文为啥不能用 trie 树,映射下多开几层
    heqing
        8
    heqing  
       2022-05-14 17:23:03 +08:00   ❤️ 1
    可以参考一下 kenlm 的实现
    abujj
        9
    abujj  
       2022-05-14 17:56:27 +08:00
    是 MapReduce 的意思吗 ?
    shikimoon
        10
    shikimoon  
    OP
       2022-05-14 18:05:40 +08:00
    @abujj 不会。。。
    shikimoon
        11
    shikimoon  
    OP
       2022-05-14 18:07:14 +08:00
    @nulIptr 是够用但是太慢
    dji38838c
        12
    dji38838c  
       2022-05-14 18:25:05 +08:00   ❤️ 1
    这不是 MapReduce 的第一课吗,赶快学学
    pengtdyd
        13
    pengtdyd  
       2022-05-14 18:26:53 +08:00
    首先排除 C 以外的其他语言,因为其他垃圾太慢了。其次就是算法和数据结构了,这个嘛,就要看个人发挥了。
    wangyu17455
        14
    wangyu17455  
       2022-05-14 20:41:00 +08:00
    map reduce
    nuistzhou
        15
    nuistzhou  
       2022-05-14 20:47:28 +08:00 via iPhone
    Mapper
    Reducer
    哈哈
    bxb100
        16
    bxb100  
       2022-05-14 21:33:44 +08:00 via Android
    单机 MapReduce 有啥用
    shm7
        17
    shm7  
       2022-05-14 21:35:58 +08:00   ❤️ 1
    GB2312 中文字就六七千个,怎么搞成上亿的词典? NLP 里面语言模型一般也就几万字,还包括很多重复的呢。
    如果就是这几千字组成的词语 /短语也算入词典的话,用沙发的方法是不是有帮助?
    ToBeHacker
        18
    ToBeHacker  
       2022-05-15 03:33:15 +08:00
    大部分都是重复的,其实字典就可以了
    Buges
        19
    Buges  
       2022-05-15 07:36:17 +08:00 via Android
    @pengtdyd 这是什么爆论,先且不说 C/Cpp/zig/Rust 等一票原生语言本身没有额外开销,性能完全取决于具体代码。C 语言在性能方面也是具有一些劣势的:
    1. 糟糕的标准库和依赖管理,很多 real world application 由于开发者为省事选择简单而非最优化的算法与实现导致性能损失。而像 Rust 这样提供方便的依赖管理,成熟且经过深度优化(复杂算法、simd 等)的库被广泛使用。
    2. 手动资源管理外加宽松约束,导致的心智负担使程序员倾向于防御性编程和不必要的复制,外加理论上对编译器优化的限制。
    3. 极大规模和复杂度的应用中 Java 等具有 JIT 的语言性能吞吐量等表现要好于 AOT 语言。(并且复杂度庞大的应用根本不可能由低级语言编写)
    4. 开发成本过高。比如绝大多数 C 编写的网络服务并发性能肯定是不如 go 的,因为后者自带,前者除了 nginx 这种谁会去费劲优化。
    pluvet
        20
    pluvet  
       2022-05-15 19:08:26 +08:00
    直接用语言自带的哈希表就够了
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   1236 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 30ms · UTC 23:16 · PVG 07:16 · LAX 16:16 · JFK 19:16
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.