std::pair를 (야매로) 정렬하기

오랜만에 프로그래밍 이야기!

PS를 하다보면, std::pair를 참 많이 쓰게 됩니다. 짬좀 쌓인 PS러(?) 열에 아홉은 using Pii = std::pair< int, int >;를 박아놓고 시작합니다. 하지만 std::pair를 그냥 쓰는 경우는 잘 없죠. 주로 배열이나 std::vector에 담고 정렬하게 됩니다. 오늘은 이 정렬에 대한 이야기입니다.


std::sort는 비교 기반 정렬을 수행합니다. 내부적으로 operator< 혹은 Compare를 만족하는 비교자를 사용해 비교합니다.

한편, std::pairoperator<는 다음과 같이 구현되어 있습니다(from GCC).

  template<typename _T1, typename _T2>
    inline _GLIBCXX_CONSTEXPR bool
    operator<(const pair<_T1, _T2>& __x, const pair<_T1, _T2>& __y)
    { return __x.first < __y.first
	     || (!(__y.first < __x.first) && __x.second < __y.second); }

이 또한 operator<에 의존해 구현되어 있죠. Compare를 만족한다면, 논리적으로 다음과 동치입니다.

  template<typename _T1, typename _T2>
    inline _GLIBCXX_CONSTEXPR bool
    operator<(const pair<_T1, _T2>& __x, const pair<_T1, _T2>& __y)
    { return __x.first <  __y.first
	     || (__x.first == __y.first && __x.second < __y.second); }

훨씬 익숙한 형태로, 우선 first의 값을 비교하고, first의 값이 같다면 second의 값을 비교합니다.


문제는 second부터 비교하는 경우입니다. 물론, 정렬을 한 번만 호출하는 경우라면 큰 문제가 되지 않습니다. 그냥 데이터를 받을 때 firstsecond를 바꾸면 되니까요. 하지만 둘 다 사용하는 경우라면 커스텀 비교자를 사용해야 합니다. 커스텀 비교자 사용시의 유의사항은 여기에 올린 적이 있습니다.

int N;
std::pair< U32, U32 > data[ SIZE ];

// 주절주절

std::sort(data, data + N, [](auto lhs, auto rhs) {
    return (lhs.second <  rhs.second)
        || (lhs.second == rhs.second && lhs.first < rhs.first);
});

이건 람다를 사용하는 예시입니다. 모던 C++을 쓸 수 없는 상황이라면 Functor를 만들어야 할겁니다. 하지만 어느 쪽이 됐든, 길고 귀찮습니다. 우리는 대회에서 귀중한 시간을 1초도 낭비할 수가 없습니다.


제가 제시하는 대안은 다음과 같습니다.

std::sort((U64*)data, (U64*)data + N);

이 트릭의 원리는 다음과 같습니다. 우선, firstsecond보다 낮은 주소에 위치하게 됩니다. 그런데, 우리가 자주 사용하는 컴퓨터(x86 등등), 적어도 채점용 컴퓨터는 리틀 엔디언을 사용합니다. 즉, second가 높은 자릿수에 오게 됩니다. 따라서 U32 두 개를 U64 취급해 버리면 second부터 정렬하는 것과 같은 효과를 낼 수 있습니다.

물론 트릭이니만큼 주의할 사항도 있습니다. 우선, 음수에 대해 사용할 수 없습니다. 또한, 구현과 엔디언에 의존적입니다. 다음의 테스트 코드를 통해 꼭 확인해 보시기 바랍니다.

std::pair< U16, U16 > p = { 0x1234, 0x5678 };
printf("%X", (U32&)p);    // 56781234

추가로 궁금하신 사항이 있으면 글 남겨주세요.

3 Likes

blah blah 불-편

수정해드렸읍니다.

참고: https://english.stackexchange.com/questions/79439/is-blah-blah-blah-the-most-common-spelling

:joy::thinking:

성능을 측정해 보았습니다.


[환경]
CPU: Intel Core i5-7200U
RAM: 8GB
OS: Manjaro 18.1.2
Compiler: GCC 9.1
Compile Optimization Level: O3


[방법]
1024회 시행 후 양 끝의 5%는 버리기


[U32 균등분포]

코드
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <numeric>
#include <random>
#include <chrono>

using U32 = unsigned int;
using U64 = unsigned long long;

template< typename F >
class Benchmark {
private:
    std::string name;
    F func;
    double ratio;

public:
    Benchmark(std::string name, F func, double ratio = 0.9): name(name), func(func), ratio(ratio) {}

    auto run(auto... paras) {
        auto start = std::chrono::system_clock::now();
        func(paras...);
        auto end   = std::chrono::system_clock::now();
        return std::chrono::duration< double >(end - start).count();
    }

    auto report(auto N, auto... paras) {
        int begin = N * (1 - ratio) * 0.5, end = N * (1 + ratio) * 0.5;
        std::vector< double > v(N);

        for(auto& i: v)
            i = run(paras...);

        std::sort(v.begin(), v.end());

        double sum = std::accumulate(v.begin() + begin, v.begin() + end, double(0)), mean = sum / (end - begin);

        std::cout << '[' << name << "]\n";
        std::cout << "mean: " << mean         << '\n'
                  << "min : " << v[ begin   ] << '\n'
                  << "max : " << v[ end - 1 ] << "\n\n";
    }
};

auto cmp(std::pair< U32, U32 > lhs, std::pair< U32, U32 > rhs) {
    return (lhs.second <  rhs.second)
        || (lhs.second == rhs.second && lhs.first < rhs.first);
}

auto sort1(std::vector< std::pair< U32, U32 > >& v) {
    std::sort(v.begin(), v.end(), cmp);
}

auto sort2(std::vector< std::pair< U32, U32 > >& v) {
    std::sort(v.begin(), v.end(), [](auto lhs, auto rhs) {
        return (lhs.second <  rhs.second)
            || (lhs.second == rhs.second && lhs.first < rhs.first);
    });
}

auto sort3(std::vector< std::pair< U32, U32 > >& v) {
    std::sort((U64*)v.data(), (U64*)v.data() + v.size());
}
결과
<N = 16>
[Function Call]
mean: 2.15239e-07
min : 2.12e-07
max : 2.6e-07

[Lambda]
mean: 9.92562e-08
min : 9e-08
max : 1.83e-07

[Trick]
mean: 7.3823e-08
min : 7.3e-08
max : 7.5e-08

----------

<N = 256>
[Function Call]
mean: 8.61356e-06
min : 8.086e-06
max : 1.1055e-05

[Lambda]
mean: 2.16294e-06
min : 1.89e-06
max : 3.157e-06

[Trick]
mean: 1.96644e-06
min : 1.558e-06
max : 2.672e-06

----------

<N = 4096>
[Function Call]
mean: 0.000300265
min : 0.000296068
max : 0.000357811

[Lambda]
mean: 0.000280525
min : 0.000262243
max : 0.000343163

[Trick]
mean: 0.000190061
min : 0.000180194
max : 0.000232383

----------

<N = 65536>
[Function Call]
mean: 0.00639728
min : 0.00637105
max : 0.00660359

[Lambda]
mean: 0.00553306
min : 0.00550157
max : 0.00588904

[Trick]
mean: 0.0039964
min : 0.00398549
max : 0.0040574

----------

<N = 1048576>
[Function Call]
mean: 0.126889
min : 0.125817
max : 0.133742

[Lambda]
mean: 0.112676
min : 0.112321
max : 0.113784

[Trick]
mean: 0.0803867
min : 0.0801385
max : 0.0815312

결론: 대략 1.5 ~ 2배의 성능차이. 이 정도면 오히려 손품을 팔아서라도 꼼수를 쓸 가치가 있다! 또한, 기수정렬 등의 방법을 사용한다면 수 배 더 개선할 수 있는 여지가 있다.

1 Like

와웅

감탄은 필요없고 추천이나 박으세오 휴먼 :joy:

데이터 영역과 프로그램 영역을 떼어놓는다는게 이런 의미였군요…
그냥 데이터만 보면 두개 데이터가 연속적으로 붙어있는 형태겠네요.

그런데 Second부터 비교하는 경우가 무슨뜻인지 잘 모르겠습니다.
말 그대로 Second부터 비교할 특수한 경우만 저 트릭을 사용한다는 뜻인가요?
그리고 N을 더한건 주솟값인가요?

요거는 좀 다른 말씀을 하시고 있는 것 같고,

요건 메모리 구조나 엔디안 이야기.

커스텀 비교자를 사용하지 않을 때는 operator<를 호출하는데, std::pairoperator<first부터 비교합니다. second부터 비교하는 상황이라면 새로 함수를 작성해줘야 합니다.

여기서 다루고 있는 트릭은 새로 함수를 작성하지 않고도 second부터 비교할 수 있게 해주는데, 사실 기본 operator<보다도 빠르다는 이야기입니다.

1 Like

근데 이런 대회에서는 써야만 하는 언어가 있나요? 아니면 각자 다른 언어를 써도 되나요?

예를 들어 정보올림피아드는 C/C++, JAVA, Python을 사용할 수 있지만 성능 혹은 라이브러리 등의 이유로 C++이 선호됩니다. 3, 4번 문제는 C++로밖에 풀 수 없는 경우도 있습니다. 기업용 코테도 경우에 따라 다르지만 대부분 C++을 사용할 수 있으며, 크게 유리합니다.

1 Like

아 글쿤요 감사합니다

c++를 잘하려면 하드웨어적 특성을 상당히 잘 알아야 하네요 ㅎㅎ

저는 아직 미숙하지만 혹시 이런 쪽에 관심이 있으시다면 컴퓨터 구조 및 설계, 컴퓨터 프로그래밍의 예술, 해커의 기쁨 등의 책들을 추천드립니다.

컴구조는 학교에서 배웠는데 나머지 책들도 한번 읽어봐야겠네요 ㅎㅎ 감사합니당

ㅋㅋㅋㅋㅋㅋㅋ 코드가 굉장히 더러운 느낌이 드는데 한편으론 또 매력적이네요…
이게 괴랄한 방법으로 최적화된 코드의 매력인 것 같습니다. 비트연산부터 시작해서…

실제로 실무에서도 흔히 쓰는 트릭이예요.

물론 아직까지는 64비트 정수형 처리가 느려서리
32비트 비교가 더 빠릅니다만.
( first 만 비교하고 second 를 비교하지 않는 indexing 의 경우엔 분리하는게 낫단 소리 )

다시 읽어보니 second 부터 비교의 케이스를 문제 삼은거군요. 흐흠.
실무에선 기수정렬해야지.

서비스로 코세님께서 기수정렬 보여주시면 수능을 잘 볼 수 있을것 같습니다. :joy:

기수정렬 제대로 하는거야 코테에선 못 써먹잖아.

1 Like

아몰랑 제가 수능 못보면 아무튼 코세님때문임 빼애액 :laughing:

성능체크 할때 캐시로드 된거랑 로드 안된거 차이 크고
터보부스트 들어갔을때 또 다르다~ 시간 재는건 문제 있음. 클럭을 재~
여러번 재야되고