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

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

  •  
  •   shikimoon · 44 天前 · 2257 次点击
    这是一个创建于 44 天前的主题,其中的信息可能已经有所发展或是发生改变。

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

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

    既然长度都在 1~5 之间,那你用三层 Trie tree 就能有效压缩深度。每一层是 1024 个格子,取格子只要位移操作不用乘法。相当于分层快速哈希,而且必然没有冲突了。
    ipwx
        4
    ipwx  
       44 天前
    上述操作必须用指针在那里魔法计算。。。不要用 STL 容器。不然速度还是提不上去
    shikimoon
        5
    shikimoon  
    OP
       44 天前
    @ipwx 都是中文,trie 树应该作用不大。
    nulIptr
        6
    nulIptr  
       44 天前
    一个字符 3 字节,一个单词 10 个字符,10 亿字符串也不到 30g 。。。我觉得字典够用
    learningman
        7
    learningman  
       44 天前
    中文为啥不能用 trie 树,映射下多开几层
    heqing
        8
    heqing  
       44 天前   ❤️ 1
    可以参考一下 kenlm 的实现
    abujj
        9
    abujj  
       44 天前
    是 MapReduce 的意思吗 ?
    shikimoon
        10
    shikimoon  
    OP
       44 天前
    @abujj 不会。。。
    shikimoon
        11
    shikimoon  
    OP
       44 天前
    @nulIptr 是够用但是太慢
    dji38838c
        12
    dji38838c  
       44 天前   ❤️ 1
    这不是 MapReduce 的第一课吗,赶快学学
    pengtdyd
        13
    pengtdyd  
       44 天前
    首先排除 C 以外的其他语言,因为其他垃圾太慢了。其次就是算法和数据结构了,这个嘛,就要看个人发挥了。
    wangyu17455
        14
    wangyu17455  
       43 天前
    map reduce
    nuistzhou
        15
    nuistzhou  
       43 天前 via iPhone
    Mapper
    Reducer
    哈哈
    bxb100
        16
    bxb100  
       43 天前 via Android
    单机 MapReduce 有啥用
    shm7
        17
    shm7  
       43 天前   ❤️ 1
    GB2312 中文字就六七千个,怎么搞成上亿的词典? NLP 里面语言模型一般也就几万字,还包括很多重复的呢。
    如果就是这几千字组成的词语 /短语也算入词典的话,用沙发的方法是不是有帮助?
    ToBeHacker
        18
    ToBeHacker  
       43 天前
    大部分都是重复的,其实字典就可以了
    Buges
        19
    Buges  
       43 天前 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  
       43 天前
    直接用语言自带的哈希表就够了
    关于   ·   帮助文档   ·   API   ·   FAQ   ·   我们的愿景   ·   广告投放   ·   感谢   ·   实用小工具   ·   2900 人在线   最高记录 5497   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 24ms · UTC 12:03 · PVG 20:03 · LAX 05:03 · JFK 08:03
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.