0

根据我所学到的迭代容器的方法,如 std::vector,是使用迭代器,如下所示:

for(vector<int>::iterator it = numbers.begin(); it != numbers.end(); it++)

我的问题是为什么不使用 standatd 迭代容器for,它更快,因为不需要调用函数 asnumbers.begin()numbers.end()
根据我的尝试,我发现for使用迭代器更快 X 30。
我写了这段代码:

vector<int> numbers;
for (int i = 0; i < 5000000; i++)
{
    numbers.push_back(i);
}

time_t t = time(0);
struct tm * now = localtime(&t);
cout << now->tm_hour << ":" << now->tm_min << ":" <<  now->tm_sec << "\n";

for(vector<int>::iterator it = numbers.begin(); it != numbers.end(); it++)
{
    *it = 7;
}

t = time(0);
now = localtime(&t);
cout << now->tm_hour << ":" << now->tm_min << ":" <<  now->tm_sec << "\n";

int size = numbers.size();
for (int i = 0; i < size; i++)
{
    numbers[i] = i;
}

t = time(0);
now = localtime(&t);
cout << now->tm_hour << ":" << now->tm_min << ":" <<  now->tm_sec;

输出是:

    19:28:25
    19:28:56
    19:28:57
4

2 回答 2

2

看看你的数字——迭代一个简单的向量需要 30 秒?这是 CPU 时间的永恒。那里有问题。

一些建议:

  • 该向量大约需要 19MB。这并不多,但它可能会导致堆碎片,或者如果您的计算机上加载了许多其他应用程序,则可能会导致虚拟机交换。要获得可靠的号码,请关闭尽可能多的应用程序并确保您的系统处于空闲状态。

  • couts 在计时器内,因此您正在测量部分 iostream 库的性能。在你采取停止时间之后,在计时部分之外进行 couts 。

  • 一秒钟的时钟对于性能指标来说不够精确。使用 timeval 和 gettimeofday() 获得微秒精度。

  • 仅对向量进行一次迭代,我就看到了运行之间的巨大差异。要获得更多可重复的结果,请多次迭代向量(如 500 次)。(这比使用更大的向量要好,这可能会导致交换/碎片问题。)

  • 打开优化(例如,g++ -O3)。循环将运行得更快,时间差会更小。内联优化可能对 std::vector<> 代码有更多帮助。

通过这些更改(如下),在我的计算机上,迭代器比没有优化的索引慢 4 倍,但使用 -O1 稍,使用 -O3 几乎相同。

#include <iostream>
#include <sys/time.h>
#include <vector>
using namespace std;

const unsigned N_REPS = 500;
const unsigned N_ITEMS = 5000000;

int print_elapsed(timeval start)
{
    timeval stop;
    gettimeofday(&stop, NULL);
    int elapsed = (stop.tv_sec * 1000000 + stop.tv_usec) - (start.tv_sec * 1000000 + start.tv_usec);
    cout << elapsed << "us" << endl;
    return elapsed;
}

int main()
{
    vector<int> numbers;
    numbers.reserve(N_ITEMS); // avoid heap fragmentation
    for (int i = 0; i < N_ITEMS; ++i)
        numbers.push_back(i);

    timeval start;
    gettimeofday(&start, NULL);

    for (unsigned r = 0; r < N_REPS; ++r)
        for (vector<int>::iterator it = numbers.begin(); it != numbers.end(); ++it)
            *it = r;

    int elapsed0 = print_elapsed(start);
    gettimeofday(&start, NULL);

    unsigned size = numbers.size();
    for (unsigned r = 0; r < N_REPS; ++r)
        for (unsigned i = 0; i < size; ++i)
            numbers[i] = r;

    int elapsed1 = print_elapsed(start);
    cout << 100 * float(elapsed1) / elapsed0 << '%' << endl;

    return 0;
}
于 2013-02-23T19:46:37.747 回答
1

Using iterators provide you the flexibility that even if you change the container type to another the iterating code will remain the same. This is because all the standard library containers provide iterators. In a way it gives you the chance to write more generic code.

于 2013-02-23T19:26:15.070 回答