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

In message "[yarv-dev:541] Re: [im]mutable string"
    on Jul.21,2005 18:58:58, <shiro lava.net> wrote:
> 以下、実装レベルと言語設計レベルで分けて議論します。

とてもためになりました。ありがとうございます。

ただ、IRCで他の方とも話をしてみて、幾つか疑問が生じたので確認
させてください。
(アホなこと言ってると思ったら切って捨ててください ^^;)

>         逐次    添字   連結   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     ○     ◎        ◎
(snip)
> 評価：
>    ◎:  C・O(n)、小さめのC
>    ○:  C・O(n)、大きめのC
>    △:  O(log(n))
>    ×:  O(n)
>    n/a: 操作そのものが不可能

(1) 逐次の場合、C・O(n)となるのはわかる気がするのですが、その
他の場合に関しては、◎も○も、C・O(n)ではなくてC・O(1)ではな
いでしょうか?

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


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


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