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

順位表を使ったソートの実装

　今回、ソート対象となる要素列内の各要素の入れ替えを行いません。そのかわり「順位表」を作ります。

　例えば要素列double data[4] = { 3.3, 1.1, 2.2, 4.4 }があったとき、同じ要素数のint列 int index[4]を用意して、index[i]が「data[N]をソートしたとき、i番目に位置する要素の添え字（index）」となるようにindex[4]のナカミを埋めよう、と。

list-04

double data[4] = { 3.3, 1.1, 2.2, 4.4 };
int   index[4] = { 1, 2, 0, 3 }; // これを作ることができれば
// 昇順に出力される
for ( int i = 0; i < 4; ++i ) {
  cout << data[index[i]] << endl;
}

　順位表はstd::sortに与える関数オブジェクトをひとひねりすることで簡単に作れます。

　まずint列 int index[N]を用意し、そのナカミを0, 1, 2 ... N-1で埋めます。しかるのちindex[N}をソートするのですが、このときstpd::sortの第3引数には順位表作成用の関数オブジェクトを与えます。関数オブジェクトに渡される2つの値a, b（ソート対象がint列なので型はどちらもint）に対しdata[a] < data[b]のときtrueを返せば、a, bはdata[N]の各要素の位置として扱われますよね。

　index[N = { 0, 1, 2 ... N-1 }をdata[N]の各要素の大小関係に基づいてソートするので、ソート完了後のindex[N]はdata[N]をソートしたときの順位表がindex[N]にできあがります。

list-05

#include <iostream>
#include <iterator>  // begin, end
#include <numeric>   // iota
#include <algorithm> // sort
using namespace std;

int main() {
  const int N = 4;
  double data[N] = { 3.3, 1.1, 2.2, 4.4 };
  int index[N];
  iota(begin(index), end(index), 0); // index を 0, 1, 2 <... N-1 で埋める
  sort(begin(index), end(index),
       [&](int a, int b) { return data[a] < data[b];});

  // 昇順に出力されることを確認
  for ( int i = 0; i < 4; ++i ) {
    cout << index[i] << " : "
         << data[index[i]] << endl;
  }
}

　ソート中に行われる要素の比較が少しばかりややこしくなったことでソートにかかる処理時間が増えているに違いありません、実測してみましょう。通常のソートと順位表方式とで処理時間を比較します。

list-06

#include <iterator>  // begin, end
#include <iostream>  // cout, endl
#include <iomanip>   // setw
#include <ctime>     // clock
#include <numeric>   // iota
#include <algorithm> // sort, is_sorted, generate_n
#include <random>    // mt19937,distribution
#include <chrono>    // chrono
using namespace std;

template<typename Function>
float measure_time(Function f) {
  auto start = chrono::high_resolution_clock::now();
  f();
  auto stop = chrono::high_resolution_clock::now();
  return chrono::duration_cast<chrono::microseconds>(stop - start).count() / 1000.0f;
}

int main() {
  const size_t N = 1000000;
  using type = double;

  // sortの対象となるdouble列を用意する
  vector<type> source(N);
  mt19937 gen(clock());
  uniform_real_distribution<double> dist;
  generate_n(source.begin(), N, [&]() { return dist(gen); });

  std::vector<type> data;

  {
  cout << "normal :\n";
  data.assign(begin(source), end(source));
  float elapsed = measure_time([&]() { std::sort(begin(data), end(data)); });
  cout << (is_sorted(begin(data), end(data)) ? " ok" : " ng") << " : " 
       << setw(10) << elapsed << "[ms]\n";
  }

  {
  cout << "index :\n";
  data.assign(begin(source), end(source));

  vector<int> index(N);
  iota(begin(index), end(index), 0);
  float elapsed = measure_time([&]() {
                   std::sort(begin(index), end(index),
                             [&](int a, int b) { return data[a] < data[b];});
                  });

  vector<type> sorted(data.size());
  transform(begin(index), end(index), begin(sorted), [&](auto n) { return data[n]; });
  cout << (is_sorted(begin(sorted), end(sorted) ) ? " ok" : " ng") << " : " 
       << setw(10) << elapsed << "[ms]\n";
  }
}

fig-01

　結果はご覧のとおり、要素数百万で約3倍の処理時間になってます。要素の比較がindexを介した間接参照となるんで仕方ないかな。