[ruby-list:11794] Re: Array.new([SIZE])

まつもと ゆきひろです

In message "[ruby-list:11770] Re: Array.new([SIZE])"
    on 99/01/28, Yoshinori Toki <[e-mail]> writes:

|土岐です。

|現在の配列の実装は、配列の大きさが拡張されるとき内部のメモリは常に「必
|要な大きさ + 16」に拡張されるようです。これだと、配列が大きくなるにつ
|れてコピーの手間がどんどん増えてしまいます。一方、配列が短くなるときは
|内部のメモリが配列の長さの 1/10 になったときに内部のメモリが切り詰めら
|れているようです。ソースの array.c をざっと眺めてみたところ、こうなっ
|てるように思ったんですけど、あってるでしょうか？

あってます．

|この仕様だと、長さゼロの配列に push して巨大配列を作ろうとすると、追加
|する数 n に対して内部メモリーの再確保＆複製が O(n) 回生じます。一方、
|巨大配列から pop していくときは、切り詰める長さが配列長に応じて変化す
|るので、内部メモリーの再確保＆複製は O(log n) 回生じることになり、この
|コストは push していく時と比較してかなり低いです。

そうですね．いろいろ考えたのですが，割り当てサイズが大きくな
るほど無駄が出るというデメリットがないわけでもないですが，少々
の無駄は妥協できるような気がしたので採用しましょう．

                                まつもと ゆきひろ /:|)