2 c++ performance iterator stl find
假设我有一个方法需要从地图中提取8个值,其中包含100个元素.你认为哪个更好:
从头到尾进行一次for循环,通过打开钥匙拉出元素？
或者使用find 8次来获取这些值？
走在列表中需要花费O(n)时间来查找随机元素.
Map是一个平衡的二叉树,因此查找是O(log n).
因此,8执行8*log2(n)的结果,并且行列表是(n).列表越大,增益越大,但在所有随机情况下,执行查找将比执行迭代更快.
在非随机情况下,如果有理由将所需的项目在树中或在"开始"(左侧)附近彼此靠近,那么步行/迭代将更快.但这似乎是不相干的.
虽然我选择了这个find选项,但人们对渐近性能的压力过大.
事实上,渐近性能是可以接收相当大的输入的算法的便利指南,但即便如此,它也不是万无一失的.对于任何合理的输入,具有比另一个更差的渐近性能的算法很可能更快.
然后有时候你的输入大小相当小(甚至是固定的).在这种情况下,渐近性能几乎毫无意义.
| 归档时间： |
|
| 查看次数： |
3207 次 |
| 最近记录： |