Giter VIP home page Giter VIP logo

cpp-overdose-lib's Introduction

CircleCI

cpp-overdose-lib

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

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

C++の言語の特徴として、その手続き的な側面が多く強調されます
これはC言語を背景としているからなのですが、近年のC++の言語仕様の拡張によって面白いことができるようになってきました

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

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を作成したので、ご紹介させてください

Requirement

  • clang++( 5.0>= )
  • gnumake

要求するコンパイラのバージョンが高いので、ArchLinuxなど最新のソフトウェアが積極的に導入されるものが望ましいです

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

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

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

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

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

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

  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のサービスと組み合わせて定常分析に用いるなどが考えられるかもしれません

cpp-overdose-lib's People

Contributors

gink03 avatar

Stargazers

 avatar  avatar  avatar  avatar

Watchers

 avatar  avatar

Recommend Projects

  • React photo React

    A declarative, efficient, and flexible JavaScript library for building user interfaces.

  • Vue.js photo Vue.js

    🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.

  • Typescript photo Typescript

    TypeScript is a superset of JavaScript that compiles to clean JavaScript output.

  • TensorFlow photo TensorFlow

    An Open Source Machine Learning Framework for Everyone

  • Django photo Django

    The Web framework for perfectionists with deadlines.

  • D3 photo D3

    Bring data to life with SVG, Canvas and HTML. 📊📈🎉

Recommend Topics

  • javascript

    JavaScript (JS) is a lightweight interpreted programming language with first-class functions.

  • web

    Some thing interesting about web. New door for the world.

  • server

    A server is a program made to process requests and deliver data to clients.

  • Machine learning

    Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.

  • Game

    Some thing interesting about game, make everyone happy.

Recommend Org

  • Facebook photo Facebook

    We are working to build community through open source technology. NB: members must have two-factor auth.

  • Microsoft photo Microsoft

    Open source projects and samples from Microsoft.

  • Google photo Google

    Google ❤️ Open Source for everyone.

  • D3 photo D3

    Data-Driven Documents codes.