天泣記

うぅむ。subsume は「包摂する」と訳されるのか...

% google-count FileUtils.{cd,pwd,mkdir,mkdir_p,rmdir,ln,ln_s,ln_sf,cp,cp_r,mv,rm,rm_r,rm_rf,install,chmod,touch}
87      FileUtils.cd
82      FileUtils.pwd
520     FileUtils.mkdir
53      FileUtils.mkdir_p
326     FileUtils.rmdir
332     FileUtils.ln
28      FileUtils.ln_s
7       FileUtils.ln_sf
1200    FileUtils.cp
112     FileUtils.cp_r
637     FileUtils.mv
423     FileUtils.rm
39      FileUtils.rm_r
83      FileUtils.rm_rf
1240    FileUtils.install
3560    FileUtils.chmod
326     FileUtils.touch

うぅむ。あんま適切じゃないか。

% for w in {cd,pwd,mkdir,mkdir_p,rmdir,ln,ln_s,ln_sf,cp,cp_r,mv,rm,rm_r,rm_rf,install,chmod,touch}

do
google-count -w ruby FileUtils.$w
done
42      ruby FileUtils.cd
61      ruby FileUtils.pwd
183     ruby FileUtils.mkdir
53      ruby FileUtils.mkdir_p
153     ruby FileUtils.rmdir
147     ruby FileUtils.ln
28      ruby FileUtils.ln_s
7       ruby FileUtils.ln_sf
299     ruby FileUtils.cp
94      ruby FileUtils.cp_r
156     ruby FileUtils.mv
165     ruby FileUtils.rm
39      ruby FileUtils.rm_r
64      ruby FileUtils.rm_rf
189     ruby FileUtils.install
191     ruby FileUtils.chmod
158     ruby FileUtils.touch

2004/02/08

#1: コンテキスト (穴があいた項) をファーストクラスオブジェクトとして扱うとすると、どういうインターフェースになるだろう?

2004/02/09

停電と聞いて shutdown したにも関わらず停電しない場合、自動的には reboot できないことに気がつく。

On parent pointers in SXML trees

うぅむ、どれもいまいち。まぁ、完璧な解はないということかな。

2004/02/10

Parents and Grove Plans

ふむ。

ざっとみると、親への参照を直接持たせることの欠点としてあげられているのはこんなかんじか。

参照しない祖先のほうも GC できなくなる
marshal すると祖先もくっついてくる
(Scheme の) equal? で扱えなくなる
(Scheme の) display だの write だので扱えなくなる
部分木を他の木に接ぐときに share できない
mutation が必要
hashed consing みたいなことができない

逆に親への参照があることによる嬉しさをまとめた話ってないのかな。

parentNode を探せばいい?

でも、リファレンスばかりひっかかる。

2004/02/11

ソースコードを対象にした検索エンジンってないのかな。

「ソースコード検索」を検索すると研究はいくつかひっかかるようだが、運用/サービスしているところはないのだろうか。

getParentNode を探していくつか用例を抜きだしてみる。

そのノードを削除する
そのノードを他のノードに入れ換える
そのノードの直前に追加
そのノードの兄弟の末尾に追加
そのノードを兄弟の末尾に移動
兄弟を調べる
そのノードの場所を示す xpath を作る
上に昇って行ってルートノードを得る
JavaScript で、スクリプトを書いた要素からいくつか上の要素を得る
tr が table 中の何番目かを調べる
DRAFT 要素の内部かどうかで処理を変える
DFS 的に直前/直後のノードを得る
祖先ノードのリストを得る
ノードを(破壊的に)挿入するときにそのノード自身が祖先でないことを確認する
ノードを親と切り離す

兄弟というのはべつに姉妹でもかまわないはずだよな...

姉妹ノードとか。

#4

% google-count {レッツ,れっつ}{ラ,ら,}{ゴー,ごー}
4500    レッツラゴー
35      レッツラごー
1540    レッツらゴー
67      レッツらごー
61300   レッツゴー
161     レッツごー
0       れっつラゴー
4       れっつラごー
160     れっつらゴー
1030    れっつらごー
196     れっつゴー
3190    れっつごー

2004/02/12

% google-count プログラ{マブル,マル,丸}
31400   プログラマブル
37      プログラマル
0       プログラ丸

g新部さんの日記

2004/02/13

#1: 東京

2004/02/14

% google-count {グーグル,google}\ {カウント,count}
0       グーグル カウント
0       グーグル count
0       google カウント
1750    google count

以前いれた Check_Type は効いているらしい

wrong argument type String (expected Regexp) (TypeError)

というのが捕まった。

これが出た行は

if /\A(?:#{Pat::StartTag}|#{Pat::EmptyTag})\z/o !~ raw_string

で、このパターンが String にすりかわっているわけだが、さて、どうやったら追い詰められるかな。

% google-count partial{-,}read read{-,}partial partial{-,}write write{-,}partial 
3090    partial-read
17      partialread
1220    read-partial
194     readpartial
4980    partial-write
18      partialwrite
1070    write-partial
49      writepartial

2004/02/15

% google-count は不幸を{まねく,招く}
4       は不幸をまねく
203     は不幸を招く

2004/02/16

wrong argument type String (expected Regexp) (TypeError) がもう一回。

if v && %r{\A#{RE_LWS}?(#{RE_TOKEN})#{RE_LWS}?/(#{RE_TOKEN})#{RE_LWS}?(#{RE_PARAMETERS})\z}o =~ v

というところで、前回と違う場所なのはちょっと意外。

o が怪しい感じ?

それとは別に Bus Error も出ていた。

signal handler が入っていると stack trace が甘くなるので、 SEGV と同様 disable しておく。

再現させることに成功したので報告したら、既知だそうな。

うぅむ。気になりはじめてから 2ヵ月もかかったというのに。

2004/02/19

Valid XML の仕組み - Web SGML 関連 - 内容中の空白

「TEXTAREA要素のレンダリングについて」というのを読んで、 XML (XHTML) にはそういう改行を無視する規定があるのかどうか調べてみる。

やはり XML には無いな。

On SGML and HTML - SGML Constructs used in HTML

2004/02/20

wiki で各ページのソースをとって来るにはどうしたらいいか?

ソースをとって来るコマンドを用意している wiki もある。しかし、text/plain から text/html に変えるなど、あまり安定でない感じ。そもそもあまり使われないから壊れると壊れっぱなしになる傾向も感じられる。
編集の textarea からとってくることもできる。しかし、凍結されて編集できない wiki からはとれないことがある。

2004/02/21

実際のところ本当に改行の無視が全部の要素に影響するのかどうか調べてみる。

<p>
xxx<b>
xxx
</b>xxx
</p>

<p>
xxx
<b>xxx</b>
xxx
</p>

<p>
xxx<b>xxx</b>xxx
</p>

これで単語間に空白が入るかどうかでわかるはず... うぅむ。mozilla は無視しないな。

では block 要素だけなのか、と思うと textarea は inline 要素だよなぁ。

2004/02/23

最近、sym_inspect で

==> bugs/20040201-132836/backtrace <==
Core was generated by `ruby ./main.rb -v'.
Program terminated with signal 11, Segmentation fault.
#0  0x0807f1db in sym_inspect (sym=14) at object.c:1126
1126	    str = rb_str_new(0, strlen(name)+1);
#0  0x0807f1db in sym_inspect (sym=14) at object.c:1126
#1  0x0805b9c1 in rb_call0 (klass=1075634596, recv=14, id=3169, oid=3169, argc=0, argv=0x0, body=0x401ce0dc, nosuper=0)
    at eval.c:5299
#2  0x0805c3e6 in rb_call (klass=1075634596, recv=14, mid=3169, argc=0, argv=0x0, scope=1) at eval.c:5642
#3  0x0805c639 in rb_funcall (recv=14, mid=3169, n=0) at eval.c:5725
#4  0x0807ea27 in rb_inspect (obj=14) at object.c:364

==> bugs/20040219-065946/backtrace <==
Core was generated by `ruby ./main.rb -v'.
Program terminated with signal 11, Segmentation fault.
#0  0x0807f4bb in sym_inspect (sym=14) at object.c:1134
1134	    str = rb_str_new(0, strlen(name)+1);
#0  0x0807f4bb in sym_inspect (sym=14) at object.c:1134
#1  0x0805ba71 in rb_call0 (klass=1075634596, recv=14, id=3169, oid=3169, 
    argc=0, argv=0x0, body=0x401ce0dc, nosuper=0) at eval.c:5302
#2  0x0805c476 in rb_call (klass=1075634596, recv=14, mid=3169, argc=0, 
    argv=0x0, scope=1) at eval.c:5641
#3  0x0805c6c9 in rb_funcall (recv=14, mid=3169, n=0) at eval.c:5724

==> bugs/20040220-122308/backtrace <==
Core was generated by `ruby ./main.rb -v'.
Program terminated with signal 11, Segmentation fault.
#0  0x0807f4bb in sym_inspect (sym=14) at object.c:1134
1134	    str = rb_str_new(0, strlen(name)+1);
#0  0x0807f4bb in sym_inspect (sym=14) at object.c:1134
#1  0x0805ba71 in rb_call0 (klass=1075634596, recv=14, id=3169, oid=3169, 
    argc=0, argv=0x0, body=0x401ce0dc, nosuper=0) at eval.c:5302
#2  0x0805c476 in rb_call (klass=1075634596, recv=14, mid=3169, argc=0, 
    argv=0x0, scope=1) at eval.c:5641
#3  0x0805c6c9 in rb_funcall (recv=14, mid=3169, n=0) at eval.c:5724

というように core を吐くことがあり、そのうち調べようと思っていたのだが、ふと backtrace をもうちょっと奥まで眺めると、

==> bugs/20040201-132836/backtrace <==
Core was generated by `ruby ./main.rb -v'.
Program terminated with signal 11, Segmentation fault.
#0  0x0807f1db in sym_inspect (sym=14) at object.c:1126
1126	    str = rb_str_new(0, strlen(name)+1);
#0  0x0807f1db in sym_inspect (sym=14) at object.c:1126
#1  0x0805b9c1 in rb_call0 (klass=1075634596, recv=14, id=3169, oid=3169, argc=0, argv=0x0, body=0x401ce0dc, nosuper=0)
    at eval.c:5299
#2  0x0805c3e6 in rb_call (klass=1075634596, recv=14, mid=3169, argc=0, argv=0x0, scope=1) at eval.c:5642
#3  0x0805c639 in rb_funcall (recv=14, mid=3169, n=0) at eval.c:5725
#4  0x0807ea27 in rb_inspect (obj=14) at object.c:364
#5  0x0805ade6 in rb_protect (proc=0x807ea0c <rb_inspect>, data=14, state=0x0) at eval.c:5070
#6  0x080c5577 in name_err_mesg_to_str (obj=1080015796) at error.c:722
#7  0x0805b9c1 in rb_call0 (klass=1075622796, recv=1080015796, id=4345, oid=4345, argc=0, argv=0x0, body=0x401cb314, 
    nosuper=0) at eval.c:5299
#8  0x0805c3e6 in rb_call (klass=1075622796, recv=1080015796, mid=4345, argc=0, argv=0x0, scope=1) at eval.c:5642
#9  0x0805c639 in rb_funcall (recv=1080015796, mid=4345, n=0) at eval.c:5725
#10 0x080800a3 in convert_type (val=1080015796, tname=0x80e04c1 "String", method=0x80e04ba "to_str", raise=2)
    at object.c:1993
#11 0x08080140 in rb_convert_type (val=1080015796, type=7, tname=0x80e04c1 "String", method=0x80e04ba "to_str")
    at object.c:2005
#12 0x080ab93e in rb_str_to_str (str=1080015796) at string.c:233
#13 0x080ac0d3 in rb_string_value (ptr=0xbffd9e20) at string.c:523
#14 0x080c4dbc in exc_initialize (argc=1, argv=0xbffda190, exc=1080015776) at error.c:348
#15 0x080c52b0 in name_err_initialize (argc=2, argv=0xbffda190, self=1080015776) at error.c:612
#16 0x080c5418 in nometh_err_initialize (argc=3, argv=0xbffda190, self=1080015776) at error.c:670
#17 0x0805b98e in rb_call0 (klass=1075622556, recv=1080015776, id=2961, oid=2961, argc=3, argv=0xbffda190, 
    body=0x401cb274, nosuper=0) at eval.c:5293
#18 0x0805c3e6 in rb_call (klass=1075622556, recv=1080015776, mid=2961, argc=3, argv=0xbffda190, scope=1) at eval.c:5642
#19 0x0805c6b9 in rb_funcall2 (recv=1080015776, mid=2961, argc=3, argv=0xbffda190) at eval.c:5735
#20 0x0805e957 in rb_obj_call_init (obj=1080015776, argc=3, argv=0xbffda190) at eval.c:7059
#21 0x0807f7ef in rb_class_new_instance (argc=3, argv=0xbffda190, klass=1075622556) at object.c:1539
#22 0x0805b1d8 in rb_method_missing (argc=1, argv=0xbffda4c0, obj=14) at eval.c:5234
#23 0x0805b98e in rb_call0 (klass=1075637416, recv=14, id=3881, oid=3881, argc=1, argv=0xbffda4c0, body=0x401cd1a0, 
    nosuper=0) at eval.c:5293
#24 0x0805c3e6 in rb_call (klass=1075637416, recv=14, mid=3881, argc=1, argv=0xbffda4c0, scope=1) at eval.c:5642
#25 0x0805c6b9 in rb_funcall2 (recv=14, mid=3881, argc=1, argv=0xbffda4c0) at eval.c:5735
#26 0x0805b2e9 in method_missing (obj=14, id=11777, argc=0, argv=0x0, call_status=0) at eval.c:5267
#27 0x0805c2d4 in rb_call (klass=1075634596, recv=14, mid=11777, argc=0, argv=0x0, scope=0) at eval.c:5622
#28 0x0805741f in rb_eval (self=1078776396, n=0x4034dffc) at eval.c:3240
#29 0x08057238 in rb_eval (self=1078776396, n=0x4034dfc0) at eval.c:3234
#30 0x0805a0e3 in rb_yield_0 (val=1080017376, self=1078776396, klass=0, flags=0, avalue=2) at eval.c:4658
#31 0x0805a328 in rb_yield_values (n=2) at eval.c:4735
#32 0x0806d304 in delete_if_i (key=1075628116, value=14) at hash.c:686
#33 0x0806cbcf in rb_hash_foreach_iter (key=1075628116, value=14, arg=0xbffdb3cc) at hash.c:133
#34 0x080ab494 in st_foreach (table=0x8876e90, func=0x806cb9c <rb_hash_foreach_iter>, arg=3221074892) at st.c:495
#35 0x0806cc1c in rb_hash_foreach_call (arg=0xbffdb3cc) at hash.c:144
#36 0x0805ae90 in rb_ensure (b_proc=0x806cc00 <rb_hash_foreach_call>, data1=3221074892, 
    e_proc=0x806cc24 <rb_hash_foreach_ensure>, data2=1078776316) at eval.c:5096
#37 0x0806cc97 in rb_hash_foreach (hash=1078776316, func=0x806d2e8 <delete_if_i>, farg=0) at hash.c:175
#38 0x0806d33b in rb_hash_delete_if (hash=1078776316) at hash.c:708
#39 0x0805b9c1 in rb_call0 (klass=1075603956, recv=1078776316, id=6681, oid=6681, argc=0, argv=0x0, body=0x401c6490, 
    nosuper=0) at eval.c:5299

というように delete_if から来ていることに気がつく。他の 2つも同様。ふむ、delete_if がらみなら、すでに報告したぶんがどうにかなってからでいいか。

そういえば、 delete_if 関連では、undefined method `queue' for 5:Fixnum (NoMethodError) といったエラーも出る。 sym_inspect が name_err_mesg_to_str からきているところをみると、それが core dump までたどり着いたということか。

2004/02/25

Golden Ratio

というのを読んで、配列の拡張の比は黄金比以下がいいという理屈がどういうことなのか考えてみる。

最初に確保するメモリ量が a とし、拡張の比が r>1 とすると、配列を伸ばしていくプログラムは順に a, ar, ar^2, ar^3, ... という量を確保し、そのたびにそれ以前に確保したぶんを開放することになる。

ということは、『「断片の再利用」が生じる条件』は (開放したのが全部連続しているなどのさまざまな仮定をおけば)

a+ar+ar^2+...+ar^(n-1) >= ar^n

というように、それ以前に開放した総量が確保しようとしている量を越えることがある場合と定式化できる。

これを n について解くと、

n >= -log(2-r)/log(r)

となる。これをみると、r が 2以上だと log の引数が 0 以下になって解がないことがわかる。逆にいえば r が 2未満なら、いつか断片の再利用が起き得るわけで、黄金比は出て来ない。おや?

なんか変なので元ネタをたどっていくと... そーか。いつか起き得るのではなく、2回目に起きる条件なのか。

a+ar >= ar^2

というのを解くと、たしかに黄金比の (1+sqrt(5))/2 が出て来る。

しかし... 等比数列の和と 2次方程式の解の公式を忘れていて検索しなければならなかったのはちょっとナニ。

しかし、考えてみると、最初に aバイトだけ malloc で確保し、次に arバイトに realloc で増やしたときに、それが連続した領域に割り付けられるというのは現実的な仮定なのだろうか?

もし aバイトの直後に arバイト空いているなら realloc は arバイトを確保してから aバイトを開放するなんてせずに、単に ar-aバイトだけ伸ばすのではないだろうか。そうすれば、ヒープ全体の量も a+arバイトじゃなくて arバイトに抑えられるし、コピーも不要なので都合がいいように思える。

そういう工夫はしないという仮定は現実的なのだろうか? この工夫は、行わないにはあまりに自明すぎるように思える。

kern/61691: very bad performance of realloc()/brk()

こういうときには古いのを調べるに限る、というわけで、Version 7 の realloc を眺める。

... realloc は free してから malloc してアドレスが同じだったらそのまま return しており、 free は free した領域を次の malloc が最初に探すように設定してる。 (そういえば、以前に malloc はそういう実装だから云々という伝承を読んだ気がしないでもない)

というわけで、Version 7 でさえそういう挙動になるようだ。そういう古いのでさえそうしているということは、現代の realloc がそうしていないということは考えにくい。 (そうすることによる欠点がなにかあれば別だけど、思いつかない)

つまり、この件に関しては、黄金比というのは机上の空論に近いように思う。

#4

いや、そういえば [ruby-dev:16808] という話があった。

FreeBSD libc の realloc が遅いというのはもしかしてそういう挙動ではないのだろうか?

ソースを眺める。

R (malloc_realloc) というオプションによるらしい。で、これがデフォルトではどうなのかというと... どうなんだ?

#5

Malloc(3) revisited

#6

だんだんと増やしてくのは間違ってるっていう主張?

2004/02/26

BSD における malloc(3) の実装の変遷

FreeBSD 2.2 Release Notes

2004/02/27

undefined method `queue' というのは

2003-07-08T11:45:53+09:00 undefined method `queue' for 5:Fixnum
2003-07-14T11:07:06+09:00 undefined method `queue' for 5:Fixnum
2003-07-15T16:54:33+09:00 undefined method `queue' for 5:Fixnum
2003-07-23T12:54:36+09:00 undefined method `queue' for 5:Fixnum
2003-07-26T06:23:59+09:00 undefined method `queue' for 5:Fixnum
2003-07-26T23:22:20+09:00 undefined method `queue' for 5:Fixnum
2003-08-04T12:35:31+09:00 undefined method `queue' for 5:Fixnum
2003-08-07T15:18:21+09:00 undefined method `queue' for 5:Fixnum
2003-08-11T15:47:03+09:00 undefined method `queue' for 5:Fixnum
2003-08-25T11:22:15+09:00 undefined method `queue' for 5:Fixnum
2003-08-25T14:23:54+09:00 undefined method `queue' for 7:Fixnum
2003-09-03T15:17:09+09:00 undefined method `queue' for 4:Fixnum
2003-09-03T18:17:59+09:00 undefined method `queue' for 5:Fixnum
2003-09-12T01:11:55+09:00 undefined method `queue' for 5:Fixnum
2003-09-23T01:23:55+09:00 undefined method `queue' for 5:Fixnum
2003-10-01T01:37:48+09:00 undefined method `queue' for 5:Fixnum
2003-10-02T20:49:45+09:00 undefined method `queue' for 5:Fixnum
2003-10-03T03:23:23+09:00 undefined method `queue' for 5:Fixnum
2003-10-05T09:12:03+09:00 undefined method `queue' for 5:Fixnum
2003-10-08T11:27:41+09:00 undefined method `queue' for 5:Fixnum
2003-10-10T10:03:49+09:00 undefined method `queue' for 5:Fixnum
2003-10-16T14:00:30+09:00 undefined method `queue' for 6:Fixnum
2003-10-27T01:58:50+09:00 undefined method `queue' for 5:Fixnum
2003-11-01T19:18:53+09:00 undefined method `queue' for 7:Fixnum
2003-11-02T02:00:51+09:00 undefined method `queue' for 5:Fixnum
2003-11-07T19:41:29+09:00 undefined method `queue' for 5:Fixnum
2003-11-11T02:59:58+09:00 undefined method `queue' for 10:Fixnum
2003-11-12T00:22:29+09:00 undefined method `queue' for 9:Fixnum
2003-11-14T14:18:07+09:00 undefined method `queue' for 5:Fixnum
2003-11-23T23:08:30+09:00 undefined method `queue' for 12:Fixnum
2003-11-25T18:59:08+09:00 undefined method `queue' for 5:Fixnum
2003-11-29T14:27:34+09:00 undefined method `queue' for 5:Fixnum
2003-12-03T12:21:55+09:00 undefined method `queue' for 5:Fixnum
2003-12-11T04:46:58+09:00 undefined method `queue' for 5:Fixnum
2003-12-14T02:30:40+09:00 undefined method `queue' for 5:Fixnum
2003-12-14T12:44:20+09:00 undefined method `queue' for 5:Fixnum
2003-12-16T07:37:50+09:00 undefined method `queue' for 5:Fixnum
2003-12-16T22:49:52+09:00 undefined method `queue' for 7:Fixnum
2003-12-17T05:15:15+09:00 undefined method `queue' for 7:Fixnum
2003-12-17T15:48:24+09:00 undefined method `queue' for 5:Fixnum
2003-12-22T02:43:01+09:00 undefined method `queue' for 5:Fixnum
2003-12-23T23:31:13+09:00 undefined method `queue' for 6:Fixnum
2003-12-24T09:46:53+09:00 undefined method `queue' for 5:Fixnum
2003-12-26T17:18:19+09:00 undefined method `queue' for 5:Fixnum
2004-01-05T22:54:33+09:00 undefined method `queue' for 5:Fixnum
2004-01-07T13:20:26+09:00 undefined method `queue' for 9:Fixnum
2004-01-08T13:36:20+09:00 undefined method `queue' for 5:Fixnum
2004-01-14T05:08:27+09:00 undefined method `queue' for 6:Fixnum
2004-01-14T11:33:18+09:00 undefined method `queue' for 444611122:Fixnum
2004-01-14T19:56:33+09:00 undefined method `queue' for 5:Fixnum
2004-01-15T21:30:29+09:00 undefined method `queue' for 9:Fixnum
2004-01-16T18:30:37+09:00 undefined method `queue' for 5:Fixnum
2004-01-17T14:49:18+09:00 undefined method `queue' for 14898:Fixnum
2004-01-18T01:50:35+09:00 undefined method `queue' for 536885810:Fixnum
2004-01-19T23:27:22+09:00 undefined method `queue' for #<Fixnum:0xb>
2004-01-20T14:42:21+09:00 undefined method `queue' for 5:Fixnum
2004-01-21T11:56:56+09:00 undefined method `queue' for 5:Fixnum
2004-01-26T10:51:55+09:00 undefined method `queue' for 5:Fixnum
2004-01-26T13:58:05+09:00 undefined method `queue' for 5:Fixnum
2004-02-03T11:15:19+09:00 undefined method `queue' for 5:Fixnum
2004-02-03T16:46:04+09:00 undefined method `queue' for 5:Fixnum
2004-02-04T11:19:35+09:00 undefined method `queue' for 6:Fixnum
2004-02-06T02:31:20+09:00 undefined method `queue' for 9:Fixnum
2004-02-06T16:14:18+09:00 undefined method `queue' for 5:Fixnum
2004-02-07T15:26:40+09:00 undefined method `queue' for 5:Fixnum
2004-02-20T21:23:28+09:00 undefined method `queue' for 5:Fixnum
2004-02-22T02:26:26+09:00 undefined method `queue' for 5:Fixnum
2004-02-23T14:59:20+09:00 undefined method `queue' for 5:Fixnum
2004-02-26T15:18:20+09:00 undefined method `queue' for 5:Fixnum

というくらい出ている。これは core を吐くよりもずっと多い。

さて、どうなりますかね。

ふと、http://www.ruby-lang.org/favicon.ico が IE で表示できないことに気がつく。

% google-count レガシー{フレンドリー,重要,じゅーよー}
0       レガシーフレンドリー
0       レガシー重要
0       レガシーじゅーよー

#4

ふと配列を等比数列で伸ばしていくときのコピーのコストを見積もってみる。

malloc(a), realloc(ar), realloc(ar^2), ..., realloc(ar^n) としたとき、コピー量は a + ar + ... + ar^(n-1) = a(r^n-1)/(r-1) である。

つまり、確保したメモリ量 ar^n に対し、a(r^n-1)/(r-1) のコピーが行われ、その比は 1/(r-1)-1/((r-1)r^n) になる。

ここで、十分に大きなメモリが必要になったとすれば、つまり十分にたくさん realloc を繰り返すはめになって n が大きくなったとすれば、比は 1/(r-1) に漸近する。

つまり、メモリを漸増的に確保するには最終的に確保するメモリの量に比例する時間がかかると概算できる。

さて、プログラムがメモリを確保する場合、そのメモリは使うために確保するわけで、何らかの値で確保したメモリを埋めるのが普通である。そして、メモリを埋めるには当然ながらそのメモリの量に比例する時間がかかる。

そしてプログラムの時間計算量を考えると、そのなかには確保したメモリを埋める部分がはいっているわけで、 realloc によるコピーのコストを含めることは、その部分の係数を増やすことになる。つまり、係数が増えるだけなのでオーダは変わらない。

なお、係数の増加は 1/(r-1) で効くので、 r をあまり 1 に近づけないことが肝要である。あたりまえか。

2004/02/28