本当は怖いHPC

HPC屋の趣味＆実益ブログ

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版

2016/07/16 時点 Intel Xeon Phi の新製品Knights Landingについてのリンク集

hpc

自分用のリンク集です．

Knights Landingの出荷が始まっているようです．前世代のKnights Cornerで問題となったリングバスは取り除かれ，メッシュネットワークで置き換えられているようなので，性能評価が出てくるのが楽しみです

Intelのオフィシャルページ．スペック等

Intel® Xeon Phi™ Product Family

Intel Xeon Phi Processor High Performance Programming, Second Edition: Knights Landing Edition（オフィシャル解説本）

後藤弘茂さんによる安定の解説

後藤さんの記事は，きちんと基礎知識がないと理解すらおぼつきません．

Intelは機械学習で覇権を握れるか? ～GPGPUに対するXeon Phiの優位点を語る - PC Watch

【後藤弘茂のWeekly海外ニュース】Intelのサーバー戦略の要となるXeon PhiとFPGA - PC Watch 2016/7/6

【後藤弘茂のWeekly海外ニュース】ホモジニアスな構成が可能な新生Xeon Phi「Knights Landing」の強味 - PC Watch 2016/7/5

【後藤弘茂のWeekly海外ニュース】Intelがスパコンカンファレンスで「Knights Landing」を正式発表 - PC Watch 2016/6/22 @ ISC

信頼と実績のHPC Wire

Intel Launches 'Knights Landing' Phi Family for HPC, Machine Learning 2016/6/21 @ISC

What Knights Landing Is Not 2016/6/18

Intel Debuts 'Knights Landing' Ninja Developer Platform 2016/4/12

A Conversation with James Reinders 2016/1/21

The Next Platform

Intel Knights Landing Yields Big Bang For The Buck Jump 2016/6/20

マイナビ

米Intel、"Knights Landing"こと最大72コアの次世代「Xeon Phi」 | マイナビニュース 2016/6/22

その他

Intel talks concurrency and Knights Landing • The Register 2015/12/16

「三菱ＵＦＪ銀、独自の仮想通貨を開発中」というニュースについて

blockchain bitcoin

www.asahi.com

三菱東京UFJ銀行が，「仮想通貨」を発行するというニュースが出ていました． この件に関しては，現時点では新聞報道があるのみで，三菱東京UFJ銀行から公式の発表はありません．ちょっと感想を書きたいと思います．

「仮想通貨」としてのMUFGコイン

まず最初に述べておくと，個人的には，今回のMUFJコインが「仮想通貨であるかどうか」という定義の問題にはあまり興味がありません．

利用者から見ると，いわゆる「ポイント」とあまり変わらないように見えます．楽天ポイントやSUICAのようなシステムに個人送金や海外での出金の機能を追加し，それをブロックチェーンを用いて実装することでコストを抑えてシステム構築を行うという趣旨のようです（ただし，一次ソースの朝日新聞の記事では「ブロックチェーン」を用いるかどうかについては言及がありません．）

個々の利用者の手元で「採掘」が行われるわけではないでしょう．コインの発行権はあくまで三菱東京UFJ銀行が握っているのですから，ハッシュ値の計算は同銀行の分散した計算サーバーが行うということになるでしょう．

個人間の送金

個人間の送金については，利用者目線から見ると多少の旨味があるという程度でしょう．三菱東京UFJ銀行の振込手数料について言えば，現時点で同一支店同士なら無料・同銀行の他店口座同士なら108円ですから，この108円が無料になることに相当すると考えられます．

期待が持てるのは，送金機能を第三者のアプリが実装できるかどうかという点です．これは仮想通貨と言うよりアプリの技術的仕組みの問題ではありますが，これが安全にできるのであれば利便性は一気に高まり画期的といえます．銀行系のAPIはマネーフォワードなどの一部業者に開示されているだけで，公開されているAPIというものはありません．

ただ，個人間の「送金」が容易に行えるというというのが現行法の範囲内で可能なのかどうかはよくわかりません．それは，既存のポイントシステムがあえて踏み込まなかった領域にどんどん踏み込むことになるからであり，法的にグレーな部分だからです．現金ではなく「ポイント」相当のものとはいえ，「1円＝1コイン」の比率と換金性を保証しているMUFGコインの交換が自由に行えるとすれば，パチンコの換金システムと同じような気持ち悪さを感じることも確かです．

手数料と海外出金

あとは変換の手数料がどの程度になるかですが，まあこれは合理的な程度に安ければ問題は無いでしょう．ただ，ビットコインのように，国際送金や現地通貨引き出しが画期的に安いということにはならないと思います．

以前にも指摘しましたが，現在のビットコインのトランザクションが格安で行えるのは，各国で「通貨」の扱いを受けていないことによって法規制がゆるく，安全性が完全には保証されていないことによってコストが削減され，その分のリスクを利用者が引き受けていることによると思います．必ずしても仮想通貨だから安い，ブロックチェーンだから安い，ということではありません．確かにMUFG内でのサーバー代は節約できると思いますが，海外での現地通貨引きだしがMUFG内で完結しているわけではないはずなので，MUFG内部でのコスト削減分だけが安くなるということでしょう．手数料全体に占める割合はそれほど多くないと想像します．

確かに銀行間のトランザクションにおいてもブロックチェーン技術を使えばシステムコストは安くなるでしょうが，現状のブロックチェーンをそのまま使うだけでは現在／将来の送金トランザクションを，満足できるレイテンシ・スループットで処理することはできないと思われます．ですから（言い方は悪いが）現状では「安かろう悪かろう」の状態であって，技術的には発展途上であるというのが冷静な見方だと思います．もちろん将来的にはDisruptive Technologyであるとは思うわけですが．

MUFGコインの話に戻ると，もし海外での現地通貨換金の手数料が劇的に安くなるのであれば，それは同銀行の持ち出しになるか，円→MUFGコインの変換手数料に転嫁されるというだけな気がしますが…

銀行の内部技術としてのブロックチェーン

「ビットコイン＆ブロックチェーン研究所」のブログでも言及されているように，どちらかと言えば銀行の内部システムの実装手法としてのブロックチェーン技術の利用の方が話しのメインなのではないかと邪推しますね．朝日新聞の記者が，一連の取材の中で一般消費者にわかりやすい（あるいはその記者自身にとってわかりやすかった）コインの話を「仮想通貨」というセンセーショナル（？）なタイトルで記事にした，という方が事実に近い気がします．なんとなく．

【広告】