3

ArrayListsキーが整数で、値がのキーと値のペアを保存したいと思いますStrings。

特定のコンテストでオンラインで問題を解決するためにコードを使用する必要があるため、データベースを使用できません。

少量のデータの場合、問題なくハッシュテーブルを操作できます。しかし、データが大きくなると、ヒープ サイズが不足します。コードだけをアップロードする必要があり、作業環境を提供できないため、ヒープサイズを変更できません。それが課題です。

4

6 に答える 6

3

  1. 文字列が頻繁に繰り返され、自然言語の頻度が高い場合は、同じ文字列に新しいオブジェクト インスタンスを使用しないでください。

    private Map<String, String> sharedStrings = new HashMap<>().

public void shareString(String s) {
    String t = sharedStrings.get(s);
    if (t == null) {
        t = s;
        sharedStrings.put(t, t);
    }
    return t;
}

  2. ストリングのナンバリングが遅すぎる可能性があります。

  3. 文字列のリストを 1 つにまとめて (セパレーターと制御文字)、おそらく文字列を Gzip 圧縮します (GZipOutputStream、GZipInputStream)。

  4. 十分な初期容量でハッシュ マップを調整します。（当たり前のことを言ってすみません。）

  5. huge large を使用して、すべての ArrayList を独自に割り当てますString[]。

    int count;
String[] allStrings = new String[999999];

Map<Integer, Long> map = new HashMap<>(9999);

void put(int key, List<String> strings) {
    int start = count;
    for (String s : strings) {
        allStrings[count] = s;
        ++count;
    }
    // high: start index, low: size
    long listDescriptor = (((long)start) << 32) | (count - start);
    map.put(key, listDescriptor);
}

  6. int や long などのプリミティブを使用したマップの実装があります。たとえば、troveライブラリ (自分では使用しませんでした)。

于 2013-08-12T12:12:33.670 に答える
1

の代わりに単純な配列を使用すると、ArrayList追加のメモリを節約できます (ただし、それほど多くはありません)。

検索パフォーマンスが優先されない場合は、 を使用しPair<Integer, List<>>て手動で検索を行うことができます。

整数の範囲が限られている場合は、配列をインスタンス化しList[integer_range]、配列インデックスをキーとして使用します。

を使用しているので、それらをStrings試してintern()、繰り返し値がないことを確認してください。

あなたが持っているデータに関する統計情報をお知らせください - キーは何か、値が繰り返されるかどうかなど。

于 2013-08-12T11:25:57.110 に答える
0

考えられる最適化の 1 つは、ArrayList が使用するストレージを最小限に抑える ArrayList.trimToSize です。

于 2013-08-12T11:54:42.570 に答える
-1

ヒープ サイズを増やすことができない場合は、ハッシュ テーブル (または使用するその他のデータ構造) のサイズを制限する必要があります。Apache LRUMapを試すことをお勧めします:

LRUマップ

最大サイズを持ち、最大サイズに達して新しいアイテムが追加されたときに、最近使用されていないアルゴリズムを使用してマップからアイテムを削除するマップの実装。

また、同期されたバージョンが本当に必要な場合は、それも利用できます。

Collections.synchronizedMap( theMapToSynchronize ) 複数のスレッドからアクセスされる場合は、この Map へのアクセスを同期する必要があります。同時 get(Object) 操作でさえ、不確定な動作を生成します。

また、LRU を使用してデータを失いたくない場合は、アルゴリズムを記述して、データ構造体にデータを保持し、ファイルなどの永続ストレージに保存する必要があります。

于 2013-08-12T11:08:08.933 に答える