排序:这是真正的性能差异，还是我做错了什么？

Question

我需要对许多由8个浮点数组成的小数组进行排序。最初我使用的是std::sort，但是对它的性能不满意，我尝试了一种由以下代码生成的比较交换算法：http://pages.ripco.net/~jgamble/nw.html。

测试代码如下：

template <typename T>
bool PredDefault(const T &a, const T &b) {return a > b;}

template <typename T>
bool PredDefaultReverse(const T &a, const T &b) {return a < b;}

template <typename T>
void Sort8(T* Data, bool(*pred)(const T &a, const T &b) = PredDefault) {
    #define Cmp_Swap(a, b) if (pred(Data[a], Data[b])) {T tmp = Data[a]; Data[a] = Data[b]; Data[b] = tmp;}

    Cmp_Swap(0, 1); Cmp_Swap(2, 3); Cmp_Swap(4, 5); Cmp_Swap(6, 7);
    Cmp_Swap(0, 2); Cmp_Swap(1, 3); Cmp_Swap(4, 6); Cmp_Swap(5, 7);
    Cmp_Swap(1, 2); Cmp_Swap(5, 6); Cmp_Swap(0, 4); Cmp_Swap(3, 7); 
    Cmp_Swap(1, 5); Cmp_Swap(2, 6);  
    Cmp_Swap(1, 4); Cmp_Swap(3, 6);
    Cmp_Swap(2, 4); Cmp_Swap(3, 5);
    Cmp_Swap(3, 4);

}

int lastTick;
int tick() {
    int hold = lastTick;
    lastTick = GetTickCount();
    return lastTick - hold;
}

int main()
{
    vector<vector<float>> rVec(1000, vector<float>(8)); 
    for (auto &v : rVec) {
        v[0] = ((float)rand()) * 0.001;
        v[1] = ((float)rand()) * 0.001;
        v[2] = ((float)rand()) * 0.001;
        v[3] = ((float)rand()) * 0.001;
        v[4] = ((float)rand()) * 0.001;
        v[5] = ((float)rand()) * 0.001;
        v[6] = ((float)rand()) * 0.001;
        v[7] = ((float)rand()) * 0.001;
    }

    system("PAUSE");
    tick();

    for (int n = 0; n < 50000; n++)
    for (int j = 0; j < rVec.size(); j++) {
        std::sort(rVec[j].begin(), rVec[j].end(), PredDefault<float>);
        std::sort(rVec[j].begin(), rVec[j].end(), PredDefaultReverse<float>);
        //Sort8(rVec[j].data(), PredDefault<float>);
        //Sort8(rVec[j].data(), PredDefaultReverse<float>);
    }

    cout << "\nTime: " << tick() << "\n";
    system("PAUSE");

    return 1;
}

在测试其中一个或另一个时添加/删除注释标记。

我并没有期望太多，但差别是10倍，赞成交换排序(在vs2012上的发布配置中完成的测试，并关闭了节能功能)。结果也证实了。是这样的吗？

Answer 1

有几个原因我可以马上想出来。

1. 你有硬编码的比较。这有助于管道衬里多指令，这使它的高效率.但是想象一下为N=1000编写代码。你必须写1000*1000的比较。
2. std::sort做O(nlogn)比较。但是这个大O符号对于大N是成立的，因为符号的常数可以是大的。因此，您不能通过运行范围为8个值来判断效率。