PS 하다보면 std::pair 정렬할 일이 오지게 많다. 그래서 어떻게 정렬하는게 가장 빠를지, 한 번 비교해봤다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
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());
}
cs


각각 함수 호출, 람다, U64 캐스팅을 사용한 std::pair정렬.

[환경]


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

[방법]


1024회 시행 후 양 끝의 5%는 버리기

[결과]


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
[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
 
----------
 
[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
 
----------
 
[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
 
----------
 
[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
 
----------
 
[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
cs


[결론]

U64로 캐스팅 후 정렬시 1.5 ~ 2배의 성능 개선. 물론 구현에 의존적이고 음수일 때는 사용 불가능. 기수정렬 등의 방법을 사용하면 차이가 더욱 차이가 드라마틱할 것이다. 누가 좀 해줘.


끗.