今日ほとんど使わない機能のテストをしていてずっとバグに悩まされていました。結局、こんな感じのバグでした。 for(int i = 0; i < 5; ++i) b[d] = a[i]; わかりますか？添え字が間違ってますよね。こんなのが10年くらい放置されていたみたいです。こういう…

よく知られた方法に行列の片方を転置して掛け合わせるという方法があります。 通常のように AikBkj としてkで回すと、Bのほうは飛び飛びのアドレスを見ることになり、キャッシュのヒットミスが起こりやすくなります。わざわざ転置してから、 AikBjk とすると…

回文数とは前から読んでも後ろから読んでも同じ自然数、例えば13231などのことで、なぜかよくProject Eulerで出てきます。 回文数は再帰的に生成することができます。例えば、131という回文数があれば、これを10倍して10001の倍数を足すことで、11311,21312,…

今まで作ったcIterable関係をここにまとめておきます。予告なく修正されることがあります。

vectorを逆順に出します。 template<typename T> class cReversed : public cIterable<T> { const vector<T> v; typename vector<T>::const_reverse_iterator p; bool first; public: cReversed(const vector<T>& w) : v(w), first(true) { } bool exists_next() { if(first) { first</t></t></t></t></typename>…

逆にvectorをiterableに変換します。 template<typename T> class cIter : public cIterable<T> { const vector<T> v; typename vector<T>::const_iterator current; bool first; public: cIter(const vector<T>& w) : v(w), first(true) { } bool exists_next() { if(first) { curre</t></t></t></t></typename>…

iterableをvectorに変換します。 template<typename T> vector<T> list(shared_ptr<cIterable<T>> g) { vector<T> v; while(g->exists_next()) v.push_back(g->value()); return v; } int main() { vector<int> v = list(range(3)); cout << v[0] << v[1] << v[2] << endl; } 012</int></t></citerable<t></t></typename>

Pythonではジェネレータでこういうことができます。 def gen(): for n in range(3): for m in range(n + 1, 4): yield (n, m) (0, 1) (0, 2) (0, 3) (1, 2) (1, 3) (2, 3)直積ではなく、mを出すiterableがnに依存しています。これを実現するにはどうすればよ…

2つのiterableの直積です。タプルを返します。 template<typename T, typename U> class cProduct : public cIterable<tuple<T,U>> { shared_ptr<cIterable<T>> gen1; shared_ptr<cIterable<U>> gen2; vector<U> v; typename vector<U>::const_iterator p; int mode; public: cProduct(shared_ptr<cIterable<T>> g1, shared_ptr<cIterable<U>…</citerable<u></citerable<t></u></u></citerable<u></citerable<t></tuple<t,u></typename>

iterate(x, f)でx, f(x), f(f(x)), ...と出します。unfoldでも実現可能だけど、めんどうなので。 template<typename T, typename U> class cIterate : public cIterable<T> { T current; U func; bool first; public: cIterate(T x, U f) : current(x), func(f), first(true) { } bool e</t></typename>…

allはすべてがtrueならtrueを、そうでなければfalseを返します。 anyはどれか一つがtrueならtrueを、そうでなければtrueを返します。 bool all(shared_ptr<cIterable<bool>> g) { while(g->exists_next()) { if(!g->value()) return false; } return true; } bool any(shared</citerable<bool>…

cIterableをつなげます。 template<typename T> class cChain : public cIterable<T> { shared_ptr<cIterable<T>> gen1; shared_ptr<cIterable<T>> gen2; bool first; public: cChain(shared_ptr<cIterable<T>> g1, shared_ptr<cIterable<T>> g2) : gen1(g1), gen2(g2), first(true) { } bool exists_next() { if(first) { if(!ge</citerable<t></citerable<t></citerable<t></citerable<t></t></typename>…

元ネタ http://python-history-jp.blogspot.com/2010/09/pythonc.html Pythonのこの挙動、知らなかった。 print -1 / 3 # -1 print -1 % 3 # 2 C++なら、 std::cout << -1 / 3 << std::endl; // 0 std::cout << -1 % 3 << std::endl; // -1 何度この挙動に悩…

繰り返し値を出します。 template<typename T> class cCycle : public cIterable<T> { shared_ptr<cIterable<T>> gen; vector<T> v; typename vector<T>::const_iterator p; bool first; public: cCycle(shared_ptr<cIterable<T>> g) : gen(g), first(true) { } bool exists_next() { if(first) { if(gen->ex</citerable<t></t></t></citerable<t></t></typename>…

zipを使うと簡単にスライシングのコードが書けます。 template<typename T> class cSlice : public cIterable<T> { shared_ptr<cIterable<tuple<int,T>>> gen; int current; int end; int delta; bool last; shared_ptr<cIterable<int>> counter; public: cSlice(shared_ptr<cIterable<T>> g, int n) : current(0), end(n), delt</citerable<t></citerable<int></citerable<tuple<int,t></t></typename>…

2つのIterableが並行に（tupleにして）値を出せるようにします。長さが違う場合は短いほうにあわせます。 #include <tuple> #include "itertools.h" using namespace std; using namespace itertools; template<typename T, typename U> class cZip : public cIterable<tuple<T,U>> { shared_ptr<cIterable<T>> gen1;</citerable<t></tuple<t,u></typename></tuple>…

takewhileと似ていますが、実のところあまり使いません。 叙述関数がtrueの間は値を出しません。 template<typename T, typename U> class cDropWhile : public cIterable<T> { U pred; std::shared_ptr<cIterable<T>> gen; bool first; public: cDropWhile(U p, std::shared_ptr<cIterable<T>> g) : pred(p), gen(</citerable<t></citerable<t></t></typename>…

#include <iostream> #include <memory> class C { int n; public: C(int m) : n(m) { } ~C() { std::cerr << "C:~C" << std::endl; } int get() const { return n; } }; int main() { auto p = std::unique_ptr<C>(new C(1)); auto q = std::move(p); auto r = std::unique_ptr<C>(n</c></c></memory></iostream>…

unique_ptrの使い方を勉強してみました。 #include <iostream> #include <memory> class C { int n; public: C(int m) : n(m) { } ~C() { std::cerr << "C:~C" << std::endl; } int get() const { return n; } }; int main() { auto p = std::unique_ptr<C>(new C(1)); std::cout <</c></memory></iostream>…

ちょっと工夫してあまりコピーが発生しないように書き直しました。 template<typename T> class cPermutations : public cIterable<vector<T>> { typedef typename vector<T>::iterator IT; template<typename T> class cPerm { typedef shared_ptr<cPerm<T>> PTR; IT begin; IT end; PTR g; const int n; i</cperm<t></typename></t></vector<t></typename>…

順列を次々に出します。 例えば、[ 1, 2, 3 ]というリストがあったとして2要素の順列を出すと、 [ [ 1, 2 ], [ 1, 3 ], [ 2, 1 ], [ 2, 3 ], [ 3, 1 ], [ 3, 2 ] ]となります。このpermutationsはPythonでは簡単に書けます（本当はライブラリにあるのでこれ…

前回のunfoldは無限列しか出しません。それをtakewhile止めています。しかし、例えば整数を10進数に分解することを考えます。10で割った余りを出していくと、 shared_ptr<cIterable<int>> digits(int n) { auto f = [] (int n) { return pair<int,int>(n % 10, n / 10); }; return un</int,int></citerable<int>…

Haskellなどにあるunfoldは、reduceの逆で初期値からリストを作っていきます。 f(状態0) → (値1, 状態1) → 値1 f(状態1) → (値2, 状態2) → 値2 という具合に値を出していきます。 reduceの逆なのにunfoldなのはあまり気にしない方向で。 template<typename T, typename U, typename V> class cUnf</typename>…

フィボナッチ数列を適当に作ります。 class cFib : public cIterable<int> { int a; int b; public: cFib() : a(1), b(1) { } bool exists_next() { int tmp = b; b += a; a = tmp; return true; } int value() const { return a; } }; shared_ptr<cIterable<int>> fib() { retur</citerable<int></int>…

Pythonのcountは指定した数から順に整数を出していきます。ここでは、引数で公差も指定できるようにしました。 class cCount : public cIterable<int> { int current; int delta; public: cCount(int s, int d) : current(s - d), delta(d) { } bool exists_next(</int>…

takewhileは、叙述関数がtrueである限り値があれば出し続けます。 template<typename T, typename U> class cTakeWhile : public cIterable<T> { U pred; shared_ptr<cIterable<T>> gen; public: cTakeWhile(U p, shared_ptr<cIterable<T>> g) : pred(p), gen(g) { } bool exists_next() { return gen->exists_next</citerable<t></citerable<t></t></typename>…

失敗した話。 #include <string> int main() { try { throw(""); } catch(std::string e) { ; } } こんなコードで例外を捕えられませんでした。実際にはこれほど単純なコードではなかったのですが。無意識のうちにこういうコードから連想していたようです。 #include <string></string></string>…

リストに対して写像を施して別のリストを作ります。 template<typename T, typename U, typename V> class cMap : public cIterable<T> { U func; shared_ptr<cIterable<V>> gen; public: cMap(U f, shared_ptr<cIterable<V>> g) : func(f), gen(g) { } bool exists_next() { return gen->exists_next(); } T value() const { r</citerable<v></citerable<v></t></typename>…

sumを作りたいのですが、その前にPythonでreduceと言ったり、Haskellでfoldと言ったりするものを作ります。リストなどに関数を次々に適用してスカラー値にするものです。(1, 2, 3)にf(x, y) = 10x + yを適用していくと、初期値を0として、 10 * 0 + 1 -> 1 1…

Pythonのifilterを作ります。叙述関数を適用してtrueになる要素だけ出します。 以下は、3の倍数だけ出力するコードです。 template<typename T, typename U> class cFilter : public cIterable<T> { U pred; shared_ptr<cIterable<T>> gen; public: cFilter(U p, shared_ptr<cIterable<T>> g) : pred(p), gen(g) { </citerable<t></citerable<t></t></typename>…