21

少し前にストリングスとさまざまな言語について話し合っていたときに、ストリングスのインターンの話題が持ち上がりました。Java と .NET フレームワークは、すべての文字列といくつかのスクリプト言語でこれを自動的に行うようです。理論的には、同じ文字列の複数のコピーが作成されないため、メモリを節約できます。また、文字列の等価比較は、文字列の各文字を O(N) で実行するのではなく単純なポインター比較であるため、時間を節約できます。

しかし、考えれば考えるほど、そのコンセプトのメリットについて懐疑的になります。利点はほとんど理論的なものであるように私には思えます：

  • まず、自動文字列インターニングを使用するには、すべての文字列が不変である必要があります。これにより、多くの文字列処理タスクが必要以上に難しくなります。(そして、はい、一般的に不変性に関するすべての議論を聞いてきました。それは重要ではありません。)
  • 新しい文字列が作成されるたびに、少なくとも O(N) 操作である文字列インターニング テーブルに対してチェックする必要があります。(編集:ここで、N は文字列のサイズであり、テーブルのサイズではありません。これは人々を混乱させるためです。)したがって、新しい文字列の作成に対する文字列の等価性の比較の比率がかなり高くない限り、節約される正味の時間はそうではありません。正の値。
  • 文字列等価テーブルが強い参照を使用している場合、不要になった文字列はガベージ コレクションされないため、メモリが浪費されます。一方、テーブルが弱い参照を使用している場合、文字列クラスはテーブルから文字列を削除するために何らかのファイナライザーを必要とするため、GC プロセスが遅くなります。(文字列インターン テーブルの実装方法によっては、これは非常に重要な場合があります。最悪の場合、ハッシュ テーブルから項目を削除すると、特定の状況下でテーブル全体の O(N) 再構築が必要になる場合があります。)

これは、実装の詳細について考えた結果です。見逃したものはありますか？文字列のインターンは実際に一般的なケースで大きなメリットをもたらしますか?

編集 2: わかりました、どうやら私は間違った前提から操作していたようです。私が話していた人は、ストリングインターンが新しく作成されたストリングのオプションであることを指摘したことはなく、実際には逆であるという印象が強かった. 問題を解決してくれたジョンに感謝します。彼のために別の受け入れられた答え。

4

7 に答える 7

26

いいえ、Java と .NET は「すべての文字列を自動的に」処理しません。それら (Java と C#) は、バイトコード/IL で表現された定数String.intern文字列式を使用して、およびString.Intern(.NET) メソッドを介してオンデマンドで実行します。.NET での正確な状況は興味深いものですが、基本的に C# コンパイラは、アセンブリ内の等しい文字列定数へのすべての参照が、最終的に同じ文字列オブジェクトを参照することを保証します。これは、型の初期化時に効率的に実行でき、大量のメモリを節約できます。

新しい文字列が作成されるたびに発生するわけではありません。

(文字列の不変性の面では、文字列が不変であることを非常に嬉しく思います。パラメーターなどを受け取るたびにコピーを取得する必要はありません。どうもありがとうございます。文字列を作成するのを見たことがありません。タスクの処理が難しくなります...)

そして、他の人が指摘しているように、ハッシュの衝突で信じられないほど不運でない限り、ハッシュテーブルで文字列を検索することは一般的にO(n)操作ではありません...

個人的には、ユーザーランド コードで文字列インターンを使用しません。文字列の何らかのキャッシュが必要な場合は、HashSet<string>または同様のものを作成します。これは、同じ文字列 (XML 要素名など) に何度も遭遇することが予想されるさまざまな状況で役立ちますが、単純なコレクションではシステム全体のキャッシュを汚染しません。

于 2011-07-11T17:31:08.710 に答える
6

まず、自動文字列インターニングを使用するには、すべての文字列が不変である必要があります。これにより、多くの文字列処理タスクが必要以上に難しくなります。(そして、はい、一般的に不変性に関するすべての議論を聞いてきました。それは重要ではありません。)

これは真実であり、文字列は Java では不変です。これが悪いことかどうかはわかりません。イミュータブルとミュータブルの違いに立ち入らずに、これは素晴らしいデザインだと思います。キャッシングと非常にシンプルなため、ここでは説明しません。

新しい文字列が作成されるたびに、少なくとも O(N) 操作である文字列インターニング テーブルに対してチェックする必要があります。そのため、新しい文字列の作成に対する文字列の等価性の比較の比率がかなり高くない限り、節約された正味の時間が正の値になる可能性はほとんどありません。

正確には O(n) ではありません。これをほぼ一定のルックアップにするハッシュマップやその他のデータ構造を実行できます。

文字列等価テーブルが強い参照を使用している場合、不要になった文字列はガベージ コレクションされないため、メモリが浪費されます。一方、テーブルが弱い参照を使用している場合、文字列クラスはテーブルから文字列を削除するために何らかのファイナライザーを必要とするため、GC プロセスが遅くなります。(文字列インターン テーブルの実装方法によっては、これは非常に重要な場合があります。最悪の場合、ハッシュ テーブルから項目を削除すると、特定の状況下でテーブル全体の O(N) 再構築が必要になる場合があります。)

あなたはこれについて正しく、私はあなたに同意します。GC処理は無視できると感じることを除いて。長い目で見れば、ガベージ コレクターに余分なチェックをさせるよりもはるかに有益です。ハッシュテーブルから削除するための O(n) について何を意味するのかわかりません。ハッシュテーブルのほとんどの操作は O(1) です

要約すると、ほとんどの操作は線形であるというあなたの仮定だと思います。しかし、文字列を検索することは一定時間に近いです。したがって、このアプローチによるパフォーマンスの低下は無視できますが、メモリは大幅に増加します。私が主張したいのは、それだけの価値があるということです。

これは、実際に何が起こっているのか、そしてそれがどのようにメモリを節約するのかについての素晴らしい引用です。

メモリを節約する (および等しいかどうかのテストを高速化する) ために、Java は文字列の「interning」をサポートしています。String に対して intern() メソッドが呼び出されると、インターンされた String のテーブルに対してルックアップが実行されます。同じ内容の String オブジェクトが既にテーブルにある場合は、テーブル内の String への参照が返されます。それ以外の場合は、文字列がテーブルに追加され、それへの参照が返されます。

于 2011-07-11T17:30:14.773 に答える
3

これは、pythonドキュメントの見解です。

sys.intern(string)

「インターンされた」文字列のテーブルに文字列を入力し、インターンされた文字列 (文字列自体またはコピー) を返します。文字列のインターンは、ディクショナリ ルックアップのパフォーマンスを少し向上させるのに役立ちます。ディクショナリ内のキーがインターンされ、ルックアップ キーがインターンされる場合、(ハッシュ後の) キー比較は、文字列比較ではなくポインター比較によって実行できます。通常、Python プログラムで使用される名前は自動的にインターンされ、モジュール、クラス、またはインスタンスの属性を保持するために使用される辞書にはインターンされたキーがあります。

インターンされた文字列は不滅ではありません。それを利用するには、intern() の戻り値への参照を維持する必要があります。

于 2011-07-11T17:36:08.793 に答える
3

a. equals(b) は、ランダムな文字列に対して非常に高速です。長くて同じ（またはほぼ同じ）文字列の場合にのみ遅くなります

Random rand = new Random(1);
String[] list = new String[2000];
for(int i=0;i<list.length;i++)
    list[i] = "1234567"+Long.toString(rand.nextInt(36*37), 36); // semi random
int count = 0;
long start = System.nanoTime();
for(int i=0;i<list.length;i++)
    for(int j=0;j<list.length;j++)
        if (list[i].equals(list[j]))
            count++;
long time = System.nanoTime() - start;
System.out.printf("The average time for equals() was %,d ns.%n", time/list.length/list.length);

2.3 GHz のラップトップで

The average time for equals() was 19 ns.

最初の値をインターン()し、比較を行うために1つの値をインターン()する必要がある場合

       if (list[i] == list[j].intern())

版画

The average time for equals() was 258 ns.

これは、インターンされていることがわかっている 1 つの値と、入力されていてインターンされていない 2 番目の値があることが多いため、一般的なケースです。

インターンされた文字列と == のみを使用し、コストをカウントしない場合は、出力されます

The average time for equals() was 4 ns.

何百万もの比較を行う場合、これは何倍も高速です。ただし、少数の比較では、8 ns 節約できますが、250 ns 以上のコストがかかる可能性があります。

intern() を避けて equals() を使用する方が簡単かもしれません。

于 2011-07-11T18:14:32.493 に答える
0

文字列インターニングは、文字列 (1) を有限集合 (2) から何度も比較する必要がある場合に便利です。

==次に、文字列をインターンするオーバーヘッドは、代わりに高速化できるという利点が勝りequals()ます。

これを行うと、 and呼び出しHashMapに依存するを使用するよりも高速になる場合があります。hashCode()equals()

于 2015-04-25T11:56:01.523 に答える
0

あなたがリストしたポイントはすべて、ある程度有効です。しかし、重要な反論があります。

  1. 特にハッシュ マップを使用している場合、不変性は非常に重要であり、頻繁に使用されます。
  2. とにかく、文字を含む配列を常に再割り当てする必要があるため、文字列合成操作は非常に遅くなります。
  3. 一方、subString()操作は非常に高速です。
  4. 文字列の等価性は確かに多く使用されており、そこで何も失うことはありません。その理由は、文字列が自動的にインターンされないためです。実際、Java では、参照が異なる場合、equals()文字ごとの比較にフォールバックします。
  5. 明らかに、インターン テーブルに強い参照を使用することはお勧めできません。GC のオーバーヘッドに対処する必要があります。
  6. Java 文字列処理は、特に定数文字列と部分文字列の操作において、スペース効率が高くなるように設計されています。

バランスを考えると、ほとんどの場合に価値があり、VM が管理するヒープの概念にうまく適合します。ただし、それが本当に苦痛になる可能性のある特別なシナリオをいくつか想像することはできました。

于 2011-07-11T17:42:49.823 に答える
0

文字列のインターンは実際に一般的なケースで大きなメリットをもたらしますか?

はい。それは巨大です。Javaで試してみてください。

インターンの有無にかかわらず、1,000 個の半ランダム文字列が等しいかどうかを比較する簡単なテストを作成します。 

a.equals( b )  is slow

a == b is fast.
于 2011-07-11T17:46:21.373 に答える