std::tupleとstd::tieを使って複数の配列を一緒にソートする(配列の構造体 SoA のソート)
互いに関連付けられた複数の配列を一緒にソートしたい場合があります.
// 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とかを使ってきっちり評価したいとは思いますが.
- 作者: επιστημη,高橋晶
- 出版社/メーカー: SBクリエイティブ
- 発売日: 2014/04/17
- メディア: 単行本
- この商品を含むブログ (6件) を見る