这是一个创建于 1450 天前的主题，其中的信息可能已经有所发展或是发生改变。
如题，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毫秒。
 |
1
lcdtyph 2020-12-04 21:41:03 +08:00
unordered_map
|
 |
2
agagega 2020-12-04 21:41:42 +08:00 via iPhone
你想要的是 unordered_map
|
 |
3
DGideas 2020-12-04 21:45:15 +08:00
楼上正解，另外也别这么黑 map 啊。。。充其量查找速度还是对数时间复杂度呢。。
|
 |
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 |
 |
5
black11black OP @secondwtq 大佬再问个事，有关插入，读取和删除的效率。目前需要对一个表类数据结构频繁操作，对应的是 py 的 list，插入，读取，删除我粗略估计在 5:10:3 这样的比例，用 vector 是正确选择吗？因为听说 vec 读取很快，但是删除开销很高。如果用链表的话哪个更合适？
|
 |
6
QBugHunter 2020-12-05 10:41:54 +08:00
@black11black
vector 时这样的，比如你要储存 10000 个对象，然后 vector 会申请一块连续的内存，可能可以存放 20000 个（这个值不同版本的 STL 有所不同），然后你要在尾部插入 10 个，或者删除 10 个，速度很快 但如果你要在尾部再插入 10000 个对象，vector 就会再申请一块 40000 个对象长度的内存，然后把 20000 个对象复制进去 |
 |
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 |
|
8
black11black OP @wctml 这方代码啥意思大佬，uo_map 的搜索比索隐快的多的意思吗？
|
|
9
black11black OP 有需要大量用到排序的数据结构，网上查了查似乎是 deque 最快，然而实测还是 vector 快，序列长度在一万左右。也是神秘
|
|
10
wctml 2020-12-07 09:26:49 +08:00
@black11black
1 、这是 C++坑的地方，在不同的用法，有不同的区别。这点不像 python 做一个事情可能只有一个最优解，但是 C++可能有 N 个解法得你去踩坑。 2 、可以了解 C ++中的 map []和 map.at 的区别； 3 、另外查找同一个位置可能编译器会有优化的，可以试试伪随机搜索效率测试。 |
|
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 |
|
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 我只能把点换成句号 |
Select Language