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

これら2つのソリューションの間に大きな違いはないと推定します。

しかし、すべてのパフォーマンス関連のクエリと同様に、インターネット上の誰かが同じである、または一方が他方よりも優れていると言うのではなく、独自の測定を行います。場合によっては、実装の微妙な違いが実際の結果に大きな違いをもたらすことがあります。

そうは言っても、の実装はstd::pair2つのメンバーを持つ構造体（またはクラス）で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秒以内です。

pairEdit2：生成されたコードを見ると、比較はとに対してインラインで行われるため、「中間」関数にはかなり長い時間がかかることは明らかですが、インラインにstruct cl2することはできませんstruct cl1-したがって、すべての比較は文字通り関数呼び出しを行います、関数内のいくつかの命令ではなく。これは大きなオーバーヘッドです。

于 2013-02-22T14:01:17.847 に答える