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
10using Key = double;
11
12static void NO_INLINE sort1(Key * data, size_t size)
13{
14 std::sort(data, data + size);
15}
16
17static void NO_INLINE sort2(Key * data, size_t size)
18{
19 radixSortLSD(data, size);
20}
21
22static 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
32int 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