current community

your communities

more stack exchange communities

Stack Exchange
tour help
Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.
up vote 1 down vote favorite

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?

share|improve this question
    
This doesn't look like you are asking for a code review !! –  JaDogg May 13 at 14:38

1 Answer 1

up vote 1 down vote accepted

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? :)

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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