1

我想知道对数组进行排序是否std::pair更快，还是对数组进行排序struct？

这是我的代码段：

代码#1：排序std::pair数组（按第一个元素）：

#include <algorithm>

pair <int,int> client[100000];

sort(client,client+100000);

代码#2：排序struct（按A）：

#include <algorithm>

struct cl{
      int A,B;
}

bool cmp(cl x,cl y){
      return x.A < y.A;
}

cl clients[100000];

sort(clients,clients+100000,cmp);

代码#3：排序struct（按A和内部运算符<）：

#include <algorithm>

struct cl{
      int A,B;

      bool operator<(cl x){
            return A < x.A;
      }
}

cl clients[100000];

sort(clients,clients+100000);

更新：我使用这些代码来解决在线法官中的问题。我对代码 #1 的时间限制为 2 秒，并接受代码 #2 和 #3（在 62 毫秒内运行）。与其他代码相比，为什么代码 #1 需要这么多时间？区别在哪里？

4

2 回答 2

3

你知道std::pair是什么吗？它是一个结构（或类，在 C++ 中与我们的目的相同）。因此，如果您想知道什么更快，通常的建议适用：您必须对其进行测试并在您的平台上自己找出答案。但最好的选择是，如果您实现与 等效的排序逻辑std::pair，您将获得等效的性能，因为编译器并不关心您的数据类型的名称是std::pair什么。

但请注意，您发布的代码在功能上与operator <提供的std::pair. 具体来说，您只比较第一个成员，而不是两者。显然，这可能会导致一些速度增益（但可能不足以在任何实际程序中注意到）。

于 2013-02-22T14:00:47.360 回答
1

我估计这两种解决方案之间没有太大区别。

但就像所有与性能相关的查询一样，不要依赖互联网上的人告诉他们是相同的，或者一个比另一个更好，而是自己进行测量。有时，实现上的细微差别会对实际结果产生很大影响。

话虽如此， 的 实现std::pair是一个具有两个成员的结构（或类），first和second，所以我很难想象这里有什么真正的区别 - 你只是用你自己的比较函数来实现你自己的对已经存在的对所做的相同的事情......无论是在类的内部函数中还是作为独立函数都不太可能产生太大的不同。

编辑：我做了以下“将代码混合在一起”：

#include <algorithm>
#include <iostream>
#include <iomanip>
#include <cstdlib>

using namespace std;

const int size=100000000;

pair <int,int> clients1[size];

struct cl1{
    int first,second;
};


cl1 clients2[size];

struct cl2{
      int first,second;

      bool operator<(const cl2 x) const {
            return first < x.first;
      }
};
cl2 clients3[size];




template<typename T>
void fill(T& t)
{
    srand(471117);   // Use same random number each time/ 
    for(size_t i = 0; i < sizeof(t) / sizeof(t[0]); i++)
    {
    t[i].first = rand();
    t[i].second = -t[i].first;
    }
}



void func1()
{
    sort(clients1,clients1+size);
}


bool cmp(cl1 x, cl1 y){
      return x.first < y.first;
}

void func2()
{
    sort(clients2,clients2+size,cmp);
}


void func3()
{
    sort(clients3,clients3+size);
}

void benchmark(void (*f)(), const char *name)
{
    cout << "running " << name << endl;
    clock_t time = clock();
    f();
    time = clock() - time;
    cout << "Time taken = " << (double)time / CLOCKS_PER_SEC << endl;
}

#define bm(x) benchmark(x, #x)

int main()
{
    fill(clients1);
    fill(clients2);
    fill(clients3);

    bm(func1);
    bm(func2);
    bm(func3);
}

结果如下：

running func1
Time taken = 10.39
running func2
Time taken = 14.09
running func3
Time taken = 10.06

我运行了 3 次基准测试，它们都在上述结果的 ~0.1 秒内。

Edit2：查看生成的代码，很明显“中间”函数需要更长的时间，因为比较是内联的pairand struct cl2，但不能内联struct cl1- 所以每次比较都会产生一个函数调用，而不是函数内部的一些指令。这是一个很大的开销。

于 2013-02-22T14:01:17.847 回答