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

各位 v 友,帮忙看看这个思路对不?

  •  
  •   liuidetmks · 2021-10-09 06:38:57 +08:00 · 2724 次点击
    这是一个创建于 1142 天前的主题,其中的信息可能已经有所发展或是发生改变。

    各位 v 友,帮忙看看这个思路对不对

    项目里面有个函数调用频率很高(极高), 大概长这样,

    char *cmd=input //string,输入
    if (cmd == "cmd1") 
       dosomething1
    else if cmd== “cmd2” 
       dosomething2
    

    这里 cmd1 cmd2 是举例的常数,实际是 30 位以内的字符串

    if 大概有 200 多个分支,( 就是你们批判的那种,一个 if 几百分支,我接下了) 我想优化下, 目前有两个想法,望各位指正

    思路 1: 统计每个 cmd 使用频率,调整 if 顺序,高频在前,低频在后,这样优化估计(目测)有些作用。(这主要是作为思路 2 被卡住了的备选


    思路 2,把 string 快速转换成 int,利用 switch case 跳转,这样当然是最好的(吗?),初步想法是 把 sting 各位按不同权重求和得到 int,这个做成一个宏,这样,即使冲突了,编译器会报错。 最终代码是这样,

    int cmdn = sum ( cmd )//这个是输入,运行时计算
    
    switch cmdn:
     case M(CMD1)://M 是宏,返回一个常数
           DO SOMETHING
     case M(cmd2 ):
           do something 2
    

    这样,新加 cmd3 命令 即使求权重和前面冲突了,编译器会立即报错,我只需要修改字符串某几位权重或者换个命令名就行。 关键点来了,如何写这个宏呢?
    要优雅,不要污,最好是接受一个参数
    不要这样
    M ( c,m,d,1 )
    要这样
    M(cmd)

    ps:我其实有点怀疑宏能不能做到这个 (分割字符串)

    15 条回复    2021-10-09 11:46:01 +08:00
    ysc3839
        1
    ysc3839  
       2021-10-09 06:48:54 +08:00 via Android   ❤️ 1
    宏大概做不到,不过 C++的 constexpr+std::integral_constant 可以实现编译期计算。
    具体可以参考我写的 i18n 库,里面用到了 FNV Hash 。
    https://github.com/ysc3839/yi18n/blob/7165a74a31d8bb65983066e908d07b4d50694299/I18n.hpp#L62
    wxd92
        2
    wxd92  
       2021-10-09 06:59:26 +08:00 via iPhone
    试下 map 呢?
    cmdMap[“cmd”] = dosomething
    wd
        3
    wd  
       2021-10-09 07:00:36 +08:00 via iPhone
    如果是 python 的话,我会做一个 map,key 是 cmd value 是个 function,然后就是 map 里面 get 下 cmd key 执行就可以了
    xuanbg
        4
    xuanbg  
       2021-10-09 07:03:31 +08:00
    哈希表呀! cmd 字符串作为 key,123 作为 value 不就好啦。
    liuidetmks
        5
    liuidetmks  
    OP
       2021-10-09 07:42:57 +08:00 via iPhone
    @ysc3839 似乎你这个是我想要的,cpp 可真太牛了
    @wd @wxd92 @xuanbg map 的话,内部好像是个黑红树,每次 get 都是 lgn,而 cmd 的频率使用相差很大,有些个命令估计到 80% ,没有充分利用到使用频率这个特性,可能效果和我说的思路 1 差不多,不过代码确实好看很多。
    angryfish
        6
    angryfish  
       2021-10-09 08:50:24 +08:00   ❤️ 5
    个人觉得根本没必要优化,有同意我观点的人儿吗?
    xuanbg
        7
    xuanbg  
       2021-10-09 08:50:34 +08:00
    @liuidetmks 哈希表可不是红黑树,查询时间复杂度是 O(1)
    ysc3839
        8
    ysc3839  
       2021-10-09 09:00:25 +08:00 via Android
    @liuidetmks C++有基于 hash 的 unordered_map,不过这个和 switch 比哪个快可能要测试了才知道。
    notyss
        9
    notyss  
       2021-10-09 09:08:02 +08:00
    benchmark it!
    dwlovelife
        10
    dwlovelife  
       2021-10-09 09:47:53 +08:00   ❤️ 1
    这样优化是为了提高一点人都感觉不到的效率么,为啥子不是想着优化复用性呢。
    liuidetmks
        11
    liuidetmks  
    OP
       2021-10-09 09:58:07 +08:00
    @angryfish @notyss easy,easy~ 别这么严肃嘛,感叹号了都用上了, 突发奇想而已,应该不会真的运用到项目,如果引入 1 楼同学的 cpp 特性,可以想象有人会问,你搞这些名堂干嘛?

    这应该不用详细测试,由于项目 cmd 是逐次追加的,前面的 cmd 大概率是高频使用的,
    但是每个 if 里面 strcmp 复杂度 N,(很小,但因为有一些前缀 cmd_ObjName_xxxxx,会差不多等于 10+), 200 多个 if,跑起来也是有点够呛吧。
    bfdh
        12
    bfdh  
       2021-10-09 10:30:55 +08:00
    单纯 if 改 switch 是没有效果的,switch 和 if 对于常量的比较逻辑是一样的。
    dirtysalt
        13
    dirtysalt  
       2021-10-09 10:56:33 +08:00
    要不要先找找每个字符串的特点,看看能不能快速映射成为 int

    如果 swtich 里面的范围是连续的话,那么编译器会会生成表格跳转的,效果也非常好 https://dirtysalt.github.io/html/c-switch-table-in-asm.html

    如果字符串已知的话,那么就可以手工地设计一个映射函数,比如 cmd1->0, cmd2->1 这样
    CEBBCAT
        14
    CEBBCAT  
       2021-10-09 11:05:00 +08:00
    赞同楼上的函数 map,优点如下:
    1. 防命令冲突
    2. 跳转逻辑重定位到了 map,跳转函数代码可以缩短到数行,逻辑清晰
    至于性能这方面……我想也许可以做个 benchmark,也许就只是几纳秒的事
    Nich0la5
        15
    Nich0la5  
       2021-10-09 11:46:01 +08:00
    hashMap<string,func>
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   1178 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 31ms · UTC 23:59 · PVG 07:59 · LAX 15:59 · JFK 18:59
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.