この話題は，langsmith とかの方が適切じゃないかと思いますが…

SASADA Koichi <ko1 atdot.net> writes:

> b. 実行効率の高さ（トータルな計算時間）
> b.1: immutable だとリテラルごとに文字列生成する必要がなくなって効率的
> （共有、非共有などが処理系の都合で柔軟に行える）
> b.2: immutable だと排他制御気にしなくていいので
> b.3: mutable だと文字列変更操作が使えるのでそのつど新しい文字列を生成し
> なくてよいので効率的（bang メソッドが使える、etc）
> 
> 　など、定性的な議論はできると思うのですが（これについて、間違い、追加な
> どあればご指摘ください）、なかなか定量的な議論は無いような気がします。

mutableで共有するには，copy-on-writeを使うのでしょうね．
昔のJavaのStringBufferではそうやってた気がする．

bang methodを使うと効率が良くなる例というのは，「1文字だけ書き換える」
とかは多分それほどなくて，「少しずつ後ろにアペンドしていく」ような場合
ですかね．ナイーブにやるとO(n^2)になってしまう．mutableな文字列でも，
長さに余裕を見たデータ構造(サイズと現在の長さが別である構造)じゃないと
O(n^2)になる．

immutableでも，gaucheのライブラリにあるlazy text constructionみたいな
ことをすれば，appendの効率も問題にならないと思うけど…

> Q1. これについて、定量的な議論をした論文なり研究成果をご存知の方はいらっ
> しゃいませんか？

決定版はすぐには見つかりませんでしたが，以下のようなのがありました．
 String Implementation comparison in Java, Icon, Python, and Lisp
http://www.cs.arizona.edu/~collberg/Teaching/520/2003/Projects/wangj.ps.gz

Mutable strings in Java: design, implementation and lightweight
 text-search algorithms
http://vigna.dsi.unimi.it/ftp/papers/MutableStrings.pdf

> 　で、多分無さそうなのですが、じゃぁ、とりあえず各言語がどんな仕様なのか
> 集めてみようかと思いまして。
> 
> 
> * mutable
>   * Ruby
>   * Scheme

Schemeでは，symbolの名前文字列をmutateしてはいけない(it is an error)と
いうことになっています．「そんなことしたら，どうなっても知らんよ」とい
うわけですが，immutableな文字列のサブタイプを持つ処理系も規格的にはOK
です．

(define sym 'dont-modify-me)
(string-set! (symbol->string sym) 0 #\a)
sym

とやると，Petit Chez Schemeは aont-modify-me を返し，
guile, scm は変更されないまま dont-modify-me を返します．
gauche は ERROR: attempted to modify immutable string: "dont-modify-me"
というエラーとなります．

> * immutable
>   * Java
>   * Python

JavaはStringBuffer (StringBuilder) がありますよね．

				前田敦司

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