C++ map::find & map::at 性能差异
C++ map::find & map::at performance difference
我正在给一些练习和一个特定的程序评分,虽然算法看起来是正确的但它会太慢(我的意思是 太减缓)。该程序正在使用 map::at
(在 C++11 中引入)访问地图。只需将 at
替换为 find
(并修复语法),相同的程序将非常快(与原始版本相比)。
查看 cplusplus.com 这两种方法都声称具有相同的复杂性,我不明白为什么一个会与另一个不同(除了 API 原因,不抛出异常等).
然后我看到数据竞争部分的描述不一样。但我不完全理解其中的含义。我假设 map::at
是线程安全的(而 map::find
不是)并因此导致一些运行时惩罚是否正确?
http://www.cplusplus.com/reference/map/map/at/
http://www.cplusplus.com/reference/map/map/find/
编辑
两者都在循环调用 10.000.000 次。没有优化标志。就 g++ foo.cpp
。这是差异(arrayX 是向量,m 是地图)
< auto t = m.find(array1.at(i));
< auto t2 = t->second.find(array2.at(i));
< y = t->second.size();
< cout << array.at(i) << "[" << t2->second << " of " << y << "]" << endl;
---
> auto t = m.at(array1.at(i));
> x = t.at(array2.at(i));
> y = m.at(array1.at(i)).size();
> cout << array.at(i) << "[" << x << " of " << y << "]" << endl;
您观察到的性能差异可归因于对象复制。
auto t = m.at(array1.at(i));
根据template argument deduction规则(auto
说明符同样适用),在上面的语句中,t
被推导为mapped_type
,这会触发一个对象复制.
您需要将 t
定义为 auto& t
才能将其推导为 mapped_type&
。
相关对话:`auto` specifier type deduction for references
我正在给一些练习和一个特定的程序评分,虽然算法看起来是正确的但它会太慢(我的意思是 太减缓)。该程序正在使用 map::at
(在 C++11 中引入)访问地图。只需将 at
替换为 find
(并修复语法),相同的程序将非常快(与原始版本相比)。
查看 cplusplus.com 这两种方法都声称具有相同的复杂性,我不明白为什么一个会与另一个不同(除了 API 原因,不抛出异常等).
然后我看到数据竞争部分的描述不一样。但我不完全理解其中的含义。我假设 map::at
是线程安全的(而 map::find
不是)并因此导致一些运行时惩罚是否正确?
http://www.cplusplus.com/reference/map/map/at/
http://www.cplusplus.com/reference/map/map/find/
编辑
两者都在循环调用 10.000.000 次。没有优化标志。就 g++ foo.cpp
。这是差异(arrayX 是向量,m 是地图)
< auto t = m.find(array1.at(i));
< auto t2 = t->second.find(array2.at(i));
< y = t->second.size();
< cout << array.at(i) << "[" << t2->second << " of " << y << "]" << endl;
---
> auto t = m.at(array1.at(i));
> x = t.at(array2.at(i));
> y = m.at(array1.at(i)).size();
> cout << array.at(i) << "[" << x << " of " << y << "]" << endl;
您观察到的性能差异可归因于对象复制。
auto t = m.at(array1.at(i));
根据template argument deduction规则(auto
说明符同样适用),在上面的语句中,t
被推导为mapped_type
,这会触发一个对象复制.
您需要将 t
定义为 auto& t
才能将其推导为 mapped_type&
。
相关对话:`auto` specifier type deduction for references