所以我一直在用 C 语言测试排序算法的运行时间,并且我不断对代码进行轻微修改,看看它会如何影响速度等等,其中一个修改是在排序算法中进行冒泡排序交换与其作为一个单独的函数调用,我希望它更快,因为函数调用打开了自己的堆栈框架,但结果慢了几乎两倍,我不知道为什么。
代码如下:
void Swap(int& x, int& y)
{
int temp = x;
x = y;
y = temp;
}
void BubbleSort(int data[], int size)
{
int i, j, temp;
bool is_sorted = false;
for (i = 0; i < (size - 1) && !is_sorted; i++)
{
is_sorted = true;
for (j = size - 1; j > i; j--)
if (data[j] < data[j - 1])
{
//used to be swap(data[j],data[j-1];
temp = data[j];
data[j] = data[j - 1];
data[j-1] = temp;
is_sorted = false;
}
}
}
- 编辑以回答评论,是的,我确实在发布时运行了编译器优化,如果你想看看我是如何获得运行时间的,这里是完整代码 https://gist.github.com/anonymous/7363330
最佳答案
我的猜测是编译器优化了 temp
变量,当它在函数中时它被识别出来了。但是如果没有该函数,temp
变量的范围会扩展到它所在的 block 之外,因此如果没有足够的优化级别,编译器可能总是将最后一个“临时”值存储在其中。
尝试将 temp
的声明从循环外部移动到您使用它的地方,即 int temp = data[j]
。
无论如何,这只是一个猜测;查看生成的组件以进行验证。
关于c++ - 使用 swap 作为函数而不是在算法本身中更快地编码,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/19857040/