Gol*_*les 11 c++ performance stl
我知道单个地图查询最多占用log(N)时间.但是我想知道,我已经看到很多使用字符串作为映射键的示例.例如,将std :: string作为键与地图而不是int相关联的性能成本是多少？
std::map<std::string, aClass*> someMap; VS std::map<int, aClass*> someMap;
谢谢!
Dav*_*eas 13
分析渐近性能的算法正在研究必须执行的操作以及它们添加到等式中的成本.为此,您需要首先了解执行的操作是什么,然后评估其成本.
在平衡二叉树中搜索密钥(映射恰好是)需要O( log N )复杂的操作.这些操作中的每一个都意味着比较匹配的密钥并且如果密钥不匹配则遵循适当的指针(子).这意味着总成本与log N这两个操作的成本成倍.以下指针是一个恒定时间操作O(1),比较键取决于键.对于整数键,比较很快O(1).比较两个字符串是另一个故事,它需要时间与所涉及的字符串的大小成比例O(L)(我故意使用的字符串参数L的长度而不是更常见的N.
当您将所有成本加起来时,您可以使用整数作为键,总成本O( log N )*( O(1) + O(1) )相当于O( log N ).(O(1)隐藏在O符号默默隐藏的常量中.
如果使用字符串作为键,则总成本是O( log N )*( O(L) + O(1) )通过更昂贵的线性操作隐藏常量时间操作O(L)并可转换为的成本O( L * log N ).也就是说,在由字符串键入的映射中定位元素的成本与存储在映射中的元素的数量的对数乘以用作键的字符串的平均长度成比例.
请注意,big-O表示法最适合用作分析工具来确定算法在问题规模增长时的行为方式,但它隐藏了许多对原始性能很重要的事实.
作为最简单的示例,如果将键从通用字符串更改为1000个字符的数组,则可以隐藏在表示法中删除的常量中的成本.比较1000个字符的数组是一个常数操作,恰好需要花费相当多的时间.渐近符号只是一个O( log N )操作,就像整数一样.
许多其他隐藏成本也会发生同样的情况,因为创建元素的成本通常被视为一个恒定时间操作,仅仅因为它不依赖于您的问题的参数(在每个成本中定位内存块的成本)分配不依赖于您的数据集,而是依赖于算法分析范围之外的内存碎片,获取malloc内部锁定的成本以保证不会有两个进程尝试返回相同的内存块取决于锁的争用取决于处理器,进程的数量以及它们执行的内存请求的数量......,再次超出了算法分析的范围).在阅读大O符号的成本时,你必须意识到它的真正含义.
除了比较已经提到的字符串的时间复杂性之外,每次将项添加到容器时,字符串键还将导致额外的内存分配.在某些情况下,例如高度并行的系统,全局分配器互斥体可能是性能问题的根源.
通常,您应该选择在您的情况下最有意义的替代方案,并且仅基于实际性能测试进行优化.众所周知,很难判断出什么是瓶颈.