1 | #if !defined(__APPLE__) && !defined(__FreeBSD__) |
2 | #include <malloc.h> |
3 | #endif |
4 | #include <ext/bit_cast.h> |
5 | #include <Common/RadixSort.h> |
6 | #include <Common/Stopwatch.h> |
7 | #include <IO/ReadHelpers.h> |
8 | #include <Core/Defines.h> |
9 | |
10 | using Key = double; |
11 | |
12 | static void NO_INLINE sort1(Key * data, size_t size) |
13 | { |
14 | std::sort(data, data + size); |
15 | } |
16 | |
17 | static void NO_INLINE sort2(Key * data, size_t size) |
18 | { |
19 | radixSortLSD(data, size); |
20 | } |
21 | |
22 | static void NO_INLINE sort3(Key * data, size_t size) |
23 | { |
24 | std::sort(data, data + size, [](Key a, Key b) |
25 | { |
26 | return RadixSortFloatTransform<uint32_t>::forward(ext::bit_cast<uint32_t>(a)) |
27 | < RadixSortFloatTransform<uint32_t>::forward(ext::bit_cast<uint32_t>(b)); |
28 | }); |
29 | } |
30 | |
31 | |
32 | int main(int argc, char ** argv) |
33 | { |
34 | if (argc < 3) |
35 | { |
36 | std::cerr << "Usage: program n method\n" ; |
37 | return 1; |
38 | } |
39 | |
40 | size_t n = DB::parse<size_t>(argv[1]); |
41 | size_t method = DB::parse<size_t>(argv[2]); |
42 | |
43 | std::vector<Key> data(n); |
44 | |
45 | // srand(time(nullptr)); |
46 | |
47 | { |
48 | Stopwatch watch; |
49 | |
50 | for (auto & elem : data) |
51 | elem = rand(); |
52 | |
53 | watch.stop(); |
54 | double elapsed = watch.elapsedSeconds(); |
55 | std::cerr |
56 | << "Filled in " << elapsed |
57 | << " (" << n / elapsed << " elem/sec., " |
58 | << n * sizeof(Key) / elapsed / 1048576 << " MB/sec.)" |
59 | << std::endl; |
60 | } |
61 | |
62 | if (n <= 100) |
63 | { |
64 | std::cerr << std::endl; |
65 | for (const auto & elem : data) |
66 | std::cerr << elem << ' '; |
67 | std::cerr << std::endl; |
68 | } |
69 | |
70 | |
71 | { |
72 | Stopwatch watch; |
73 | |
74 | if (method == 1) sort1(data.data(), n); |
75 | if (method == 2) sort2(data.data(), n); |
76 | if (method == 3) sort3(data.data(), n); |
77 | |
78 | watch.stop(); |
79 | double elapsed = watch.elapsedSeconds(); |
80 | std::cerr |
81 | << "Sorted in " << elapsed |
82 | << " (" << n / elapsed << " elem/sec., " |
83 | << n * sizeof(Key) / elapsed / 1048576 << " MB/sec.)" |
84 | << std::endl; |
85 | } |
86 | |
87 | { |
88 | Stopwatch watch; |
89 | |
90 | size_t i = 1; |
91 | while (i < n) |
92 | { |
93 | if (!(data[i - 1] <= data[i])) |
94 | break; |
95 | ++i; |
96 | } |
97 | |
98 | watch.stop(); |
99 | double elapsed = watch.elapsedSeconds(); |
100 | std::cerr |
101 | << "Checked in " << elapsed |
102 | << " (" << n / elapsed << " elem/sec., " |
103 | << n * sizeof(Key) / elapsed / 1048576 << " MB/sec.)" |
104 | << std::endl |
105 | << "Result: " << (i == n ? "Ok." : "Fail!" ) << std::endl; |
106 | } |
107 | |
108 | if (n <= 1000) |
109 | { |
110 | std::cerr << std::endl; |
111 | |
112 | std::cerr << data[0] << ' '; |
113 | for (size_t i = 1; i < n; ++i) |
114 | { |
115 | if (!(data[i - 1] <= data[i])) |
116 | std::cerr << "*** " ; |
117 | std::cerr << data[i] << ' '; |
118 | } |
119 | |
120 | std::cerr << std::endl; |
121 | } |
122 | |
123 | return 0; |
124 | } |
125 | |