[解決済み】.NETで文字列が不変なら、なぜSubstringはO(n)時間かかるの？

質問

.NETでは文字列は不変であるのに、なぜ string.Substring() はO( substring.Length ) の時間ではなく O(1) ?

つまり、トレードオフがあるとすれば、それは何だったのでしょうか？

解決方法は？

UPDATE: この質問がとても気に入ったので、ブログに書きました。参照 文字列、不変性、永続性

簡単に言うと O(n)は、nが大きくならなければO(1)です。 ほとんどの人は小さな文字列から小さな部分文字列を取り出すので、漸近的にどのように複雑さが増していくかは 全く関係ない .

長くなりましたが、その答えは

インスタンスに対する操作によって、わずかな量（通常 O(1) または O(lg n)）のコピーまたは新規割り当てで元のメモリを再利用できるように構築された不変データ構造を、quot; persistent" immutable data structure と呼びます。.NETの文字列は不変ですが、ご質問は本質的に「なぜ永続的でないのですか？

という操作に注目すると 通常 .NETプログラムで文字列に対して行われることは、あらゆる関連する方法で ほとんど悪化しない は、単に全く新しい文字列を作成することです。 複雑な永続的データ構造を構築するための費用と難易度は、それ自体ではペイしないのです。

通常、quot;substring"は、ある程度長い文字列（数百文字程度）の中から、短い文字列（例えば10文字や20文字）を取り出すために使用されます。カンマで区切られたファイルのテキスト行があり、3番目のフィールドである姓を抽出したいとします。行の長さは数百文字で、名前は数十文字です。文字列の割り当てと50バイトのメモリコピーは 驚異的な速さ 最近のハードウェアでは 既存の文字列の中央へのポインタと長さからなる新しいデータ構造を作ることは また 驚くほど速いというのは関係なく、「十分速い」というのは定義上、十分速いということです。

抽出された部分文字列は通常サイズが小さく、寿命も短いです。ガベージコレクタはすぐにそれらを回収するつもりですし、そもそもヒープ上でそれほど場所を取っていません。つまり、メモリの大部分を再利用するような永続的な戦略をとることも、得策ではありません。ガベージコレクタが内部ポインタの処理に悩まされるようになり、遅くなるばかりです。

もし、文字列に対して通常行われる部分文字列操作がまったく異なるものであれば、永続的なアプローチを取ることは理にかなっていると言えるでしょう。もし、一般的に100万文字の文字列があり、何千もの重複する10万文字単位の部分文字列を抽出し、それらの部分文字列がヒープ上で長い間生きているとしたら、持続的部分文字列アプローチを採用することは完全に理にかなっていると言えるでしょう。しかし ほとんどのビジネスプログラマーは、そのようなことを漠然としたものでさえしません。 . DNA解析のプログラマーは、このような文字列の使用特性を持つ問題を毎日解決しなければなりませんが、あなたはそうではない可能性が高いです。DNA解析のプログラマーは、このような文字列の使用特性を持つ問題を毎日解決しなければなりません。 その を使用するシナリオがあります。

例えば、私のチームでは、C#やVBのコードを入力すると、その場で解析するプログラムを書いています。これらのコードファイルの一部は 巨大 そのため、部分文字列の抽出や文字の挿入・削除などの文字列操作をO(n)で行うわけにはいきません。私たちは、テキストバッファの編集を表現するための永続的で不変のデータ構造を構築し、既存の文字列データの大部分を迅速かつ効率的に再利用することを可能にしました。 と 既存の字句解析や構文解析が、典型的な編集の際に行われます。これは解決困難な問題で、その解決方法はC#とVBのコード編集という特殊な分野に特化したものであった。組み込みの文字列型にこの問題を解決することを期待するのは非現実的でしょう。