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
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
|
// This example shows how to sort structs using complex multiple part keys using
// string_sort.
//
// Copyright Steven Ross 2009-2014.
//
// Distributed under the Boost Software License, Version 1.0.
// (See accompanying file LICENSE_1_0.txt or copy at
// http://www.boost.org/LICENSE_1_0.txt)
// See http://www.boost.org/libs/sort for library home page.
#include <boost/sort/spreadsort/string_sort.hpp>
#include <boost/sort/spreadsort/float_sort.hpp>
#include <time.h>
#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
#include <vector>
#include <iostream>
#include <fstream>
#include <string>
using std::string;
using namespace boost::sort::spreadsort;
//[generalized_functors
struct DATA_TYPE {
time_t birth;
float net_worth;
string first_name;
string last_name;
};
static const int birth_size = sizeof(time_t);
static const int first_name_offset = birth_size + sizeof(float);
static const boost::uint64_t base_mask = 0xff;
struct lessthan {
inline bool operator()(const DATA_TYPE &x, const DATA_TYPE &y) const {
if (x.birth != y.birth) {
return x.birth < y.birth;
}
if (x.net_worth != y.net_worth) {
return x.net_worth < y.net_worth;
}
if (x.first_name != y.first_name) {
return x.first_name < y.first_name;
}
return x.last_name < y.last_name;
}
};
struct bracket {
inline unsigned char operator()(const DATA_TYPE &x, size_t offset) const {
// Sort date as a signed int, returning the appropriate byte.
if (offset < birth_size) {
const int bit_shift = 8 * (birth_size - offset - 1);
unsigned char result = (x.birth & (base_mask << bit_shift)) >> bit_shift;
// Handling the sign bit. Unnecessary if the data is always positive.
if (offset == 0) {
return result ^ 128;
}
return result;
}
// Sort a signed float. This requires reversing the order of negatives
// because of the way floats are represented in bits.
if (offset < first_name_offset) {
const int bit_shift = 8 * (first_name_offset - offset - 1);
unsigned key = float_mem_cast<float, unsigned>(x.net_worth);
unsigned char result = (key & (base_mask << bit_shift)) >> bit_shift;
// Handling the sign.
if (x.net_worth < 0) {
return 255 - result;
}
// Increasing positives so they are higher than negatives.
if (offset == birth_size) {
return 128 + result;
}
return result;
}
// Sort a string that is before the end. This approach supports embedded
// nulls. If embedded nulls are not required, then just delete the "* 2"
// and the inside of the following if just becomes:
// return x.first_name[offset - first_name_offset];
const unsigned first_name_end_offset =
first_name_offset + x.first_name.size() * 2;
if (offset < first_name_end_offset) {
int char_offset = offset - first_name_offset;
// This signals that the string continues.
if (!(char_offset & 1)) {
return 1;
}
return x.first_name[char_offset >> 1];
}
// This signals that the string has ended, so that shorter strings come
// before longer ones.
if (offset == first_name_end_offset) {
return 0;
}
// The final string needs no special consideration.
return x.last_name[offset - first_name_end_offset - 1];
}
};
struct getsize {
inline size_t operator()(const DATA_TYPE &x) const {
return first_name_offset + x.first_name.size() * 2 + 1 +
x.last_name.size();
}
};
//] [/generalized_functors]
//Pass in an argument to test std::sort
int main(int argc, const char ** argv) {
std::ifstream indata;
std::ofstream outfile;
bool stdSort = false;
unsigned loopCount = 1;
for (int u = 1; u < argc; ++u) {
if (std::string(argv[u]) == "-std")
stdSort = true;
else
loopCount = atoi(argv[u]);
}
double total = 0.0;
//Run multiple loops, if requested
std::vector<DATA_TYPE> array;
for (unsigned u = 0; u < loopCount; ++u) {
indata.open("input.txt", std::ios_base::in | std::ios_base::binary);
if (indata.bad()) {
printf("input.txt could not be opened\n");
return 1;
}
// Read in the data.
DATA_TYPE inval;
while (!indata.eof() ) {
indata >> inval.first_name;
indata >> inval.last_name;
indata.read(reinterpret_cast<char *>(&(inval.birth)), birth_size);
indata.read(reinterpret_cast<char *>(&(inval.net_worth)), sizeof(float));
// Handling nan.
if (inval.net_worth != inval.net_worth) {
inval.net_worth = 0;
}
if (indata.eof())
break;
array.push_back(inval);
}
indata.close();
// Sort the data.
clock_t start, end;
double elapsed;
start = clock();
if (stdSort) {
std::sort(array.begin(), array.end(), lessthan());
} else {
//[generalized_functors_call
string_sort(array.begin(), array.end(), bracket(), getsize(), lessthan());
//] [/generalized_functors_call]
}
end = clock();
elapsed = static_cast<double>(end - start);
if (stdSort) {
outfile.open("standard_sort_out.txt", std::ios_base::out |
std::ios_base::binary | std::ios_base::trunc);
} else {
outfile.open("boost_sort_out.txt", std::ios_base::out |
std::ios_base::binary | std::ios_base::trunc);
}
if (outfile.good()) {
for (unsigned u = 0; u < array.size(); ++u)
outfile << array[u].birth << " " << array[u].net_worth << " "
<< array[u].first_name << " " << array[u].last_name << "\n";
outfile.close();
}
total += elapsed;
array.clear();
}
if (stdSort) {
printf("std::sort elapsed time %f\n", total / CLOCKS_PER_SEC);
} else {
printf("spreadsort elapsed time %f\n", total / CLOCKS_PER_SEC);
}
return 0;
}
|
