タグ

algorithmとmemoryに関するkgbuのブックマーク (4)

  • 本当に1.5倍のほうがメモリ効率がよいのか - inamori’s diary

    C++のstd::vectorにpush_backしていくと、ある領域を確保して、それを超えそうになったらまたある程度ゆとりのある領域を確保するという機構になっています。 2倍だけじゃない - d.y.d. にまとめてありますが、std::vectorや類似するコンテナは2倍ずつ領域を大きくしていくのかと思いきや、1.5倍というのも多いんですね。実際にVC10 beta2で動かしてみると、 #include <iostream> #include <vector> int main() { std::vector<int> v; for(int i = 0; i < 100; i++) { const std::vector<int>::size_type old_cap = v.capacity(); v.push_back(i); const std::vector<int>::siz

    本当に1.5倍のほうがメモリ効率がよいのか - inamori’s diary
    kgbu
    kgbu 2010/07/24
    利用効率を実際にテストしてみた結果、あまり差はなく、むしろ2倍のほうが、コピー回数少ない利点があるのでは?、、ということらしい。母関数みたいなものを得ることはできるだろうか。
  • 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%)となることがわかります

  • L&#39;eclat des jours(2009-11-10)

    _ でっかなバッファを避ける? Aleviating Memory Fragmentation in Mono コンパクティングしなければ、いやでもフラグメントがどかどかできる。 するとでっかなバッファを取ろうとすると新しいページの割り当てが必要となりプロセスが肥大する。 だからでっかなバッファを要求すんな。細切れ継ぎ合わせメモリーストリームを使え。 と読んだ。 細切れ継ぎ合わせ方式だと実際のバッファへのポインタ分だけ余分なメモリをうわけだし、次の細切れへの移動にオーバーヘッドがかかるわけだが、それを補ってあまりある恩恵が得られればOK。 (ここで、「さっそく試してみる」といかないところがだめなところだ)

  • ■ - kurimura’s diary

    stack_ni_yasasii_free_tree treeを回転させて回転しきれなくなったら削除だと割と簡単にかける気がする。 void stack_ni_yasasii_free_tree(tree* t) { while(t){ tree*tmp; while(t->r){ tmp = t->r; t->r = tmp->l; tmp->l = t; t = tmp; } tmp = t; t = t->l; wrap_free(tmp); } }

    ■ - kurimura’s diary
  • 1