10:01 10/07/20 それでも２倍だ 先日の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%)となることがわかります

翻訳者前書き この文書は Why Not Numerical Recipes? の全訳です。 コメントは 中野武雄 (nakano@webmasters.gr.jp) までお願いします。 まあ NR もその後版を重ねてますし、 この文書の出所・文責もよくわからなくなってますんで、 どこまで信じるかは読者にお任せします (日付も入ってないし)。 以前は "Why not use Numerical Recipes" という、 もうちょっと reference に耐える文書があったように記憶しているのですが。 武井伸光さんには、訳文について多くの有益なコメントをいただきました。 件のページは http://math.jpl.nasa.gov/nr/ ではないか、 というご指摘を関根達夫さんからいただきました。 ただ残念ながらこのページは現在アクセスできないようです (のでリンクにはしてません)

『お絵描き掲示板』 に、「塗りつぶし」コマンド（＝お絵描きソフトで、ペンキ缶のアイコンのやつ） をつけようかなと思い、そのやり方を考えてみました。 そしたら、とてもいいロジックが出来たので紹介することにしました。 このロジックは、僕が今まで調べたもののうち、どんなものよりも高速で、 かつ単純なものになっています。 （もしかしたらさらに速いやり方があるかもしれません）。 ではさっそくそのロジック（アルゴリズム）を説明します。 一般的な塗りつぶしのアルゴリズムは以下のようなもの。 これは、走査線一本ごとに境界を探して行く方法なので、 「スキャンラインアルゴリズム」とか「走査線アルゴリズム」とか呼ばれている。 ＜処理ステップ＞ 前提として、図２のような、閉曲線（境界線）で囲まれた領域があるとする まず塗りつぶしを始める一点 ( X, Y ) を決める その座標 X, Y をスタックに積む