V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
V2EX 提问指南
black11black
V2EX  ›  问与答

C++ STL 中查找速度最快的是什么数据结构?

  •  
  •   black11black · 2020-12-04 21:37:30 +08:00 · 2671 次点击
    这是一个创建于 1431 天前的主题,其中的信息可能已经有所发展或是发生改变。

    如题,C++不太熟,最近有个需求是要把 python 科学计算代码用 C++加速,写的过程中遇到问题就来问 V 友了。

    目前要实现一个类似 python 中字典映射的操作,即比如输入 token = "sam" ,要求能够快速的获取到某数据结构(比如说一个 vector )中 sam 对应的指定项。据我所知 vector 原生可以用角标提取,但应该是不支持用字符串提取这种的,即 v[0]这种是 OK 的但是 v["sam"]这种应该是不行的。

    由于我不清楚 stl 容器具体的搜索实现,并不能确定用哪种方式会更快。因为我知道 py 的字典查找经过了 hash 优化,如果 c++不好好选择算法的话,一个搞不好比 python 更慢也是有可能的。

    网上搜到一些资料显示 vector 比 set 查找更快,而另一些资料则显示相反,互相矛盾,看不太懂。求问一下 c++带佬,这种常见数据结构在 c++里的最佳实践是什么?

    ===========================

    另外之前 v2 一个老哥似乎说过 map 查找速度超级慢

    第 1 条附言  ·  2020-12-04 22:27:26 +08:00

    贴个条,楼下老哥说的无序map

    我是cython环境开发,就直接在cython环境里写了,随手测了一下,测试办法是创建一个长度为1000万的map,搜索其中第9999999项,重复一千万次,计时。

    简单代码如下

    # distutils: language=c++
    import cython
    from libcpp.unordered_map cimport unordered_map
    import time
    
    cdef int i , j
    cdef float sum = 0
    cdef unordered_map[int, float] o_map
    for i in range(10000000):
        o_map[i] = 1000000 - i
    # 重复一千万次
    st_time = time.time()
    for j in range(10000000):
        sum += o_map[9999999]
    print(time.time() - st_time , sum)
    
    # Python字典实现
    o_dict = dict()
    sum = 0
    for i in range(10000000):
        o_dict[i] = 10000000 - i
    st_time = time.time()
    for j in range(10000000):
        sum += o_dict[9999999]
    print(time.time() - st_time , sum)
    

    运行速度,map版本87毫秒,python版本320毫秒。确实不是我黑map,就是慢啊,c这速度都快叫jit赶上了。。顺带一提pypy3执行速度140毫秒。

    12 条回复    2020-12-07 09:29:47 +08:00
    lcdtyph
        1
    lcdtyph  
       2020-12-04 21:41:03 +08:00
    unordered_map
    agagega
        2
    agagega  
       2020-12-04 21:41:42 +08:00 via iPhone
    你想要的是 unordered_map
    DGideas
        3
    DGideas  
       2020-12-04 21:45:15 +08:00
    楼上正解,另外也别这么黑 map 啊。。。充其量查找速度还是对数时间复杂度呢。。
    secondwtq
        4
    secondwtq  
       2020-12-04 22:15:47 +08:00   ❤️ 4
    vector 只能整数 index 这只是个接口问题而已,你自己往里面存个 pair 自己写函数查也可以
    C++ 社区的意思是,所有涉及到 pointer chasing 的都慢,所以 std::list 是垃圾,vector FTW
    所以如果数据小的话,就直接用 vector 线性查,可能比其他数据结构还要快,这个叫 flat map (不是 Monad bind 的那个 flatmap )
    另外,vector 还会加一个 SBO 的优化,这样就可以完全避免内存分配,这个叫 small vector

    unordered_map 在性能方面的问题在于它是 chaining 实现的,内存性能一般不如 open addressing,所以有时候会用 open_addressing 的实现,这个叫 dense_map
    unordered_map 的优势在于迭代器稳定,map 的优势在于 ordered access

    至于查字符串还有专门的数据结构

    至于楼主这个,你得自己 benchmark
    black11black
        5
    black11black  
    OP
       2020-12-04 23:27:35 +08:00 via Android
    @secondwtq 大佬再问个事,有关插入,读取和删除的效率。目前需要对一个表类数据结构频繁操作,对应的是 py 的 list,插入,读取,删除我粗略估计在 5:10:3 这样的比例,用 vector 是正确选择吗?因为听说 vec 读取很快,但是删除开销很高。如果用链表的话哪个更合适?
    QBugHunter
        6
    QBugHunter  
       2020-12-05 10:41:54 +08:00
    @black11black
    vector 时这样的,比如你要储存 10000 个对象,然后 vector 会申请一块连续的内存,可能可以存放 20000 个(这个值不同版本的 STL 有所不同),然后你要在尾部插入 10 个,或者删除 10 个,速度很快
    但如果你要在尾部再插入 10000 个对象,vector 就会再申请一块 40000 个对象长度的内存,然后把 20000 个对象复制进去
    wctml
        7
    wctml  
       2020-12-05 14:57:53 +08:00
    年轻人 你不讲武德,为什么查同一位置;

    ```
    unordered_map<int, float> mapValue;
    clock_t timeStart = clock();
    for (size_t index(0); index < 10000000; ++index)
    {
    mapValue[index] = 1000000 - index;
    }
    std::cout << "make time " << (clock() - timeStart) << std::endl;
    double sum(0);
    timeStart = clock();
    for (size_t index(0); index < 10000000; ++index)
    {
    sum += mapValue[9999999];
    }
    std::cout << "find time " << (clock() - timeStart) << std::endl;

    sum = 0;
    timeStart = clock();
    for (size_t index(0); index < 10000000; ++index)
    {
    const auto& iter = mapValue.find(9999999);
    if (iter != mapValue.end())
    {
    sum += iter->second;
    }
    }
    std::cout << "find time " << (clock() - timeStart) << std::endl;
    ```

    make time 3432
    find time 39
    find time 7
    black11black
        8
    black11black  
    OP
       2020-12-05 18:44:35 +08:00 via Android
    @wctml 这方代码啥意思大佬,uo_map 的搜索比索隐快的多的意思吗?
    black11black
        9
    black11black  
    OP
       2020-12-05 18:45:50 +08:00 via Android
    有需要大量用到排序的数据结构,网上查了查似乎是 deque 最快,然而实测还是 vector 快,序列长度在一万左右。也是神秘
    wctml
        10
    wctml  
       2020-12-07 09:26:49 +08:00
    @black11black
    1 、这是 C++坑的地方,在不同的用法,有不同的区别。这点不像 python 做一个事情可能只有一个最优解,但是 C++可能有 N 个解法得你去踩坑。
    2 、可以了解 C ++中的 map []和 map.at 的区别;
    3 、另外查找同一个位置可能编译器会有优化的,可以试试伪随机搜索效率测试。
    wctml
        11
    wctml  
       2020-12-07 09:27:45 +08:00
    sum = 0;
    timeStart = clock();
    for (size_t index(0); index < 10000000; ++index)
    {
    sum += mapValue.at(9999999);
    }
    std::cout << "find time " << (clock() - timeStart) << std::endl;

    find time 7
    wctml
        12
    wctml  
       2020-12-07 09:29:47 +08:00
    ```
    sum = 0;
    timeStart = clock();
    for (size_t index(0); index < 10000000; ++index)
    {
    sum += mapValue 。at(9999999);
    }
    std::cout << "find time " << (clock() - timeStart) << std::endl;

    find time 7
    ```

    请不要在每一个回复中都包括外链,这看起来像是在 spamming
    我只能把点换成句号
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   3353 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 22ms · UTC 10:59 · PVG 18:59 · LAX 02:59 · JFK 05:59
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.