C++ Overdose 〜高速なデータ分析を求めて〜

c++ overdose

C++17のラムダ式と、テンプレートを用いることで、Rのdplyr, Kotlin, Scalaなどに似たシンタックスで、同等の機能が動かせることを示します

もっと関数型ライクにC++を使いたい！

C++の言語の特徴として、その手続き的な側面が多く強調されます

これはC言語を背景としているからなのですが、近年のC++の言語仕様の拡張によって面白いことができるようになってきました

例えば、Rという統計言語にはデータのオペレーションが感覚的にわかりやすい、dplyrというライブラリがあります

C++がデータ分析の文脈で使われないのはなぜでしょうか。いろんな人がいろんなことを言いますが、早い話、サッと組んで、サッと動かすということができないからです

The answers already cover the main reason data scientists don't use C and that is the convenience of rapid prototype building. 1

これを解決できそうな機運が少しあり、dplyrやScala Likeなコードスタイルを用いることで、手続き型特有の大量の一時変数を隠蔽することに成功しました

これに似せたライブラリ overdose-libを作成したので、ご紹介させてください

ラムダとTemplateとautoによる型推定  

ラムダは匿名関数と呼ばれ、リテラルの中に埋め込むことができ、また変数に束縛することもできる名前のない関数です。ラムダ式は変数に束縛することも可能で、変数に代入したラムダ式を取り回して、任意の処理をすることができます

TemplateはもともとジェネリックなSTLの型を指定することができるものでしたが、型以外にも実数値やラムダ式を引数に取れるし、コンパイル時に動作するので、コンパイル時に実行し計算するものとなっています

autoは型推論で、型宣言を簡潔にするものですが、一部戻り値などをジェネリックに動作することが期待できて、戻り値の型がテンプレートやコンパイル時の型の取得のdecletypeなどで、自動的に推論させることが可能です。

これを用いると、関数型言語の一つの要件である第1級関数という関数をデータと同じように扱うことが可能になります

例えば、任意の関数Fを受け取り、型SのベクタをFで変換してから型Rで返却する関数を返す関数はこのようにかけます。

  template<typename S, typename R, typename F>
  auto mapper(const F& f) {
    return [f](std::vector<S> source) {
      std::vector<R> tmp; 
      for(auto s:source) {
        R r = f(s); 
        tmp.push_back(r);
      }
      return tmp;
    };
  };

これを>>(ダブルアロー)のオペレータを定義すると、このように書くことができます  
この例では、[1, 2, 3, 4]のベクタを各要素を二乗する操作です  
echoは標準出力に対する出力する関数を返す関数

  auto src = vector{1, 2, 3, 4};
  src >> mapper<int,int>([](int i ){ return i*i;}) >> echo<int>();

出力はこのようになります

$ ./bin/a.out
[1,4,9,16]

色々な関数を実装してみた

RのdplyrやPythonのpandas、Apache SparkのRDDなどを参考にして実装しました
dplyrとSpark RDDと今回作成したoverdose(仮称)の関数と機能の比較表です

機能	dplyr(R)	Spark RDD(Scala,Java)	overdose(C++)
パイプライン操作	%>%	.(dot)	>>(ダブルアロー)
任意の関数で処理	map	map	mapper
畳み込み処理	reduce	reduce	reduce
フィルタ操作	filter	filter	filter
グルーピング	group_by	group_by	groupBy
並び替え	arrange	sortBy	sortBy
二つのデータのペアリング	-	zip	zipMap
合計値を計算	accumulate	sum	sum
最小値を計算	-	min	min
最大値を計算	-	max	max
平均値を計算	-	mean	mean
要素を取り出す	flatten	flatten	flatten
ユニークにする	distinct	distinct	distinct
要素を追加する	mutate	(mapで代替)	(mapperで代替)
index付きmap	-	withIndex	mapperIndexed
シリアライザ	-	toString()	SERIAL,DESERIAL
並列性	multidplyr	並列性がある	concurrent::mapper

minimal install

ご注意!!

完全にclang++以外の存在を忘れていましが、このプログラムはclang 5.0.0(final)で開発と動作確認しています

$ clang++ --version
clang version 5.0.0 (tags/RELEASE_500/final)

C++で作られているので、/usr/includeにインクルードファイルを設置し、/usr/lib(64)にsoをおけば、システム全体から利用できるようになりますが、
とりま、example.cppを編集することで任意の機能を成り立たせることができます。

ダウンロードはこちらから行えます

$ git clone https://github.com/GINK03/cpp-overdose-lib
$ cd cpp-overdose-lib/
$ make 
$ make test <- errorが出なければOK
$ sudo make install <- システム全体に反映する際にはやる（任意）

サンプルの実行
example.cppというFizzBuzzの10000までの数のFizz, Buzz, FizzBuzz, Otherをカウントします

コンパイルと実行にするにはこうします

$ make 
$ ./a.out
KEY: Buzz VALUE_SIZE: 1333 
KEY: Fizz VALUE_SIZE: 2667
KEY: FizzBuzz VALUE_SIZE: 666 
KEY: Other VALUE_SIZE: 5333   

mapper

一般的なScala, Ruby, Kotlinなどのmap処理に該当します。vectorの要素の中身に、ラムダ式でデータを操作することで、任意の形に変形します　　

例えば、[1, 2, 3, 4, 5, 6]のリストを全て二乗して、[1, 4, 9, 16, 25, 36]というデータを得たいとします

この時、overdoseではこのようにします

void mapperTest() {
  vector<int>({1,2,3,4,5,6})
    >> mapper<int,int>([](int i){ return i*i;}) 
    >> echo<int>();
}
(出力)-> [1,4,9,16,25,36]

インターフェース

mapper<INPUT, OUTPUT> -> std::vector<OUTPUT>

左にデータとなる構造を置き、>>(ダブルアロー)で射とするべき関数を用意します  
この時、mapperのラムダ式に入力される型情報をINPUT,戻り値の型をOUTPUTとします  
なので、型変換などにも用いることができます

reducer

Scala, Ruby, KotlinのReduceとほぼ同じ働きをします  
Reduceは何らかの畳み込みを行うのですが、掛け算と、足し算であるべき初期値が異なったりします(足し算では初期値が0.0, 掛け算などでは1.0など)  

void reducerTest() {
  vector<int>({1,2,3,4,5,6})
    >> reducer<int, int>(0, [](int& y, int x){ y = y+x;} )
    >> let<int>([](auto out){ cout << "REDUCED: " << out << endl;});
}
(出力)-> REDUCED: 21

インターフェース

reducer<INPUT,OUTPUT> -> std::vector<OUTPUT>

入力される型情報と、出力される型情報を指定します

コンパイラの解釈力に依存しますが、文脈から型情報を指定しなくても通る場合があります

filter

Scala, Ruby, Kotlinなどのfilterとおなじです  
条件に該当するデータのみを取り出します  
例えば、2の倍数になるもののみを取り出すとこのようになります  

void filterTest() {
  vector<int>({1,2,3,4,5,6,7}) 
    >> filter<int, int>([](int i){
      return i%2 == 0;
    }) >> echo<int>() ;
}
(出力)-> 
[2,4,6]

インターフェース

filter<INPUT, OUTPUT>(FUNCTOR) -> std::vector<OUTPUT>

このようなインターフェースです

groupBy

KotlinのgroupByに触発されて使いました  
KotlinのgroupByではList型に変換すると、このようなデータ構造で帰ってきます

List<Pair<KEY,List<ORIGINAL>>>

この構造が便利で特定のキーで集約したい場合によく使います。

キーの型と、出力する型を指定し、キーを作るラムダ式を指定することで、同等の機能を実現します  
この例では、1から100までのintのvectorを作成して、その値を5で割った値のあまりをキーにグルーピングをします

グルーピングした値はvector<tuple<KEY, ORIGINAL>>となります

void groupByTest() {
  vector<int> src = OD::Range(1,100);
  src >> groupBy<int, int>( [](auto i){ 
    return i%5;
  }) >> mapper<tuple<int,vector<int>>, int>( [](auto tup){
    auto [key,value] = tup;
    auto join = value >> joinToString<int>(",");
    cout << "GROUPBY TEST KEY: " << key << " VALUE: " << join << endl;//
    return 0;
  });
}
(出力)-> 
GROUPBY TEST KEY: 0 VALUE: 5,10,15,20,25,30,35,40,45,50,55,60,65,70,75,80,85,90,95
GROUPBY TEST KEY: 1 VALUE: 1,6,11,16,21,26,31,36,41,46,51,56,61,66,71,76,81,86,91,96
GROUPBY TEST KEY: 2 VALUE: 2,7,12,17,22,27,32,37,42,47,52,57,62,67,72,77,82,87,92,97
GROUPBY TEST KEY: 3 VALUE: 3,8,13,18,23,28,33,38,43,48,53,58,63,68,73,78,83,88,93,98
GROUPBY TEST KEY: 4 VALUE: 4,9,14,19,24,29,34,39,44,49,54,59,64,69,74,79,84,89,94,99

インターフェース

groupBy<KEY,ORIGINAL>(FUNCTOR) -> std::tuple<KEY,std::vector<ORIGINAL>>

このようなインターフェースになります

sortBy

色々な言語と一緒でsortで用いる評価式をラムダ式で与えることで、実現しています  

特にPythonとKotlinのsortByがいいと思っていて、評価式をラムダ式で与えるのではなく、キーとなる値を返すラムダ式を与えるとシンプルで良いと思います  

Python3で降順にソートする際は、このような表現を取ることができます  

>>> sorted([1,2,3,4,5,6,7], key=lambda x:x*-1)
[7, 6, 5, 4, 3, 2, 1]

これをC++で似たシンタックスで実現すると、このようになります  

void sortByTest() {
  vector<int> src = {1,2,3,4,5,6,7};
  src >> sortBy<int, int>([](int i){ return i*-1;}) >> echo<int>();
}
(出力)-> 
[7,6,5,4,3,2,1]

インターフェース

sortBy<KET,ORIGINAL>(FUNCTOR) -> vector<ORIGINAL>

zip

Pythonでzip関数もあるのですが、Kotlinのようなzipを定義したいと思います  

Kotlinではzipはこのようになっています

>>> listOf(1,2,3,4,5).zip(listOf("a", "b", "c", "d", "e"))
[(1, a), (2, b), (3, c), (4, d), (5, e)]

今回作成したoverdoseでは次のようになります  

void zipTest() {
  vector<int> source = {1,2,3,4,5,6,7};
  vector<string> target = {"a","b","c","d","e","f","g"};
  source >> zip<int, string>(target) >> let<vector<pair<int,string>>>([](auto ts){
    for(auto t1:ts) {
      auto [src, tgt] = t1;
      cout << "SOURCE: " << src << " TARGET: " << tgt << endl;
    }
  });
}
(出力)-> 
SOURCE: 1 TARGET: a
SOURCE: 2 TARGET: b
SOURCE: 3 TARGET: c
SOURCE: 4 TARGET: d
SOURCE: 5 TARGET: e
SOURCE: 6 TARGET: f
SOURCE: 7 TARGET: g

インターフェース

zip<SOURCE,TARGET>(std::vector<TARGET>) -> std::vector<std::pair<SOURCE,TARGET>>

sum, mean, min, max

他の言語でも色々実装されていますが、こんな感じです  

void sumMeanMaxMinTest() {
  vector<int> source = {1,2,3,4,5,6};
  auto print = [](double i) { cout << i << endl; };
  source >> sum<int>() >> let<int>(print);
  source >> mean<int>() >> let<double>(print);
  source >> max<int>() >> let<int>(print);
  source >> min<int>() >> let<int>(print);
}
(出力)-> 
21
3.66667
6
1

インターフェース  

sum<INPUT> -> INPUT
mean<INPUT> -> double
max<INPUT> -> INPUT
min<INPUT> -> INPUT

flatten

入れ子構造になったvectorを展開します  

void flattenTest() {
  vector<vector<int>> src = { {1,2},{2,3},{3,4},{4,5} };
  src >> flatten<int>() >> echo<int>();
}
(出力)-> 
[1,2,2,3,3,4,4,5]

インターフェースはこのようになっています  

flatten<INPUT>() -> std::vector<INPUT>

distinct

特定のキーで重複を消します(発見した最後の値のみが保存されます)  

void distinctTest() {
  vector<pair<string,int>> src = { {"a",1}, {"b",2}, {"b",3}, {"c",4}, {"a",5} };
  src >> distinct<string, pair<string,int>>([](auto t){
    return get<0>(t);
  }) >> mapper<pair<string,int>,int>( [](auto t){
    auto [key,val] = t;
    cout << "DISTINCT: " << key << " VALUE: " << val << endl;
    return 0;
  }) ;
}
(出力)-> 
DISTINCT: a VALUE: 5
DISTINCT: b VALUE: 3
DISTINCT: c VALUE: 4

mapperIndexed（インデックス付きマップ）

関数型におけるmapは並列性が担保されるべきで、本来はindexとかつけられないと思うのですが、一部のScalaやRubyなどの実装系においてはindexがついた状態でのmapが可能です

同様のことをc++で行うと、このように用いることができます  

void mapperIndexedTest() {
  vector<string> src = {"a", "b", "b", "c", "a"};
  src >> mapperIndexed<string, int>( [](int index, auto str) {
    cout << "Index: " << index << " Val: " << str << endl;
    return 0;
  });
}
(出力)-> 
Index: 0 Val: a
Index: 1 Val: b
Index: 2 Val: b
Index: 3 Val: c
Index: 4 Val: a

インターフェースは普通のmapと変わらないのですが、functorがindexを受け取れるようになっています  

mapperIndexed<INPUT, OUTPUT>(FUNCTOR) -> std::vector<OUTPUT>

シリアライザ, デシリアライザ

今回実装した内容は、プリミティブ型 + std::stringのみに対応したクラスや構造体のシリアライザとデシリアライザです  
C++はOSのメモリ空間を直接参照できるのでプリミティブな型(int, double)などはそのデータをそのままdumpすることができます

std::stringなどは、クラスの値なので内部でメモリを内容をどれを取るか決める必要がありますが、char*として表現できるので、char*として保存して、復旧時にstd::stringに変換します

C++というよりC言語芸なのですが、C++のtemplateとconstexprの型情報による分岐を組み合わせることで、このように、シリアライズとデシリアライズを行えます

struct Sample {
  int a;
  double b;
  std::string c;
  std::string serial() {
    return OD::SERIAL::dump(&a,this) + OD::SERIAL::SEPARATOR + OD::SERIAL::dump(&b,this) + OD::SERIAL::SEPARATOR + OD::SERIAL::dump(&c,this);
  };
};

// シリアライズとデシリアライズテスト
void testSerialDesrial() {
  auto sa1 = Sample{1, 2.0, "Hoge"};
  auto serial = sa1.serial();
  cout << "SERIAL: " << serial << endl;
  auto sa = OD::DESERIAL::recover<Sample>(serial);
  cout << "desrialized " << sa.a << " " << sa.b << " " << sa.c << " ," <<  endl;
}
(出力)-> 
SERIAL: int<Left>0<Left>01 00 00 00 <Left>4<Right>double<Left>8<Left>00 00 00 00 00 00 00 64 <Left>8<Right>std::string<Left>16<Left>Hoge<Left>32
desrialized 1 2 Hoge

並列性

マシン間をまたいでの並列性は担保していませんが、コンピュータ内部のCPUのコアぶんだけ並列でmap処理を行うことができます

これはJavaとかの並列性が担保されたmapなどと同等だと思われ、処理順序が担保されないので、データのindexなどを気にしない処理に向いています

例えば、一般的に重いと思われる素数判定を1から1,000,000まで行うとこの程度の時間が必要で、これはPythonの役10倍です

[C++でconcurrent::mapperを用いる場合]
$ time ./bin/a.out
real    3m4.833s

実験に用いたコード

void testPrimeCheck() {
  OD::Range(1, 1000000) >> concurrent::mapper<int,pair<int,bool>>( [](int i) {
    bool isPrime = true;
    for(int s=2; s <= i/2; s++) {
      if(i%s == 0) {
        isPrime = false;
        break;
      }
    }
    return make_pair(i, isPrime);
  });
}

[Python3で行う場合]
time python3 test.py  > d
real    33m21.345s 

実験に用いたコード

for i in range(2,1000000):
  isPrime = True
  for j in range(2, i//2):
    if i%j == 0:
      isPrime = False
      break

  if isPrime:
    print(i)

総括

C++で他の言語で用いられているような、いくつかの便利な関数を用意することができました

C++は、動的な言語に比べてコンパイル時に静的に型の情報が矛盾がないようにチェックされます

例えば、この方法ばバッチ的に回す分析でできるだけ、高速に処理したいなどのモチベーションに向いており、AWSのサービスと組み合わせて定常分析に用いるなどが考えられるかもしれません

最後まで読んでいただきありがとうございました。ダウンロードはこちらから行えます