From: "U.Nakamura" <usa garbagecollect.jp>
Subject: [yarv-dev:544] Re: [im]mutable string
Date: Sun, 24 Jul 2005 01:24:38 +0900

> >    ◎:  C・O(n)、小さめのC
> >    ○:  C・O(n)、大きめのC

間違えました。これはどちらもC・O(1)です。
逐次アクセスというのは何らかのイテレータを使って順にアクセスする
形態を考えているので、次に読む文字への何らかのポインタを保持している
ことを前提にしています。var/[mi]で定数項が大きくなるのは、一文字を
取り出すのに若干手間がかかるから、くらいの理由です。

> (2) fix/mのN変更、var/mの1変更・N変更がn/aなのはなぜでしょう?
> mutableなんだから可能だと思うのですが?
> おそらく×になるのではないかと思いました。

char str[6] = "abcde"; で、strの "c" を "XXX" にその場で置き換えて
str = "abXXXde" にすることはできませんよね。(文字列実体の話をしている
ことを思い出して下さい)
var/mについてはさらに、1文字変更であってもそれがASCII文字から多バイト
文字への変更である可能性があるので一般に不可能です。
どちらも、実現するためには文字列実体の再アロケートが必要になります。
それはN変更・再構築というケースで表現しています。

それと、tre/iの部分文字列取り出しとN変更・再構築は木構造をコピー
する必要があるのでO(log(n))でしたね。△です。

--shiro




--
ML: yarv-dev quickml.atdot.net
使い方: http://www.atdot.net/~ko1/quickml