タグ

ブックマーク / www.kmonos.net (3)

  • d.y.d. 2倍だけじゃない

    10:01 10/07/20 それでも2倍だ 先日のvectorの伸長度合いの記事に関して 当に1.5倍のほうがメモリ効率がよいのか という反応をいただきました。とても興味深い。みんな読みましょう。 自分の理解メモ: 「再利用ができるから嬉しい」等の議論をするなら、 今までに確保したメモリ (1 + r^1 + ... + r^k) のうち、 有効に使えてるメモリ r^{k-1} (バッファ拡大直後) や r^k (次のバッファ拡大直前) の割合で評価してみようじゃないかという。 まず簡単のために再利用をしない場合を考えると、この割合はそれぞれ (r-1)/r^2、 (r-1)/r になります(途中計算略)。 この利用率が最悪になる瞬間 (r-1)/r^2 を最善にしよう、 という一つの指標で考えてみると、式を微分なりなんなりしてみると r = 2 で最大(25%)となることがわかります

  • 20分でわかるPurely Functional Data Structures (PDF)

    20分でわかる Purely Functional Data Structures k.inaba (http://www.kmonos.net/) Apr. 4, 2010 あらすじ イ ミ ュ ー タ ブ ル デ ー タ 構 造 は 遅 い Immutable Object だけで作るデータ構造 このの 内 容を 全速力で 布教する お題:キュー (Queue) • FIFO (First-In First-Out) • pushBack(e) でデータeを入れる • popFront() で取り出せる • 入れた順に出てくる • 以上 破壊的キュー Immutable Object でない 打倒すべき目標 代 入 手続き型でよくある interface Queue<E> { void pushBack(E e); E popFront(); } よくある実装 1 2 3 ・ 4 ・

  • letsboost::scope_exit

    sample サンプルの動作確認バージョン [GCC4.4/1.41.0] [VC9/1.41.0] #include <iostream> #include <vector> #include <numeric> #include <boost/foreach.hpp> #include <boost/scope_exit.hpp> using namespace std; void f( vector<int>& v1, vector<int>& v2 ) { // v1 に 値を push v1.push_back(v1.size()); // f を抜けるときに戻す BOOST_SCOPE_EXIT( (&v1) ) { v1.pop_back(); } BOOST_SCOPE_EXIT_END // v2 に 値を push v2.push_back(v2.size()); //

  • 1