問題タブ [string-interning]

何文字をs1 is s2与える必要がありFalseますか？制限はどこにありますか？つまり、Pythonが文字列の個別のコピーを作成し始めるまでに、文字列の長さを尋ねています。

intern()Java にあるような C または C++ のメソッドのようなものはありますか? そうでない場合、C または C++ で文字列インターンを実行するにはどうすればよいですか?

わかりました、この質問はこの質問の延長です

Java Strings: "String s = new String("silly");"

上記の質問はこれと同じ質問をしましたが、私は新たな疑問点があります。

Effective Javaおよび上記の質問の回答によると、不要なオブジェクトが作成されるため、行うべきではありません。String s = new String("a new string");

Javaは自動文字列インターニングを行っていると思うので、この結論についてはよくわかりません。つまり、文字列の場合、メモリにはそのコピーが1つしかありません。

それでは見てみましょうString s = new String("a new string");。

"a new string"は既にメモリ内に作成された文字列です。

私がするときString s = new String("a new string");、それsも"a new string"です。によるとautomatic string interning、sは の同じメモリ アドレスを指す必要があります"a new string"ね。

では、不要なオブジェクトを作成しているとどのように言えますか?

不変オブジェクトを含むいくつかの状況では、意味的に同一である多くの別個のオブジェクトが存在する可能性があります。簡単な例は、ファイルから文字列にテキストの多くの行を読み取ることです。プログラムの観点からは、2行が同じ文字シーケンスを持っているという事実は「一致」ですが、プログラマーの観点からは、大量の重複が予想される場合があります。多くの文字列インスタンスが同一である場合、それらの個別のインスタンスへの参照を単一のインスタンスへの参照に変更すると、メモリが節約され、それらの間の比較も容易になります（2つの文字列参照が同じ文字列を指している場合、文字を入力する必要はありません-それらが同一であることを決定するための文字ごとの比較）。

一部のシナリオでは、システムが提供する文字列インターン機能が役立つ場合があります。ただし、いくつかの厳しい制限があります。

1. 文字列がインターンされると、そのインターンされたコピーは、その文字列への他の参照が存在するかどうかに関係なく、永久に存続します。
2. 文字列インターン機能は文字列でのみ機能し、他の不変のタイプでは使用できません。

trueが存在する場合WeakDictionary<ImmutableClassType, ImmutableClassType>（各要素について、キーと値は同一になります）、コードは次のようになります。

残念ながら、私はWeakDictionary<keyType, valType>.netに組み込まれているクラスを知りません。さらに、両方の参照が常に同じものを指している場合、各アイテムのキーと値の弱参照を生成するのは無駄に思えます。

についていくつか読んだConditionalWeakTableことがありますが、それは興味深いクラスのように聞こえますが、目的は1つのインスタンスを取得して、意味的に同等の別の独立したインスタンスを見つけることができるため、ここでは使用できないと思います。

クラスのインスタンスの有効期間が明確に定義されている状況では、従来の方法を使用してDictionary同一のインスタンスをマージするのが妥当な場合があります。Dictionaryただし、多くの場合、そのようなものをいつ放棄するか、またはその中のアイテムをクリーンアップする必要があるかを知るのは難しい場合があります。ベースのWeakReferenceインターンコレクションは、そのような問題を回避します。そのようなものは存在しますか、それとも簡単に実装できますか？

補遺 svickが指摘したように、ライブでターゲットの値を返し、デッドでその値を返し続けるをDictionary<WeakReference, WeakReference>定義する実用的な方法がないため、aはやや問題があります。整数のターゲットハッシュコード値（コンストラクターで設定）を含み、その整数を返す構造体を定義できます。わずかな改善は、を使用して、削除のためにテーブルアイテムをキューに入れるために使用できるファイナライズ可能なオブジェクトにターゲットをリンクすることです。IEqualityComparerWeakReferenceGetHashCodeGetHashCodeConditionalWeakTableWeakReference

辞書を熱心にクリーンアップしようとすることと、やや受動的なアプローチを取ること（たとえば、最後のスイープ以降に少なくとも1つのGCがあった場合にアイテムを追加するときにスイープを実行することと、最後のスイープ以降に追加されたアイテムの数が、それを生き残ったアイテムの数を超えています）。辞書内のすべてをスイープすることは無料ではありませんが、ConditionalWeakTableもおそらく無料ではありません。

PPS 私が考えていた別の概念ですが、弱いインターンのアプローチほど有用ではなく、論理的に不変の型に可変の「タイムスタンプ」値​​を保持させ、によるその引数ref。2つの異なるインスタンスが等しいことが判明した場合、それらのタイムスタンプ値が調べられます。両方がゼロの場合、グローバルカウンター（-1、-2、-3など）から連続した負の数が割り当てられます。低いタイムスタンプ値を持っていた（または割り当てられた）パラメータは、他のパラメータに置き換えられます。

このようなアプローチを使用すると、多くのオブジェクトインスタンスが繰り返し比較された場合、参照の多くが「古い」インスタンスへの参照に置き換えられます。使用パターンによっては、これにより、インターンディクショナリを使用せずに、ほとんどの同一のオブジェクトインスタンスがマージされる場合があります。ただし、ネストされたオブジェクトにこのようなアプローチを適用するには、「不変」オブジェクトを使用して、ネストされたオブジェクトの参照を変更して、他のおそらく同一のネストされたオブジェクトを指すようにする必要があります。「おそらく同一の」オブジェクトが常にそうである場合、これは問題ないはずですが、そうでない場合、かなり奇妙な誤動作を引き起こす可能性があります。

Java のデフォルトの文字列インターンには多くの悪評が寄せられているため、代替手段を探しています。

Java 文字列のインターンに代わる優れた API を提案できますか? 私のアプリケーションは Java 6 を使用しています。私の要件は、主にインターンによる文字列の重複を避けることです。

悪い報道について：

• 文字列インターンは、ネイティブ メソッドを介して実装されます。また、C の実装では、1k エントリの固定サイズを使用し、多数の文字列のスケーリングが非常に不十分です。
• Java 6 はインターンされた文字列を Perm gen に格納します。したがって、GC されず、perm gen エラーにつながる可能性があります。これは Java 7 で修正されていることはわかっていますが、Java 7 にアップグレードできません。

なぜインターリングを使用する必要があるのですか?

• 私のアプリケーションは、さまざまな展開でヒープ サイズが 10 ～ 20G のサーバー アプリです。
• プロファイリング中に、数十万の文字列が重複していることがわかりました。重複した文字列を保存しないようにすることで、メモリ使用量を大幅に改善できます。
• メモリは私たちにとってボトルネックであったため、時期尚早の最適化を行うのではなく、メモリをターゲットにしています。

私の目標は、ストリングインターニングを行うことです。このために、次のことができるハッシュ化されたコンテナー クラスを探しています。

• ノードごとに 1 つのメモリ ブロックのみを割り当てる
• ノードごとに異なるユーザーデータ サイズ

値の型は次のようになります。

すべての String オブジェクトのサイズは異なります。これは、演算子 new + 配置 new で実現されます。したがって、基本的にはノードを自分で割り当てて、後でコンテナーにプッシュしたいと考えています。

以下の容器は適していません:

• std::unordored_set

• ブースト::マルチインデックス::*

  異なるサイズのノードを割り当てることはできません

• boost::intrusive::unordered_set

  最初はうまくいくようです。しかし、いくつかの欠点があります。まず、バケット配列を割り当て、負荷係数を自分で維持する必要があります。これは単に不必要であり、エラーが発生しやすいものです。

  しかし、もう 1 つの問題は解決が困難です。文字列型のオブジェクトしか検索できません。しかし、エントリを探すたびに文字列を割り当てるのは非効率的で、入力として std::string しかありません。

このタスクに使用できるハッシュ化されたコンテナーは他にありますか?

質問はこのコードに要約されます：

Java標準はとの値について何らかの保証を与えますか？もちろん、Java仕様の関連部分へのリンクは素晴らしいでしょう。case1case2

はい、SOが見つけたすべての「類似の質問」を調べましたが、この方法で質問に答えたものは見つからなかったため、重複は見つかりませんでした。equalsいいえ、これは、で置き換えることによって文字列比較を「最適化」するという誤った考えに関するものではありません==。

この質問は実際には実際には使用されませんが、Pythonが文字列インターンをどのように行うかについて興味があります。私は次のことに気づきました。

これは私が期待した通りです。

これを行うこともできます。

そして、それはかなり賢いです！

しかし、これを行うことはできません。

なぜPythonは評価せずs1+"g"、それが同じであることに気づきs2、同じアドレスを指すのでしょうか？その最後のブロックで実際に何が起こっているのFalseでしょうか？

NoStringInterningのデモンストレーションに問題があります

.NET CLR 2、3、4を試してみました。出力として、取得するのはTrueの束だけです。私はたくさんのFalseを期待しています！

先日、いくつかの Java コードを逆コンパイルしたところ、次のことがわかりました。

明らかに「==」を使用して文字列が等しいかどうかをテストするのは悪いことです

しかし、私は疑問に思いました-このコードはコンパイルおよび逆コンパイルされています。すべての文字列がコンパイル時に定義され、インターンされ、コードがコンパイルされた場合、s1.equals(s2) が最適化されて「s1 == s2」になる可能性はありますか?