「入れ替えを行わないソート」のおはなし

要素の交換回数による影響

　ソートは要素の比較と交換を何度も行うことで実現されています。比較に要する時間がソート時間に大きく影響することを示しました。では交換はどうでしょう。要素の交換は要するに何回かのコピーです。ソート中にそれほどの回数比較とコピーが行われるのか、調べてみました。

list-07

#include <iostream>
#include <algorithm>
#include <numeric>
#include <vector>
#include <random>
#include <ctime>
#include <cassert>
using namespace std;

class Item {
private:
  static int compare_;
  static int copy_;
public:
  static int  compare() { return compare_; }
  static int  copy()    { return copy_; }
  static void clear() { compare_ = 0;  copy_ = 0; }

private:
  int value_;
public:
  explicit Item(int v =0) : value_(v) {}
  Item& operator=(int v)           { value_ = v; return *this; }

  // copy constructor
  Item(const Item& other) : value_(other.value_) { ++copy_; }
  Item(Item&& other)      : value_(other.value_) { ++copy_; }

  // copy operator
  Item& operator=(const Item& rhs) { value_ = rhs.value_; ++copy_; return *this; }
  Item& operator=(Item&& rhs)      { value_ = rhs.value_; ++copy_; return *this; }

  friend bool operator<(const Item& lhs, const Item& rhs) 
    { ++Item::compare_; return lhs.value_ < rhs.value_; } 
};

int Item::compare_;
int Item::copy_;

int main() {
  const int N = 1000;
  vector<Item> data(N);
  iota(begin(data), end(data), 0);
  mt19937 rand(clock());

  int compare = 0;
  int copy = 0;
  const int rep = 10;
  for ( int i = 0;  i < rep; ++i ) {
    shuffle(begin(data), end(data), rand);
    Item::clear();
    sort(begin(data), end(data));
    cout << Item::compare() << " compare\t"
         << Item::copy() << " copy\n";
    compare += Item::compare();
    copy += Item::copy();
    assert( is_sorted(begin(data), end(data)));
  }
  cout << "----- avarage:\n"
       << compare/rep << " compare\t"
       << copy/rep << " copy\n";
}

fig-02

　要素数1000の要素列をソートするのに比較／コピーどちらも15,000回ほど行われるんだそうです。比較は言うに及ばず、コピーもかなり頻繁に行われています。ってことは、コピーにかかるコスト（コピーにかかる時間）の大きな要素であれば、要素の交換を行わない順位表方式のほうが速くなると考えられます。順位表方式で交換されるのはintなので、コピー・コストはさほどに大きくはないでしょうから。

　やってみましょう。コピー・コストの大きな要素heavyを定義し、その配列を直接ソートするのと順位表方式とでそれぞれの処理時間を比較します。

list-08

template<typename T, std::size_t N>
struct heavy {
  T body[N];
  heavy() = default;
  heavy(T val) { std::fill_n(body, N, val); }
  heavy(const heavy& other) { std::copy(other.body, other.body+N, body);}
  heavy& operator=(const heavy& other) { std::copy(other.body, other.body+N, body); return *this; }
  bool operator<(const heavy& other) const { return body[0] < other.body[0]; }
};

　heavyすなわち32個のdouble列を内包する要素をソート対象とし、要素数百万で比較したのがコチラ：

fig-03

　案の定、処理時間が逆転しましたね。交換（すなわちコピー）にかかる時間が抑えられることで順位表方式のほうが速くなっています。