.NET では文字列が不変なのに、なぜ Substring には O(n) 時間がかかるのでしょうか? 質問する

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

簡単に答えると、n が大きくならなければ O(n) は O(1) です。ほとんどの人は小さな文字列から小さな部分文字列を抽出するので、複雑さが漸近的にどのように増加するかはまったく関係ありません。

長い答えは次のとおりです。

インスタンスに対する操作で、少量のコピーまたは新規割り当て (通常は O(1) または O(lg n)) のみで元のメモリを再利用できるように構築された不変データ構造は、「永続的な」不変データ構造と呼ばれます。.NET の文字列は不変です。質問は基本的に、「なぜ永続的ではないのか」ということです。

なぜなら、.NET プログラムで文字列に対して通常実行される操作を見ると、まったく新しい文字列を作成する方が、あらゆる点でほとんど悪いことではないからです。複雑な永続的なデータ構造を構築するコストと困難さは、それ自体に見合うものではありません。

一般的に、人々は「部分文字列」を使用して、数百文字程度のやや長い文字列から、たとえば 10 文字または 20 文字程度の短い文字列を抽出します。コンマ区切りのファイルに 1 行のテキストがあり、3 番目のフィールドである姓を抽出したいとします。行の長さはおそらく数百文字で、名前は数十文字です。50 バイトの文字列割り当てとメモリ コピーは、最新のハードウェアでは驚くほど高速です。既存の文字列の中央へのポインタと長さで構成される新しいデータ構造を作成するのも驚くほど高速であるということは無関係です。「十分に高速」とは、定義上、十分に高速であるということです。

抽出された部分文字列は通常、サイズが小さく、存続期間も短いため、ガベージ コレクターがすぐに再利用します。また、そもそもヒープ上で多くの領域を占有していません。したがって、メモリの大部分の再利用を促す永続的な戦略を使用することも、良いことではありません。内部ポインターの処理に気を配る必要が生じたため、ガベージ コレクターの速度が遅くなるだけです。

文字列に対して通常行われる部分文字列操作がまったく異なる場合、永続的なアプローチを採用するのは理にかなっています。通常、数百万文字の文字列があり、数十万文字の範囲のサイズを持つ何千もの重複する部分文字列を抽出し、それらの部分文字列がヒープ上に長期間存在する場合、永続的な部分文字列アプローチを採用するのは完全に理にかなっています。そうしないのは無駄で愚かなことです。しかし、ほとんどの基幹業務プログラマーは、そのようなことを少しでも行いません。.NET は、ヒトゲノム プロジェクトのニーズに合わせて調整されたプラットフォームではありません。DNA 分析プログラマーは、毎日、これらの文字列の使用特性に関する問題を解決する必要があります。あなたがそうすることはない可能性が高いです。それを行う少数のプログラマーは、使用シナリオに厳密に一致する独自の永続データ構造を構築します。

たとえば、私のチームでは、C# および VB のコードを入力するとすぐにその場で分析するプログラムを作成しています。これらのコード ファイルの一部は膨大なため、O(n) の文字列操作を行って部分文字列を抽出したり、文字を挿入または削除したりすることはできません。私たちは、テキスト バッファーへの編集を表すための永続的で不変なデータ構造を多数構築しました。これにより、一般的な編集時に既存の文字列データの大部分と既存の語彙および構文の分析を迅速かつ効率的に再利用できます。これは解決が難しい問題であり、その解決策は C# および VB のコード編集の特定の領域に限定されていました。組み込みの文字列型でこの問題を解決できると期待するのは非現実的です。