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

土岐です。

From: Koji Arai <[e-mail]>
Subject: [ruby-list:11768] Re: Array.new([SIZE])
Date: Thu, 28 Jan 1999 00:04:22 +0900

> > Array.new()の仕様が今のようになった以上、
> > 「メモリのリアロケートが裏で発生するかもしれない」
> > という考えは捨て去るのが健康的かも知れない。
> 
> こういう理想がある以上、やはりこれを追求するべきだ
> と思いました。このような考えに至ったのは、

蛇足ですが、理想に半歩近づくかもしれない方法を考えてみました。既に考慮
されてたらごめんなさい。

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

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

# うーん、ビッグ O 記法の使い方ってこれでいいんだろうか。
# 本当は再確保＆複製の手間の考慮しないといけないような気がする。

だったら配列を拡張するときも内部のメモリの増分を現在の長さに応じて変化
させればいいのではと考えて、とりあえずパッチを作ってみました。内部のメ
モリは現在の長さに対して 3/2 倍ずつ増えてゆきます。当然ながら、メモリ
は余分に消費することになります。メモリよりも速度を優先する人にはいいか
も。

*** array.c.orig	Thu Jan 28 02:10:25 1999
--- array.c	Thu Jan 28 02:13:11 1999
***************
*** 231,237 ****
      }
  
      if (idx >= RARRAY(ary)->capa) {
! 	RARRAY(ary)->capa = idx + ARY_DEFAULT_SIZE;
  	REALLOC_N(RARRAY(ary)->ptr, VALUE, RARRAY(ary)->capa);
      }
      if (idx > RARRAY(ary)->len) {
--- 231,241 ----
      }
  
      if (idx >= RARRAY(ary)->capa) {
! 	int capa_inc = RARRAY(ary)->capa / 2;
! 	if (capa_inc < ARY_DEFAULT_SIZE) {
! 	    capa_inc = ARY_DEFAULT_SIZE;
! 	}
! 	RARRAY(ary)->capa = idx + capa_inc;
  	REALLOC_N(RARRAY(ary)->ptr, VALUE, RARRAY(ary)->capa);
      }
      if (idx > RARRAY(ary)->len) {
***************
*** 304,310 ****
  {
      ary_modify(ary);
      if (RARRAY(ary)->len >= RARRAY(ary)->capa) {
! 	RARRAY(ary)->capa+=ARY_DEFAULT_SIZE;
  	REALLOC_N(RARRAY(ary)->ptr, VALUE, RARRAY(ary)->capa);
      }
  
--- 308,318 ----
  {
      ary_modify(ary);
      if (RARRAY(ary)->len >= RARRAY(ary)->capa) {
! 	int capa_inc = RARRAY(ary)->capa / 2;
! 	if (capa_inc < ARY_DEFAULT_SIZE) {
! 	    capa_inc = ARY_DEFAULT_SIZE;
! 	}
! 	RARRAY(ary)->capa+=capa_inc;
  	REALLOC_N(RARRAY(ary)->ptr, VALUE, RARRAY(ary)->capa);
      }
  
----------------------------------------------------------------------------
土岐 仁謙	神戸大学高エネ研 Ｍ１
URL: http://www3.phys.sci.kobe-u.ac.jp/~toki/index.html
PGP fingerprint = D0 A8 90 AB 73 F8 34 FE  CE CA DB BF 01 30 C0 35