4

多くの文字列比較を行い、比較的少ない文字列操作を行い、別のテーブルを使用して文字列を識別子にマップし、効率的な等価性とメモリフットプリントの削減を実現する、文字列を多用するプログラムをいくつか見たことを思い出します。

public class Name {
    public static Map<String, Name> names = new SomeMap<String, Name>();
    public static Name from(String s) {
        Name n = names.get(s);
        if (n == null) {
            n = new Name(s);
            names.put(s, n);
        }
        return n;
    }
    private final String str;
    private Name(String str) { this.str = str; }
    @Override public String toString() { return str; }
    // equals() and hashCode() are not overridden!
}

これらのプログラムの 1 つが OpenJDK の javac であったことは確かなので、おもちゃのアプリケーションではありません。もちろん、実際のクラスはもっと複雑でした(また、CharSequence を実装していると思います)が、おわかりのように、プログラム全体Nameが予想されるあらゆる場所に散らばっていStringて、文字列操作が必要なまれなケースでは、変換されました。概念的には次のように、文字列に変換してから再度キャッシュしました。

Name newName = Name.from(name.toString().substring(5));

私はこれのポイントを理解していると思います-特に、周りに同じ文字列がたくさんあり、多くの比較がある場合-しかし、通常の文字列を使用してinternそれらを使用するだけでは同じことを達成できませんでしたか? ドキュメントにはString.intern()明示的に次のように記載されています。

...
intern メソッドが呼び出されたときに、equals(Object) メソッドによって決定されたこの String オブジェクトと等しい文字列がプールに既に含まれている場合、プールからの文字列が返されます。それ以外の場合は、この String オブジェクトがプールに追加され、この String オブジェクトへの参照が返されます。

したがって、任意の 2 つの文字列 s および t について、s.intern() == t.intern() は、s.equals(t) が true である場合にのみ true になります。
...

では、のようなクラスを手動で管理することと、 を使用することの利点と欠点は何Nameintern()ですか?

これまで考えたことは次のとおりです。

  • マップを手動で管理するということは、通常のヒープをintern()使用することを意味し、permgen を使用します。
  • マップを手動で管理する場合Name、インターンされた文字列とインターンされていない文字列が同じ型を共有しているため、ある場所でインターンを忘れる可能性があります。
  • に依存するintern()ということは、余分なクラスをコーディングせずに、既存の、最適化され、実証済みのメカニズムを再利用することを意味します。
  • マップを手動で管理すると、新しいユーザーにとってコードがより混乱し、厳格な操作がより面倒になります。

...しかし、ここで何か他のものが欠けているように感じます。

4

5 に答える 5

2

残念ながら、String.intern()単純な同期 HashMap よりも遅くなる可能性があります。それほど遅くする必要はありませんが、今日の Oracle の JDK では遅いです (おそらく JNI が原因です)。

考慮すべきもう 1 つの点は、パーサーを作成していることです。でいくつかの文字を収集char[]し、それらから文字列を作成する必要があります。文字列はおそらく共通で共有できるので、プールを使用したいと思います。

String.intern()そのようなプールを使用します。まだ検索するには、最初に String が必要です。だから私たちはnew String(char[],offset,length)最初にする必要があります。

に基づいて直接ルックアップを実行できるカスタム プールでは、そのオーバーヘッドを回避できますchar[],offset,length。たとえば、プールはtrieです。文字列はプールにある可能性が最も高いため、メモリを割り当てずに文字列を取得します。

独自のプールを作成したくないが、古き良き HashMap を使用する場合でも、ラップするキー オブジェクトchar[],offset,length(CharSequence など) を作成する必要があります。文字をコピーしないため、これは新しい文字列よりもまだ安価です。

于 2012-01-13T16:30:17.977 に答える
1

名前のようなクラスを手動で管理することと、intern() を使用することの利点と欠点は何ですか?

型チェックは主要な関心事ですが、不変の保存も重大な関心事です。

Nameコンストラクターに簡単なチェックを追加する

Name(String s) {
  if (!isValidName(s)) { throw new IllegalArgumentException(s); }
  ...
}

Name無効な名前に対応するインスタンスが存在しないことを保証できます* "12#blue,,"。これは、引数として s を取り、他のメソッドによって返された sNameを消費するメソッドは、無効なs がどこに忍び寄るかNameについて心配する必要がないことを意味します。Name

この議論を一般化するために、コードが無効な入力から保護するように設計された壁のある城であると想像してください。いくつかの入力を通過させたいので、通過する入力をチェックするガード付きのゲートを設置します。Nameコンストラクターはガードの一例です 。

Stringとの違いNameは、Strings をガードできないことです。境界の内外を問わず、悪意のあるコードでもナイーブなコードでも、任意の文字列値を作成できます。バグStringのある操作コードは、城内でのゾンビの発生に似ています。ゾンビは不変条件を通過する必要がないため、警備員は不変条件を保護できません。ゾンビはただ拡散し、データを破壊します。

値が "is a" であることは、値が "is a"Stringであることよりも少ない有用な不変条件を満たしますName

同じトピックを見る別の方法については、 stringly typedを参照してください。

Serializable* -コンストラクターのバイパスを許可する逆シリアル化に関する通常の警告。

于 2012-01-13T16:13:41.203 に答える
1

内部 String の文字列プール内で (おそらく線形の) 検索を行う必要があるintern() ため、私は常に Mapを使用します。これを頻繁に行うと、Map ほど効率的ではありません。Map は高速検索用に作成されています。

于 2012-01-13T16:14:52.097 に答える
1

Java 5.0 & 6 の String.intern() は、通常、最大サイズが小さい perm gen スペースを使用します。十分な空きヒープがある場合でも、スペースが不足している可能性があります。

Java 7 は通常のヒープを使用して、intern() された文字列を格納します。

文字列の比較は非常に高速であり、オーバーヘッドを考慮すると、比較時間を短縮することに大きな利点があるとは思いません。

これが行われるもう 1 つの理由は、重複する文字列が多数ある場合です。十分な重複がある場合、これにより多くのメモリを節約できます。

文字列をキャッシュするより簡単な方法は、LinkedHashMap のような LRU キャッシュを使用することです

private static final int MAX_SIZE = 10000;
private static final Map<String, String> STRING_CACHE = new LinkedHashMap<String, String>(MAX_SIZE*10/7, 0.70f, true) {
    @Override
    protected boolean removeEldestEntry(Map.Entry<String, String> eldest) {
        return size() > 10000;
    }
};

public static String intern(String s) {
    // s2 is a String equals to s, or null if its not there.
    String s2 = STRING_CACHE.get(s);
    if (s2 == null) {
        // put the string in the map if its not there already.
        s2 = s;
        STRING_CACHE.put(s2,s2);
    }
    return s2;
}

これがどのように機能するかの例です。

public static void main(String... args) {
    String lo = "lo";
    for (int i = 0; i < 10; i++) {
        String a = "hel" + lo + " " + (i & 1);
        String b = intern(a);
        System.out.println("String \"" + a + "\" has an id of "
                + Integer.toHexString(System.identityHashCode(a))
                + " after interning is has an id of "
                + Integer.toHexString(System.identityHashCode(b))
        );
    }
    System.out.println("The cache contains "+STRING_CACHE);
}

版画

String "hello 0" has an id of 237360be after interning is has an id of 237360be
String "hello 1" has an id of 5736ab79 after interning is has an id of 5736ab79
String "hello 0" has an id of 38b72ce1 after interning is has an id of 237360be
String "hello 1" has an id of 64a06824 after interning is has an id of 5736ab79
String "hello 0" has an id of 115d533d after interning is has an id of 237360be
String "hello 1" has an id of 603d2b3 after interning is has an id of 5736ab79
String "hello 0" has an id of 64fde8da after interning is has an id of 237360be
String "hello 1" has an id of 59c27402 after interning is has an id of 5736ab79
String "hello 0" has an id of 6d4e5d57 after interning is has an id of 237360be
String "hello 1" has an id of 2a36bb87 after interning is has an id of 5736ab79
The cache contains {hello 0=hello 0, hello 1=hello 1}

これにより、intern() された文字列のキャッシュの数が制限されます。

固定配列を使用すると、高速ではあるが効果的ではありません。

private static final int MAX_SIZE = 10191;
private static final String[] STRING_CACHE = new String[MAX_SIZE];

public static String intern(String s) {
    int hash = (s.hashCode() & 0x7FFFFFFF) % MAX_SIZE;
    String s2 = STRING_CACHE[hash];
    if (!s.equals(s2))
        STRING_CACHE[hash] = s2 = s;
    return s2;
}

上記のテストは、必要な場合を除いて同じように機能します

System.out.println("The cache contains "+ new HashSet<String>(Arrays.asList(STRING_CACHE)));

null空のエントリに対して次のインクルードを示す内容を出力します。

The cache contains [null, hello 1, hello 0]

このアプローチの利点は速度であり、ロックせずに複数のスレッドで安全に使用できることです。つまり、スレッドごとに STRING_CACHE のビューが異なっていてもかまいません。

于 2012-01-13T16:54:19.780 に答える
0

では、名前のようなクラスを手動で管理することと、intern() を使用することの利点と欠点は何ですか?

1 つの利点は次のとおりです。

したがって、任意の 2 つの文字列 s および t について、s.intern() == t.intern() は、s.equals(t) が true である場合にのみ true になります。

多くの小さな文字列を頻繁に比較しなければならないプログラムでは、これはうまくいくかもしれません。また、最終的にスペースを節約します。のような名前をAbstractSyntaxTreeNodeItemFactorySerializer頻繁に使用するソース プログラムを考えてみましょう。intern() を使用すると、この文字列は 1 回格納され、それだけです。他のすべてはそれを参照するだけですが、とにかくあなたが持っている参照です。

于 2012-01-13T16:20:31.280 に答える