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

順位表方式のもう一つの使いみち

　コピー・コストの大きな要素列のソートを速くするだけでなく、順位表方式の使いみちがもう一つあります。SOA（Structure of Array）のソートです。

　例えば"名前／身長／体重の組がN個"を、

list-09

struct record {
  string name;    // 名前
  double height;  // 身長
  double weightl; // 体重
};

record data[N];

なんてなコードで表現します。これがAOS（Array of Structure）、"まとまりの列"です。

　一方、こちらがSOA（Structure of Array）"列のまとまり"です。

list-10

  string   name[N];
  double height[N];
  double weight[N];

　数値／統計計算にはこっちの方が楽だったりします。というのも、BLASやLAPACKなどの数値計算ライブラリ／パッケージが提供する関数のほとんどが計算対象となる配列（とその大きさ）を引数に与えますから。AOSだと計算のたびにメンバごとの配列に転写したり計算後に書き戻したりと前処理・後処理が必要になりますからね。

　SOAのソートは、この例だとname, height, weightの各要素を連動させて要素の入れ替えることになりますが、順位表方式なら要素の入れ替えを行わないので速いし簡単。

list-11

#include <iostream>
#include <iterator>
#include <numeric>   // iota
#include <algorithm> // sort
#include <string>    // string
using namespace std;

int main() {
  // SOA（Structure of Array）
  const int N = 5;
  string   name[N] = { "あいかわ", "いのうえ", "うちむら", "えがしら", "おかもと" };
  double height[N] = { 133.3,      111.1,      144.4,      122.2,      155.5    };
  double weight[N] = {  63.3,       61.1,       64.4,       62.2,       65.5    };

  // 身長（height）昇順の順位表を作る
  int index[N];
  iota(begin(index), end(index), 0);
  sort(begin(index), end(index),
       [&](int a, int b) { return height[a] < height[b]; }); 

  for ( int i = 0; i < N; ++i) {
    cout << name[index[i]] << " "
         << height[index[i]] << "[cm] "
         << weight[index[i]] << "[kg]\n";
  } 
}

fig-04

　順位表に基づいて要素列を入れ替える関数gatherを作ってみました：

list-12

template<typename RandomAccessIterator, typename ForwardIterator>
ForwardIterator gather(RandomAccessIterator first, RandomAccessIterator last, ForwardIterator iofirst) {
  ForwardIterator iolast = iofirst;
  std::advance(iolast, std::distance(first, last));
  std::vector<std::iterator_traits<ForwardIterator>::value_type> tmp(iofirst, iolast);
  return std::transform(first, last, iofirst, [&](auto n) { return tmp[n];});
}

　順位表indexのソートが完了したら、

list-13

  gather(begin(index), end(index), begin(name)  );
  gather(begin(index), end(index), begin(height));
  gather(begin(index), end(index), begin(weight));

することで名前／身長／体重が連動して身長の昇順にソートされます。

　サンプルコードには、Microsoft製並列パターンライブラリPPL（Parallel Patterns Library）を用いてマルチスレッド実装したコードをオマケに入れておきました。4-coreでほぼ2倍速くなりました。

　なんだか今回は（も?）lambda式が大活躍しました。C++にSTLが導入されて僕のコード・スタイルが大きく変わったのですが、lambda式はコードの表現力をさらに拡げてくれました。先日C++17の機能リストが確定したそうです。C++の次の進化が楽しみです。