1
\$\begingroup\$

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?

\$\endgroup\$
  • \$\begingroup\$ This doesn't look like you are asking for a code review !! \$\endgroup\$ – bhathiya-perera May 13 '15 at 14:38
2
\$\begingroup\$

You spend a lot of lines of code trying to get the expressions lessthan(), getsize(), and bracket() to behave like plain old functions. Consider just using plain old functions, instead. For example:

static uint8_t get_char(int x, size_t offset)
{
    const int bit_shift = 8 * (sizeof(int) - offset - 1);
    uint8_t result = (x >> bit_shift) & 0xFF;
    if (offset == 0) result ^= 128;
    return result;
}

static uint8_t bracket(const std::pair<int,int>& x, size_t offset)
{
    if (offset < sizeof(int))
      return get_char(x.first, offset);
    return get_char(x.second, offset - sizeof(int));
}

...
string_sort(a.begin(), a.end(), bracket, getsize(), lessthan());

You could also productively replace the expression getsize() with

auto getsize = [](auto){ return 2*sizeof(int); };

...
string_sort(a.begin(), a.end(), bracket, getsize, lessthan());

Finally, lessthan is equivalent to std::less<std::pair<int,int>>, so you can just write

string_sort(a.begin(), a.end(), bracket, getsize, std::less<>());

That's the kind of shortening you were looking for, right? :)

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.