文字列統合 - 百科事典

コンピュータサイエンスにおいて、ストリング・インタニアは、それぞれのユニークな文字列値に対して、一つのコピーのみを保存する方法です。この文字列は不変でなければなりません。ストリング・インタニアにより、文字列処理のタスクがより時間効率よくまたはスペース効率よく行えることがありますが、その代わりに、文字列が作成されたりインタニアされたりする際にさらに時間を要するようになります。ユニークな値は、ストリング・インタニア・プールに保存されます。

各文字列の単一のコピーコンスタントはそのインタニアと呼ばれ、通常は文字列クラスのメソッドで検索されます。例えば、JavaのString.intern()です。Javaのすべてのコンパイル時定数文字列は、このメソッドを使用して自動的にインタニアされます。

ストリング・インタニアは、Java、Python、PHP（バージョン5.4以降）、Lua、.NET言語など、いくつかの現代のオブジェクト指向プログラミング言語でサポートされています。Lisp、Scheme、Julia、Ruby、Smalltalkは、基本的にインタニアされた文字列のシンボルタイプを持つ言語に属します。ニュージャージー標準MLのライブラリには、同じことを行うアトムタイプがあります。Objective-Cのセレクタは、主にメソッド名として使用され、インタニアされた文字列です。

文字列以外のオブジェクトもインタニアできます。例えば、Javaでは、プリミティブ値がワラッパーオブジェクトにボックス化された場合、特定の値（どのブール型、どのバイト型、0から127までのどのチャータ型、および-128から127までのどのショート型またはインテジャ型）がインタニアされ、これらの値のどれか一つに対するボックス化変換の2つの異なる実行は、同じオブジェクトに結果するようになっています。

歴史
Lispは、そのシンボルに対するインタニアされた文字列の概念を導入しました。歴史的に、ストリング・インタニア・プールとして使用されるデータ構造は、リンクリストとして実装された場合「oblist」と呼ばれ、配列として実装された場合「obarray」と呼ばれます。

現代のLispの方言は、典型的にシンボルと文字列を区別します；特定の文字列をインタニアすると、既存のシンボルが返され、または新しいシンボルが作成され、その名前がその文字列になります。シンボルには、文字列にない追加のプロパティがあります。例えば、関連する値のストレージやネームスペースです。この区別は、意図せずインタニアされた文字列とインタニアされていない文字列を比較することを防ぐのに役立ちます。

力強さ
ストリング・インタニアは、文字列比較を高速化し、文字列キーを使用してオブジェクトの属性やメソッドを取得するように依存するアプリケーション（コンパイラや動的プログラミング言語の実行環境など）でのパフォーマンスのボトルネックとなる場合があります。インタニアをしない場合、2つの異なる文字列を比較するには、両方の文字列の全ての文字を調べる必要があります。これは以下の理由で遅いです：文字列の長さに対して本質的にO(n)であり、通常は複数のメモリ領域からの読み取りが必要で、それが時間を要します；さらに、読み取りはプロセッサキャッシュを埋め尽くし、他のニーズに対してキャッシュが不足することになります。インタニアされた文字列では、元のインタニア操作の後、シンプルなオブジェクトの同一性テストのみで十分です；これは通常、ポインタの同一性テストとして実装され、通常はメモリ参照なしで単一のマシン命令です。

多くの同じ文字列値のインスタンスがある場合、ストリング・インタニアはメモリ使用量も減少させます。例えば、ネットワークやストレージから読み込まれる場合があります。これらの文字列にはマジックナンバーやネットワークプロトコル情報が含まれることがあります。例えば、XMLパーサーはタグ名や属性名をメモリを節約するためにインタニアします。Java RMIシリアライゼーションオブジェクトストリーム上でのオブジェクトのネットワーク転送では、シリアライゼーション時に重複するオブジェクトの代わりにStringオブジェクトのハンドルを使用するため、インタニアされた文字列をより効率的に転送できます。

問題


= マルチスレッド =
インタニアされた文字列が不変でない場合、マルチスレッドと組み合わせた際に問題が発生する可能性があります。多くのシステムでは、インタニアされた文字列はアドレス空間内のすべてのスレッド（またはポインタを共有する可能性のあるすべてのコンテキスト）に対してグローバルでなければなりません。したがって、インタニア・プールはグローバルリソースであり、安全な並行アクセスのために同期される必要があります。これは、インタニア・プールの変更が必要な場合（インタニア・プールが確認され、必要に応じて変更される場合）の文字列の作成に影響を与えます。このオプティマイズが安全であるプラットフォームでは、ダブルチェックロッキングが使用できますが、インタニア・プールの変更に対する互換排他の必要性はコストがかかることがあります。

ストリング空間を複数のプールに分断して、それぞれを独立して同期することで、競合を減少させることもできます。


= 未使用のインタニアされた文字列のリカバリ =
インタニアされた文字列の多くの実装では、使用されていない文字列のリカバリ（手動または他の方法で）を試みていません。インタニアされた文字列の数が少ないまたは固定されている、または短期間で終了するアプリケーションでは、システムリソースの損失は許容できるかもしれません。しかし、ランタイムで大量のインタニアされた文字列が作成される長期間のシステムでは、未使用のインタニアされた文字列をリカバリする必要が発生することがあります。このタスクはガベージコレクタによって処理できますが、これは正しく機能するためにストリング・インタニアに対する弱い参照がインタニア・プールに保存される必要があります。


参考情報
Flyweightパターン


参考文献



外部リンク
Visual J# Stringクラス
.NET Stringクラス
Guava Javaライブラリ - Interner - Non-permgen String.internおよび他の不変型の弱いおよび強い参照実装
Javaのintern()メソッドの理解