]>
Commit | Line | Data |
---|---|---|
11fdf7f2 TL |
1 | // spreadsort float functor sorting example. |
2 | // | |
3 | // Copyright Steven Ross 2009. | |
4 | // | |
5 | // Distributed under the Boost Software License, Version 1.0. | |
6 | // (See accompanying file LICENSE_1_0.txt or copy at | |
7 | // http://www.boost.org/LICENSE_1_0.txt) | |
8 | ||
9 | // See http://www.boost.org/libs/sort for library home page. | |
10 | ||
11 | // Caution: this file contains Quickbook markup as well as code | |
12 | // and comments, don't change any of the special comment markups! | |
13 | ||
14 | #include <boost/sort/spreadsort/spreadsort.hpp> | |
15 | #include <time.h> | |
16 | #include <stdio.h> | |
17 | #include <stdlib.h> | |
18 | #include <algorithm> | |
19 | #include <vector> | |
20 | #include <string> | |
21 | #include <fstream> | |
22 | #include <sstream> | |
23 | #include <iostream> | |
24 | ||
25 | using namespace boost::sort::spreadsort; | |
26 | ||
27 | //[float_functor_types | |
28 | #define CAST_TYPE int | |
29 | #define KEY_TYPE float | |
30 | //] [/float_functor_types] | |
31 | ||
32 | ||
33 | //[float_functor_datatypes | |
34 | struct DATA_TYPE { | |
35 | KEY_TYPE key; | |
36 | std::string data; | |
37 | }; | |
38 | //] [/float_functor_datatypes] | |
39 | ||
40 | ||
41 | //[float_functor_rightshift | |
42 | // Casting to an integer before bitshifting | |
43 | struct rightshift { | |
44 | int operator()(const DATA_TYPE &x, const unsigned offset) const { | |
45 | return float_mem_cast<KEY_TYPE, CAST_TYPE>(x.key) >> offset; | |
46 | } | |
47 | }; | |
48 | //] [/float_functor_rightshift] | |
49 | ||
50 | //[float_functor_lessthan | |
51 | struct lessthan { | |
52 | bool operator()(const DATA_TYPE &x, const DATA_TYPE &y) const { | |
53 | return x.key < y.key; | |
54 | } | |
55 | }; | |
56 | //] [/float_functor_lessthan] | |
57 | ||
58 | // Pass in an argument to test std::sort | |
59 | // Note that this converts NaNs and -0.0 to 0.0, so that sorting results are | |
60 | // identical every time | |
61 | int main(int argc, const char ** argv) { | |
62 | size_t uCount,uSize=sizeof(DATA_TYPE); | |
63 | bool stdSort = false; | |
64 | unsigned loopCount = 1; | |
65 | for (int u = 1; u < argc; ++u) { | |
66 | if (std::string(argv[u]) == "-std") | |
67 | stdSort = true; | |
68 | else | |
69 | loopCount = atoi(argv[u]); | |
70 | } | |
71 | std::ifstream input("input.txt", std::ios_base::in | std::ios_base::binary); | |
72 | if (input.fail()) { | |
73 | printf("input.txt could not be opened\n"); | |
74 | return 1; | |
75 | } | |
76 | double total = 0.0; | |
77 | std::vector<DATA_TYPE> array; | |
78 | input.seekg (0, std::ios_base::end); | |
79 | size_t length = input.tellg(); | |
80 | uCount = length/uSize; | |
81 | //Run multiple loops, if requested | |
82 | for (unsigned u = 0; u < loopCount; ++u) { | |
83 | input.seekg (0, std::ios_base::beg); | |
84 | //Conversion to a vector | |
85 | array.resize(uCount); | |
86 | unsigned v = 0; | |
87 | while (input.good() && v < uCount) { | |
88 | input.read(reinterpret_cast<char *>(&(array[v].key)), | |
89 | sizeof(array[v].key)); | |
90 | //Checking for denormalized numbers; float_sort looks too fast on them. | |
91 | if (!(float_mem_cast<KEY_TYPE, CAST_TYPE>(array[v].key) & 0x7f800000)) { | |
92 | //Make the top exponent bit high | |
93 | CAST_TYPE temp = 0x40000000 | | |
94 | float_mem_cast<KEY_TYPE, CAST_TYPE>(array[v].key); | |
95 | memcpy(&(array[v].key), &temp, sizeof(KEY_TYPE)); | |
96 | } | |
97 | //Testcase doesn't sort NaNs; they just cause confusion | |
98 | if (!(array[v].key < 0.0) && !(0.0 < array[v].key)) | |
99 | array[v].key = 0.0; | |
100 | //Adding the data, in this case a string | |
101 | std::stringstream intstr; | |
102 | intstr << array[v].key; | |
103 | array[v].data = intstr.str(); | |
104 | ++v; | |
105 | } | |
106 | clock_t start, end; | |
107 | double elapsed; | |
108 | start = clock(); | |
109 | if (stdSort) | |
110 | std::sort(array.begin(), array.end(), lessthan()); | |
111 | else | |
112 | float_sort(array.begin(), array.end(), rightshift(), lessthan()); | |
113 | end = clock(); | |
114 | elapsed = static_cast<double>(end - start) ; | |
115 | std::ofstream ofile; | |
116 | if (stdSort) | |
117 | ofile.open("standard_sort_out.txt", std::ios_base::out | | |
118 | std::ios_base::binary | std::ios_base::trunc); | |
119 | else | |
120 | ofile.open("boost_sort_out.txt", std::ios_base::out | | |
121 | std::ios_base::binary | std::ios_base::trunc); | |
122 | if (ofile.good()) { | |
123 | for (unsigned v = 0; v < array.size(); ++v) { | |
124 | ofile.write(reinterpret_cast<char *>(&(array[v].key)), | |
125 | sizeof(array[v].key)); | |
126 | ofile << array[v].data; | |
127 | } | |
128 | ofile.close(); | |
129 | } | |
130 | total += elapsed; | |
131 | array.clear(); | |
132 | } | |
133 | if (stdSort) | |
134 | printf("std::sort elapsed time %f\n", total / CLOCKS_PER_SEC); | |
135 | else | |
136 | printf("spreadsort elapsed time %f\n", total / CLOCKS_PER_SEC); | |
137 | return 0; | |
138 | } |