0

所以我一直在测试 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;
            }
    }
}
4

2 回答 2

2

我的猜测是，编译器在temp变量位于函数中时会对其进行优化，并且可以识别交换的内容。但是如果没有函数，temp变量的范围就会扩展到使用它的块之外，因此如果没有足够的优化级别，编译器可能总是将最后一个“临时”值存储在其中。

尝试将声明temp从循环外部移动到您正在使用它的位置，即int temp = data[j].

无论如何，这只是一个猜测；查看生产的组件以进行验证。

于 2013-11-08T10:49:31.053 回答
0

我希望这样会更快，因为函数调用在那里打开了自己的堆栈帧

期望Swap被内联是完全合理的。在这种情况下，编译器与您手动执行的操作基本相同，并且两个版本之间没有区别。

事实上，我已经检查了你在 SO 发布的代码，包括 clang 3.4（主干）和 gcc 4.7.2，具有优化级别-O3，你的交换的两个版本之间绝对没有区别（Swap函数与手动内联交换） .

这是我的代码：

#include <algorithm>
#include <cstdio>
#include <numeric>
#include <vector>
#include <boost/chrono.hpp>

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])
            {
                Swap(data[j],data[j-1]);
                //temp = data[j];
                //data[j] = data[j - 1];
                //data[j-1] = temp;
                is_sorted = false;
            }
    }
}

int main() {

    const int SIZE = 30000;

    std::vector<int> v(SIZE);

    std::iota(v.begin(), v.end(), 0);

    std::shuffle(v.begin(), v.end(), std::mt19937(5489u));

    using namespace boost::chrono;

    auto start = high_resolution_clock::now();

    BubbleSort(v.data(), v.size());

    auto finish = high_resolution_clock::now();

    std::printf("%ld  ms\n", duration_cast<milliseconds>(finish-start).count());
}

我用(clan)g++ -O3 -std=c++11 sort.cpp -lboost_system -lboost_chrono -lrt.

所以，问题一定出在其他地方。

于 2013-11-08T11:56:49.290 回答