こんにちは、なかむら(う)です。

In message "[yarv-dev:545] Re: [im]mutable string"
    on Jul.24,2005 04:23:23, <shiro lava.net> wrote:
> > >    ◎:  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変更・再構築というケースで表現しています。

こっちも理解しました。
N変更・再構築と同じだから×だろう、と思ったのですが、そうなっ
てしまうからn/aと表現した、ということですね。


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

以上をまとめ直すと、こうですか。
いずれにせよ、mutableにしてもあんまりええことないよ、という話
にはあんまり影響ないですね。

        逐次    添字   連結   1変更   N変更   検索   部分     N変更・再構築

fix/m    ◎     ◎     ×     ◎     n/a     ◎     ×        ×
fix/i    ◎     ◎     ×     n/a    n/a     ◎     ◎        ×
var/m    ○     ×     ×     n/a    n/a     ◎     ×        ×
var/i    ○     ×     ×     n/a    n/a     ◎     ◎        ×
lis/m    ◎     ×     ×     ×     ×      ○     ×        ×
lis/i    ◎     ×     ×     n/a    n/a     ○     ×(*1)    ×
tre/m    ○     △     ◎     △     △      ○     △        △
tre/i    ○     △     ◎     n/a    n/a     ○     △        ◎


操作：

   逐次:各文字への逐次アクセス       添字:文字インデックスによるアクセス
   連結:連結による文字列作成        1変更:1文字のみの(長さを変えない)変更
   N変更:N文字の(長さを変える)変更   検索: 部分文字列検索
   部分:部分文字列の取り出し         
   N変更・再構築: 長さを変える変更を、新たな文字列構築として行う

評価：
   ◎:  C・O(1)、小さめのC
   ○:  C・O(1)、大きめのC
   △:  O(log(n))
   ×:  O(n)
   n/a: 操作そのものが不可能

  (*1) 末尾を共有する文字列の場合◎、その他の場合×



それでは。
-- 
U.Nakamura <usa garbagecollect.jp>


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