読者です 読者をやめる 読者になる 読者になる

本当は怖い情報科学

情報系大学院生の趣味&実益ブログ。

std::tupleとstd::tieを使って複数の配列を一緒にソートする(配列の構造体 SoA のソート)

c++

互いに関連付けられた複数の配列を一緒にソートしたい場合があります.

// SoAの例
std::vector<int> student_ids;
std::vector<std::string> names;
std::vector<int> math_scores;

// AoSの例
struct Student {
  int id;
  std::string name;
  int math_score
};

専門的には,SoA(Structure of Array:配列の構造体)と呼びます(かならずしも構造体とはなっていなくても).一方,普通に構造体やクラスの配列になっている場合はAoS(Array of Structure:構造体の配列)と呼ばれます.

さて,このSoAのデータ構造をソートしたいと思います.上の例で言いうと,生徒番号を元に名前などのフィールドを一斉にソートしたいということです.最初からAoSを採用すれば余計な苦労はありませんが,歴史的な事情や効率の都合でSoAになっているとします.

そこで,C++11のstd::tupleを使って,SoAを内部的にAoSに変換してソートする関数を書いてみました.ポイントは,std::tieを使うとPythonの一括代入のようなことができるという点ですね.これは調べるまで知りませんでした.

template<class T, class...Args>
void TiedSort(std::vector<T> &a, std::vector<Args>&... args) {
  using tt = struct {
    T key;
    std::tuple<Args...> val;
  };
  std::vector<tt> vals(a.size());

  for (size_t i = 0; i < a.size(); i++) {
    vals[i].key = a[i];
    vals[i].val = std::make_tuple(args[i]...);
  }

  std::sort(std::begin(vals), std::end(vals), [](const tt& a, const tt& b) {
      return a.key < b.key;
    });
  
  for (size_t i = 0; i < a.size(); i++) {
    a[i] = vals[i].key;
    std::tuple<Args&...>(args[i]...) = vals[i].val;
  }
}

int main() {
  std::vector<int> student_ids = {3,2,5,1,4};
  std::vector<double> weights = {42.3, 34.6, 32.5, 51.2, 41.7};
  std::vector<double> heights = {1,1,1,1,1};
  
  TiedSort<int, double, double>(student_ids, weights, heights);
}

なお,SoAをソートする方法としては,インデックス配列を用意してそれをソートする方法(数学で言う置換:permutationを使う)方法もありますが,これだと一時領域が必要になりコピーのコストが増大するため低速でした.そのうちPAPIとかを使ってきっちり評価したいとは思いますが.

C++テンプレートテクニック 第2版

C++テンプレートテクニック 第2版

【広告】