정렬 쌍 대 구조체 : 어느 것이 더 빠릅니까?

Question

죄송합니다, 내 나쁜에 대한 영어 :

나는 (STL을 사용하여) 쌍의 배열이 더 빠르다는 것을 알고 싶습니다. 또는 struct (C++)의 배열과 이유는 무엇입니까? 추가 정보를

는 코드 아래 참조 :

코드 1 : (제에 의해) 정렬 쌍

#include <algorithm> 

pair <int,int> client[100000]; 

sort(client,client+100000); 

코드 2 : 정렬 구조체 (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 : 정렬 구조체 (A 및 내부 연산자에 의해 <)

#include <algorithm> 

struct cl{ 
     int A,B; 

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

cl clients[100000]; 

sort(clients,clients+100000); 

어느 것이 더 낫습니까? 당신의 도움 :)

UPD에 대한

감사 : 나는 온라인 판사이 두 코드 (1, 2)에 대한 해결 문제를 사용합니다. 나는 코드 1에 대해 TL (제한 시간, 2 초)를 얻고 코드 2와 3 (62 밀리 초) 동안 AC를 얻습니다! 왜?? 그 차이는 어디입니까?

Answer 1

당신은 무엇을 알고 있습니까 std::pair 무엇입니까? 구조체 (또는 클래스, 이는 우리의 목적을 위해 C++에서 동일한 것입니다)입니다. 따라서 무엇이 더 빠른지 알고 싶다면 일반적인 조언이 적용됩니다. 테스트하고 플랫폼에서 직접 찾아야합니다. 그러나 가장 좋은 방법은 std::pair에 해당하는 정렬 논리를 구현하면 컴파일러가 데이터 형식의 이름이 std::pair 또는 다른 것인지 여부를 신경 쓰지 않기 때문에 동일한 성능을 얻을 수 있다는 것입니다.

게시 한 코드가 std::pair에 제공된 operator <과 기능적으로 동일하지 않습니다. 특히, 첫 번째 구성원 만 비교하고 둘 다 비교하지는 않습니다. 분명히 이것은 약간의 속도 향상을 가져올 수 있습니다 (그러나 실제 프로그램에서 주목할만큼 충분하지 않을 수도 있음).

Answer 2

나는이 두 가지 솔루션간에 큰 차이가 없다고 생각합니다.

그러나 모든 성능 관련 검색어와 마찬가지로 인터넷에서 누군가가 동일하거나 다른 사람보다 낫다고 말하기보다는 자신의 측정을하십시오. 때로는 구현의 미묘한 차이가 실제 결과에 많은 차이를 만듭니다.

는 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 

내가 벤치 마크를 세 번 실행, 그들은 ~ 안에 모두 나는 "함께 코드를 매쉬"다음 만든 위의 결과 중 0.1 초.

Edit2가 : 그리고 생성 된 코드에서 찾고, 그것은 "중간"기능은 비교가 pair 및 struct cl2 인라인 구성되어 있기 때문에, 꽤 오래 걸리지 만 struct cl1 인라인 될 수 없음을 매우 분명하다 - 따라서 모든 비교는 문자 그대로 함수 내에서 몇 가지 지침이 아니라 함수 호출을 작성합니다. 이것은 큰 오버 헤드입니다.