多段階選抜 (C++20) (MSVC only)

C++20(TS) generator document is below.

多段階選抜
解答日
シリーズ:yieldの練習/ジェネレータを入れ子に/整数平方根・立方根の実装

問題
 

http://nabetani.sakura.ne.jp/hena/ord24eliseq/
https://qiita.com/Nabetani/items/1c83005a854d2c6cbb69

Ruby
2014/8/2(当日)
https://qiita.com/cielavenir/items/9f15e29b73ecf98968a5

C#/Python
2014/8/4
https://qiita.com/cielavenir/items/a1156e6a4f71ddbe5dcb

 
ここから上はdrop_prev_square/drop_prev_cubicをまとめる前の答案

Go/C#/Ruby/Python
2014/8/5
https://qiita.com/cielavenir/items/2a685d3080862f2c2c47

PHP/JavaScript
2014/9/9
https://qiita.com/cielavenir/items/28d613ac3823afbf8407

VB
2014/9/10
https://qiita.com/cielavenir/items/cb7266abd30eadd71c04

D
2015/12/21
https://qiita.com/cielavenir/items/47c9e50ee60bef2847ec

Perl
2017/3/10
https://qiita.com/cielavenir/items/6dfbff749d833c0fd423

Lua
2017/3/13
https://qiita.com/cielavenir/items/c60fe7e8da73487ba062

C++20(TS)
2017/3/15

https://qiita.com/cielavenir/items/e1129ca185008f49cbab (MSVC)
https://qiita.com/cielavenir/items/1cfa90d73d11bb7dc3d4 (clang)

F#
2017/3/17
https://qiita.com/cielavenir/items/a698d6a26824ff53de81

Boo/Nemerle
2017/5/13
https://qiita.com/cielavenir/items/e2a783f0fe4b0fe0ed48

Perl6
2017/5/15
https://qiita.com/cielavenir/items/656ea17fa96c865c4498

Kotlin
2017/5/25
https://qiita.com/cielavenir/items/9c46ce8d9d12e51de285

Crystal
2018/5/8
https://qiita.com/cielavenir/items/1815bfa6a860fd1f90db

MoonScript
2018/6/16
https://qiita.com/cielavenir/items/8b03cce0386f4537b5ad

Julia/Rust
2018/12/20
https://qiita.com/cielavenir/items/3ddf72b06d625da0c4a5

Nim
2018/12/26
https://qiita.com/cielavenir/items/5728944867e609fd52a7

Tcl
2018/12/31
https://qiita.com/cielavenir/items/76cbd9c2022b48c9a2c9

Pascal/Cobra
2019/1/16
https://qiita.com/cielavenir/items/81b81baf8dfc1f877903

Icon
2019/1/17
https://qiita.com/cielavenir/items/889622dcc721f5a4da24

(icbrtの実装に関する)補題
2017/5/11
整数除算であってもn/(x*y)はn/x/yに等しい(ことの証明)
https://qiita.com/cielavenir/items/21a6711afd6be8c18c55


  • 真打登場。

  • ただしVisual C++ 2017でしか動きません。 Works with only Visual C++ 2017.


tyama_hena24_enum.cpp

// http://qiita.com/Nabetani/items/1c83005a854d2c6cbb69

// http://nabetani.sakura.ne.jp/hena/ord24eliseq/

#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <functional>
#include <numeric>
#include <experimental/generator>
#include <cstdio>
#include <cmath>
using namespace std;
using namespace std::experimental;

generator<int> generate(){
int i=1;
for(;;){
co_yield i;
i+=1;
}
}
generator<int> drop_prev(bool(*check)(int),generator<int> _prev){
auto prev=_prev.begin();
int a=*prev;
++prev;
int b=*prev;
for(;;){
if(!check(b))co_yield a;
a=b;
++prev;
b=*prev;
}
}
generator<int> drop_next(bool(*check)(int),generator<int> _prev){
auto prev=_prev.begin();
int a=*prev;
++prev;
int b=*prev;
co_yield a;
for(;;){
if(!check(a))co_yield b;
a=b;
++prev;
b=*prev;
}
}
generator<int> drop_n(bool(*check)(int,int),int n,generator<int> _prev){
auto prev=_prev.begin();
int i=0;
for(;;){
i++;
int a=*prev;
if(!check(i,n))co_yield a;
++prev;
}
}
bool is_sq(int n){
int x=(int)sqrt(n);
return x*x==n;
}
bool is_cb(int n){
int x=(int)cbrt(n);
return x*x*x==n;
}
bool is_multiple(int i,int n){return i%n==0;}
bool is_le(int i,int n){return i<=n;}

int main(){
map<char,function<generator<int>(generator<int>)>> f={
{'S',[&](auto e){return drop_next(&is_sq,move(e));}},
{'s',[&](auto e){return drop_prev(&is_sq,move(e));}},
{'C',[&](auto e){return drop_next(&is_cb,move(e));}},
{'c',[&](auto e){return drop_prev(&is_cb,move(e));}},
{'h',[&](auto e){return drop_n(&is_le,100,move(e));}},
};
vector<int>v(8);
iota(v.begin(),v.end(),2);
for(auto &e:v)f[(char)('0'+e)] = [&](int &j){
return [&](auto e){return drop_n(&is_multiple,j,move(e));};
}(e);

string line;
for(;getline(cin,line);){
bool first=true;
//cS => f['S'](f['c'](generate()))
//auto z=reduce!((s,e)=>f[e](s))(generate(),line);

auto z=generate();
for(char e:line)z=f[e](move(z));
auto it=z.begin();
for(int i=0;i<10;i++){
int n=*it;
++it;
if(!first)putchar(',');
first=false;
printf("%d",n);
}
puts("");
fflush(stdout);
}
}



170314追記

最初に書いた答案は間違いだらけだった…

diffは以下の通り。

diff --git a/hena/tyama_hena24_enum.cpp b/hena/tyama_hena24_enum.cpp

index f14a604..1d9dc83 100644
--- a/hena/tyama_hena24_enum.cpp
+++ b/hena/tyama_hena24_enum.cpp
@@ -3,8 +3,10 @@

#include <iostream>
#include <string>
+#include <vector>
#include <map>
#include <functional>
+#include <numeric>
#include <experimental/generator>
#include <cstdio>
#include <cmath>
@@ -18,7 +20,7 @@ generator<int> generate(){
i+=1;
}
}
-generator<int> drop_prev(const function<bool(int)> &check,const generator<int> &_prev){
+generator<int> drop_prev(bool(*check)(int),generator<int> _prev){
auto prev=_prev.begin();
int a=*prev;
++prev;
@@ -30,7 +32,7 @@ generator<int> drop_prev(const function<bool(int)> &check,const generator<int> &
b=*prev;
}
}
-generator<int> drop_next(const function<bool(int)> &check,const generator<int> &_prev){
+generator<int> drop_next(bool(*check)(int),generator<int> _prev){
auto prev=_prev.begin();
int a=*prev;
++prev;
@@ -43,7 +45,7 @@ generator<int> drop_next(const function<bool(int)> &check,const generator<int> &
b=*prev;
}
}
-generator<int> drop_n(const function<bool(int,int)> &check,int n,const generator<int> &_prev){
+generator<int> drop_n(bool(*check)(int,int),int n,generator<int> _prev){
auto prev=_prev.begin();
int i=0;
for(;;){
@@ -65,16 +67,19 @@ bool is_multiple(int i,int n){return i%n==0;}
bool is_le(int i,int n){return i<=n;}

int main(){
- map<char,function<generator<int>(const generator<int>&)>> f={
- {'S',[&](auto &e){return drop_next(&is_sq,e);}},
bool is_le(int i,int n){return i<=n;}

int main(){
- map<char,function<generator<int>(const generator<int>&)>> f={
- {'S',[&](auto &e){return drop_next(&is_sq,e);}},
- {'s',[&](auto &e){return drop_prev(&is_sq,e);}},
- {'C',[&](auto &e){return drop_next(&is_cb,e);}},
- {'c',[&](auto &e){return drop_prev(&is_cb,e);}},
- {'h',[&](auto &e){return drop_n(&is_le,100,e);}},
+ map<char,function<generator<int>(generator<int>)>> f={
+ {'S',[&](auto e){return drop_next(&is_sq,move(e));}},
+ {'s',[&](auto e){return drop_prev(&is_sq,move(e));}},
+ {'C',[&](auto e){return drop_next(&is_cb,move(e));}},
+ {'c',[&](auto e){return drop_prev(&is_cb,move(e));}},
+ {'h',[&](auto e){return drop_n(&is_le,100,move(e));}},
};
- for(int i=2;i<10;i++){
- f[(char)('0'+i)] = [&](auto &e){return drop_n(&is_multiple,i,e);};
- }
+ vector<int>v(8);
+ iota(v.begin(),v.end(),2);
+ for(auto &e:v)f[(char)('0'+e)] = [&](int &j){
+ return [&](auto e){return drop_n(&is_multiple,j,move(e));};
+ }(e);
+
string line;
for(;getline(cin,line);){
bool first=true;
@@ -82,7 +87,7 @@ int main(){
//auto z=reduce!((s,e)=>f[e](s))(generate(),line);

auto z=generate();
- for(char e:line)z=f[e](z);
+ for(char e:line)z=f[e](move(z));
auto it=z.begin();
for(int i=0;i<10;i++){
int n=*it;


チェック関数の渡し方


  • C++11ではfunction<ret(param)>という覚えやすい書き方ができるようになった。これのconst&を渡すことが主流であろう。

  • しかし、この書き方だとfunctionオブジェクトが生成されてしまい、この参照は(おそらくf[]()を抜けた段階で)破棄されてしまう。

  • よって、 存在するオブジェクトの値渡し でなければならない。関数を渡す場合は必然的に関数ポインタを使うことになる。

  • 2..9においても、この数値をメモリ上に残して置かなければならない。

  • cf: http://stackoverflow.com/questions/37634643/why-does-my-program-have-variable-lifetime-issues-when-using-generators


generatorの渡し方

通常、引数の渡し方は3通りある。



  1. const generator<int> &_prev


    • その場で生成したオブジェクトをコピーを避けかつ変数に入れずに渡したいときに使用する方法である。

    • generator#begin()はgeneratorオブジェクトを変更するため、今回は不可である。




  2. generator<int> &_prev


    • コピーを避け、かつオブジェクトを変更する必要があるときに使用する方法である。

    • generatorオブジェクトが変更される点は満たすが、上記の変数の寿命の兼ね合いで正常に動かない。




  3. generator<int> _prev


    • 毎回コピーを行う方法である。

    • 今回、これだけが正しく動作する。なお、コピーのコストはかなり小さいようである。



そして、generatorクラスはコピーコンストラクタが削除されているため、ムーブセマンティクスを用いて渡す必要がある。

ドキュメントも少ない現状、常用は難しい印象でした。

以下SEO対策



Passing check function


Passing generator

Usually there are 3 ways to pass generators.



  1. const generator<int> &_prev


    • We use this if we want to use immediate objects without variables and to avoid copying them.

    • Since generator#begin() modifies the generator object, we cannot use method.




  2. generator<int> &_prev


    • We use this if we want to avoid copying objects and to modify them in the function.

    • This method satisfies that generator objects are modified, but the variables lifetime (written above) matters and the program will crash.




  3. generator<int> _prev


    • This method copies the objects every time.

    • In our cases, only this method works. Actually the copying cost looks small.



Finally the generator class's copy constructor is deleted. So we have to use the move semantics.

Since we have few documents, common use looks difficult now.


170513

整数平方根・立方根コードです


isqrt_icbrt.cpp

int isqrt(int n){

if(n<=0)return 0;
if(n<4)return 1;
int x=0,y=n;
for(;x!=y&&x+1!=y;)x=y,y=(n/y+y)/2;
return x;
}
int icbrt(int n){
if(n<0)return icbrt(-n);
if(n==0)return 0;
if(n<8)return 1;
int x=0,y=n;
for(;x!=y&&x+1!=y;)x=y,y=(n/y/y+y*2)/3;
return x;
}


181024

clangでもコンパイルできる完全版を https://qiita.com/cielavenir/items/1cfa90d73d11bb7dc3d4 に置きました