Boost 1.58 has new library spreadsort, so I tried it out. I wrote simple sample for sorting vector of pairs of int:
#include <chrono>
#include <iomanip>
#include <boost/sort/sort.hpp>
// based on http://www.boost.org/doc/libs/develop/libs/sort/doc/html/sort/sort_hpp/string_sort.html
struct lessthan
{
inline bool operator()(const std::pair<int, int> &x, const std::pair<int, int> &y) const
{
return x < y;
}
};
struct bracket
{
inline unsigned char operator()(const std::pair<int, int> &x, size_t offset) const
{
if (offset < sizeof(int))
return get_char(x.first, offset);
return get_char(x.second, offset - sizeof(int));
}
private:
inline unsigned char get_char(int x, size_t offset) const
{
static const boost::uint64_t base_mask = 0xff;
const int bit_shift = 8 * (sizeof(int) - offset - 1);
unsigned char result = (x & (base_mask << bit_shift)) >> bit_shift;
if (offset == 0)
return result ^ 128;
return result;
}
};
struct getsize
{
inline size_t operator()(const std::pair<int, int> &) const
{
return 2 * sizeof(int);
}
};
bool verify_sorted(const std::vector<std::pair<int, int>> & a)
{
lessthan ls;
for (size_t i = 0; i + 1 < a.size(); i++)
{
if (ls(a[i + 1], a[i]))
return false;
}
return true;
}
int main()
{
std::vector<std::pair<int, int>> r;
srand(12345);
for (size_t i = 0; i < 10000000; i++)
r.push_back(std::make_pair(rand(), rand()));
{
std::vector<std::pair<int, int>> a = r;
auto t_start = std::chrono::high_resolution_clock::now();
std::sort(a.begin(), a.end());
auto t_end = std::chrono::high_resolution_clock::now();
std::cout << std::fixed << std::setprecision(2) << "CPU time used (std::sort): "
<< std::chrono::duration<double, std::milli>(t_end - t_start).count()
<< " ms\n";
std::cout << (verify_sorted(a) ? "OK." : "FAIL!") << std::endl;
}
{
std::vector<std::pair<int, int>> a = r;
auto t_start = std::chrono::high_resolution_clock::now();
boost::sort::spreadsort::string_sort(a.begin(), a.end(), bracket(), getsize(), lessthan());
auto t_end = std::chrono::high_resolution_clock::now();
std::cout << std::fixed << std::setprecision(2) << "CPU time used (boost::sort::spreadsort::string_sort): "
<< std::chrono::duration<double, std::milli>(t_end - t_start).count()
<< " ms\n";
std::cout << (verify_sorted(a) ? "OK." : "FAIL!") << std::endl;
}
}
It's faster then std::sort, but it's seems to me this implementation is to heavyweight and ugly for such a simple task. Can anyone propose better one?