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

C++萌新求快速对 std::vector<std::string>去重(string 是"数字")

  •  
  •   csfreshman · 2022-10-25 23:59:13 +08:00 · 1721 次点击
    这是一个创建于 520 天前的主题,其中的信息可能已经有所发展或是发生改变。

    遇到一个问题是需要遍历 std::vectorstd::string,string 内容可能重复,需要过滤,对每一个 string 执行一个处理逻辑,伪代码:

        std::vector<std::string> vec;
        for(auto str:vec)
        {
            if(xxxx.find(str) == xxxx.end())
            {
                //first match,handle
                handle();
                xxxx.insert(str);
            } else {
                //noting to do
            }
        }
    

    我写了两个方案,晚上学习了 benchmark 写法,写了对比下,居然是先转成整数速度快一些? https://quick-bench.com/q/MJ4zzU3S5LIhGHd8qlgwBNRAOEc String_dup_set 和 String_dup_atoi ,第一个写法可能再向 set 中插入的时候触发了构造? 请教大家,有没有更优雅,更快速的方法,最好 c++14 支持(当前项目代码不支持 17 20 )

    9 条回复    2022-10-27 08:48:38 +08:00
    yuruizhe
        1
    yuruizhe  
       2022-10-26 00:59:02 +08:00 via iPhone
    先排序,再从尾部一个一个删元素?
    lanmiao
        2
    lanmiao  
       2022-10-26 01:02:42 +08:00
    因为你的测试字符串,就是专门为 String_dup_atoi 准备的,set<int> 相比 set<string> 在 计算 hash 、相等判断当然快啦。
    你改成随机字符串,String_dup_atoi 还能用?
    wevsty
        3
    wevsty  
       2022-10-26 02:06:38 +08:00
    std::unordered_set 默认使用 std::hash ,但 std::hash 某些编译器上的实现不够优良比较容易产生冲撞。建议是自己指定一个合适的 hash 算法,或者直接用 std::set 。

    既然知道是 copy 产生了开销,那就尽量避免 copy 。
    for(auto str:vec)
    这里的 str 可能会产生复制,不如写成
    for(auto &str:vec)

    如果确定 string 内的内容一定是数字,那么先转换成 int 确实是更划算的选项,因为你每次 insert 都必然会复制对象,复制 int 毫无疑问比复制一个 std::string 更快

    最后,代码风格上我个人不建议驼峰和下划线一起用,要么统一驼峰,要么统一下划线。
    wevsty
        4
    wevsty  
       2022-10-26 02:51:24 +08:00
    我稍微帮你改了一下,你可以对照看看结果。

    https://quick-bench.com/q/ZfSKwXB43akAlzz1MeR0DwL6r7M
    GeruzoniAnsasu
        5
    GeruzoniAnsasu  
       2022-10-26 04:12:10 +08:00
    你这个 bench 也太不严谨了……
    https://quick-bench.com/q/lbS2mpw9mSu7EbyfG_57FMsb9Iw

    但其实 quick bench 本来也 bench 个寂寞,没有火焰图的 profiling 都是脑补空气,甚至瓶颈在算法本身呢还是内存分配呢,不知道的
    csfreshman
        6
    csfreshman  
    OP
       2022-10-27 00:09:39 +08:00
    @GeruzoniAnsasu 学习了,我明天看下,多谢
    csfreshman
        7
    csfreshman  
    OP
       2022-10-27 00:11:58 +08:00
    @wevsty for(auto &str:vec) 这里现在线上跑的有优化,vec 的量这里我加监控统计,平均 1500 左右,明天研究下你写的那个 bench ,多谢
    whi147
        8
    whi147  
       2022-10-27 08:47:54 +08:00 via iPhone
    转为 std::set 不行吗
    whi147
        9
    whi147  
       2022-10-27 08:48:38 +08:00 via iPhone
    利用 hash 特性去重
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   5533 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 27ms · UTC 06:39 · PVG 14:39 · LAX 23:39 · JFK 02:39
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.