平々毎々(アーカイブ)

はてなダイアリーのアーカイブです。

アルゴリズムと数学

Radium Software Developmentより

vector のような可変長配列構造では,配列の要素が足りなくなると,「延び率」によって拡張された領域を確保し,そこへ古い配列の内容をコピーしてから,古い配列を解放するという手順を踏む。解放された古い領域はメモリの「断片」として残り,配列の拡張が行われる度に蓄積されることになるのだけれど,もし,拡張された領域のサイズが,この「断片」を合計したサイズよりも小さくなれば,「断片」の再利用が生じるはずだ。逆にこの「再利用」が発生しないと,配列は延々と新しい領域を確保し続け,メモリを一方的に消費してしまうこととなる。

では,この「断片の再利用」が生じる条件とは何なのだろうか……それが,「延び率を黄金比よりも小さくすること」であるということだ。これは恐らく,黄金比フィボナッチ数列の関連性から導くことができるのだと思うのだけれど,色々考えているうちに時間切れとなってしまった(もう寝なければ!)。

Radium Software Development: 040223 - Golden Ratio

やー、これは興味深い。

領域の伸び率を¥alpha(>1)とする。

ある時点での領域を単位サイズ(=1)とすると、次に拡張されたときのサイズは¥alpha¥alpha>1だから、この時点ではまだ再利用できない。

再び拡張されたときのサイズは¥alpha^2。この時点で、¥alpha^2¥leq¥alpha+1なら、領域を再利用できる。

ってことで、¥alpha^2-¥alpha-1=0という黄金比二次方程式を解いて、¥alpha>1の解だけを選んで、¥alpha=¥frac{1+¥sqrt{5}}{2}¥simeq1.618...