今天突然发现自己是个大杀软。。。

起因

在LeetCode上写题，想了半天毫无头绪，遂翻题解，恍然大悟，直呼妙哉😆

按照题解思路快速完成代码并提交，击败了50%多点的选手🤨

然而点开击败了99%选手的提交代码，发现和题解也是一样思路，遂百思不得其解😕

发现99%代码还使用了我认为奇慢无比的下标直接访问vector元素！？

想当年我了解到使用iterator遍历vector后便为这种看起来很高大上的方法所折服并沿用至今，面对着“三观”尽碎的可能，上网查资料得知：下标直接访问的确比iterator更快！！

但是。。。毕竟实践是检验真理的唯一标准，我决定再自己试试（临死挣扎）。。。

测试

分成3组：

  1. 直接用下标index
  2. 迭代器iterator
  3. C++11中的新特性foreach

网上查阅资料得知，iterator访问有几种优化方法：

  1. 使用后自增
  2. 常量迭代器
  3. 提取vector.end()

首先是代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
// 编译器命令 -static-libgcc -lpsapi
#include <Windows.h>
#include <math.h>
#include <psapi.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#include <algorithm>
#include <iostream>
#include <random>
std::vector<unsigned int> arr;
LARGE_INTEGER lstart, lend, lfreq;
std::mt19937 mt;
double totIndex, totIter, totFor;
inline void init() {
    QueryPerformanceFrequency(&lfreq);
    mt = std::mt19937(std::random_device{}());
    printf("Count,Index,Iterator,ForEach\n");
}
inline void timerStart() {
    QueryPerformanceCounter(&lstart);
}
inline void timerStop() {
    QueryPerformanceCounter(&lend);
}
inline double timerSpan() {
    return (double)(lend.QuadPart - lstart.QuadPart) / (double)lfreq.QuadPart * 1000.0;
}
inline void randInit() {
    long long n = mt() % (long long)1e9;
    arr.clear();
    unsigned int u = 0;
    for (long long i = 1; i <= n; i++)
        arr.push_back(++u);
    printf("%lld,", n);
}
inline void byIndex() {
    long long n = arr.size();
    unsigned int temp;
    timerStart();
    for (int i = 0; i < n; ++i) {
        temp = arr[i];
    }
    timerStop();
    printf("%g,", timerSpan());
    totIndex += timerSpan();
}
// 此处的版本为最终优化版本
inline void byIterator() {
    long long n = arr.size();
    unsigned int temp;
    std::vector<unsigned int>::iterator it = arr.begin(), ed = arr.end();
    timerStart();
    for (; it != ed; ++it) {
        temp = *it;
    }
    timerStop();
    printf("%g,", timerSpan());
    totIter += timerSpan();
}
inline void byForEach() {
    long long n = arr.size();
    unsigned int temp;
    timerStart();
    for (unsigned int ui : arr) {
        temp = ui;
    }
    timerStop();
    printf("%g\n", timerSpan());
    totFor += timerSpan();
}
int main() {
    init();
    for (int i = 1; i <= 20; i++) {
        randInit();
        byIndex();
        byIterator();
        byForEach();
    }
    printf("Average:\n%g,%g,%g", totIndex / 20.0, totIter / 20.0, totFor / 20.0);
    return 0;
}

每组实验测20次，取平均值

结果

时间单位都是毫秒

无优化

Count Index Iterator ForEach
412496532 437.699 2162.42 1989.42
119216746 179.232 1095.75 638.162
495923606 742.139 4560.92 2651.87
931352601 1391.1 8568.66 4993.88
26313293 39.5728 241.531 140.297
552602825 1135.94 5075.68 2957.53
745457912 1437.66 6843.82 3985.57
213446826 319.521 1965.62 1140.39
119067789 177.646 1094.69 635.889
188234190 280.416 1733.99 1007.83
728322180 1091.2 6685.73 3914.53
841381042 1265.75 7732.66 4507.66
361173914 542.042 3323.2 1935.33
270545070 403.941 2487.95 1447.04
12213090 18.1363 114.191 72.117
386551741 692.889 3559.2 2071.83
96517083 144.475 887.358 514.5
318260028 475.689 2927.36 1701.81
467059067 697.862 4297.45 2493.89
416695198 622.697 3830.22 2224.67

平均值：

Index Interator ForEach
604.781 3459.42 2051.21
100% 572% 339%

每组20次的数据量都是一样，下面直接放平均值

迭代器后自增（++it）

Index Iterator For
675.051 3299.05 2428.63
100% 489% 360%

常迭代器后自增（const_iterator，++it）

Index Iterator For
874.831 4232.79 2428.63
100% 539% 309%

我的评价是，没杀软用

提取vector.end()，后自增

Index Iterator For
512.14 1625.49 1695.14
100% 317% 331%

提取vector.end()，后自增 + O3优化

Index Iterator For
2e-5 1287.46 1430.17
100% 6.4373e9% 7.15085e9%

Index杀疯了

总结

没什么好说的，我是大杀软，Index 薄纱好吧，我的 Iterator 😭😭😭

没经过优化前直接被Index和ForEach双双薄纱，开满优化才和ForEach差不多快😭😭😭

然后Index经过O3优化甚至能恐怖到0ms？？！😲😲😲

我的评价是：wyx是纯纯的小丑🤡🤡🤡

wyx自从学了iterator之后如得灵丹妙药，在坚信用iterator速度薄纱下标访问的无厘头良好自我感觉的陶醉下，直到今天为止他只要用到vector必用iterator🤡🤡🤡

不说了，iterator，再见！