3

我以 3 种不同的方式在 C++ 中实现了插入排序。一种使用基本的 C 数组，一种使用向量，一种使用迭代器：

void insertionsort_array(int *arr, size_t length)
{
    for (int i = 1; i < length; i++)
        for (int k = i; k > 0 && arr[k] < arr[k-1]; k--)
            swap(arr[k], arr[k-1]);
}

template<typename T>
void insertionsort_vector(vector<T>& arr)
{
    for (int i = 1; i < arr.size(); i++)
        for (int k = i; k > 0 && arr[k] < arr[k-1]; k--)
            swap(arr[k], arr[k-1]);
}

template<class IterType>
void insertionsort_iterator(IterType iter, IterType end)
{
    for (IterType edge = iter + 1; edge != end; ++edge) 
        for (IterType ptr = edge; ptr != iter && *ptr < *(ptr-1); --ptr) 
            swap(*ptr, *(ptr-1));
}

我希望这些函数的运行时间会有所不同。但是，情况并非如此（GCC -O0 的计时）：

// array
Sorting 1000000 lists of length 10:    2605531 usec
Sorting   50000 lists of length 100:   1268442 usec
Sorting     500 lists of length 1000:   787731 usec
Sorting       5 lists of length 10000:  759133 usec

// vector
Sorting 1000000 lists of length 10:    2888354 usec
Sorting   50000 lists of length 100:   2031675 usec
Sorting     500 lists of length 1000:  1604312 usec
Sorting       5 lists of length 10000: 1603279 usec

// iterator
Sorting 1000000 lists of length 10:    3003877 usec
Sorting   50000 lists of length 100:   4150561 usec
Sorting     500 lists of length 1000:  3829943 usec
Sorting       5 lists of length 10000: 3766683 usec

对于长度为 10 的列表，它们的性能大致相同，但对于长度为 10 的数组，迭代器的性能几乎是 C 数组的五倍。怎么会这样？

编辑：我使用 -O3 重新测试了它，效果似乎消失了。很高兴知道我可以使用编译器优化来避免这个问题，但我仍然想了解在 -O0 处发生的这种奇怪行为。

// array
Sorting 1000000 lists of length 10:    802136 usec
Sorting   50000 lists of length 100:   300472 usec
Sorting     500 lists of length 1000:  185330 usec
Sorting       5 lists of length 10000: 179851 usec

// vector
Sorting 1000000 lists of length 10:    955003 usec
Sorting   50000 lists of length 100:   302232 usec
Sorting     500 lists of length 1000:  185034 usec
Sorting       5 lists of length 10000: 181459 usec


// iterator
Sorting 1000000 lists of length 10:    811077 usec
Sorting   50000 lists of length 100:   230852 usec
Sorting     500 lists of length 1000:  112885 usec
Sorting       5 lists of length 10000: 105739 usec

我在 GCC 中使用 -O0 或 -O3 进行编译，并且没有使用其他编译器标志。

4

1 回答 1

4

在没有优化的情况下，最大的区别可能来自于调用类似operator[]. 当函数被调用时，会发生很多导致开销的事情，并且在循环中调用时尤其重要。但是，启用优化后，所有这些函数调用都是内联的，这就是您看到差异消失的原因。请注意，现在任何编译器都应该为您提供几乎相同的性能，无论您是使用std::vector数组还是普通数组。

于 2013-05-01T05:40:27.453 回答