c++ - (使用 'while' 的插入排序)和(使用 'for' 的插入排序)之间的计算时间有何不同？

Question

关闭。这个问题不符合Stack Overflow guidelines .它目前不接受答案。












想改进这个问题？将问题更新为 on-topic对于堆栈溢出。

2年前关闭。




Improve this question

/////////////////////////////////////////////////////////////
void insertion_sort_f(int *A, int s, int e) {
    int j, i, tmp;
    for (j = s+1; j < e; j++) {
        tmp = A[j];     
        for (i = j - 1; i >= 0 && A[i] > tmp; i--)
            A[i+1] = A[i];          
        A[i + 1] = tmp;
    }
}
void insertion_sort_w(int *A, int s, int e) {
    int j, i, tmp;
    for (j = s + 1; j < e; j++) {
        tmp = A[j];
        i = j;
        while (--i >= 0 && A[i] > tmp) {
            A[i + 1] = A[i];
        }
        A[i + 1] = tmp;
    }
}
//////////////////////////////////////////////////////////////

我用 100000 个数据测试了两种插入排序，一种使用“for”，另一种使用“while”。
我想计算时间没有有意义的差异。
但“while”比“for”平均快 1000 毫秒。
哪一个得出这个结果？

附言。
我发布了完整的代码进行解释。 https://colorscripter.com/s/56xWn0O

Answer 1

如果将函数更改为:

void insertion_sort_w(int *A, int s, int e) {
    int j, i, tmp;
    for (j = s + 1; j < e; j++) {
        tmp = A[j];
        i = j - 1;
        while (i >= 0 && A[i] > tmp) {
            A[i + 1] = A[i];
            --i;
        }
        A[i + 1] = tmp;
    }
}

clang 和 gcc 将为这两种方法产生相同的输出。 https://godbolt.org/z/8Hzxys

使用您的原始实现，为这两种方法生成的 ASM 之间的差异很小。如果(通过优化!)两者之间有任何显着的性能差异，我会感到非常惊讶。

仔细看看 ASM: https://godbolt.org/z/Xo3hZ7

您的 while 循环版本确实会产生更少的 ASM，但这并不意味着它会更快。这只是意味着编译器在for循环版本中生成了一些额外的代码块和跳转。这实际上可能会使 for 循环版本稍微快一些，因为它可能有一个额外的早期输出，而 while 循环版本没有。再说一次，额外的跳跃可能是一个问题。

使用诸如 vtune 之类的分析器可能是清楚了解相对性能的最佳选择。