私は、メモリと、それほどではないが速度が重要であるアプリケーションを書いています。プロファイリングから、マップとセットの操作に多くの時間を費やしていることがわかりました。これらのメソッドをあまり呼び出さない方法を検討している間、アクセス時間やメモリのオーバーヘッドを大幅に改善する実装を作成した、または遭遇した人がいるかどうか疑問に思っています。または少なくとも、いくつかの仮定を考えると、それはこれらのことを改善することができますか？
JDKソースを見ると、これをより速くまたはよりスリムにすることができないとは信じられません。
Commons Collectionsを知っていますが、より高速またはよりスリムにすることを目的とした実装はないと思います。Googleコレクションについても同じです。
更新：スレッドセーフは必要ないことに注意してください。
通常、これらの方法は非常に迅速です。確認すべき点がいくつかあります: ハッシュ コードは実装されていますか? それらは十分に均一ですか？そうしないと、ゴミのパフォーマンスが得られます。
http://trove4j.sourceforge.net/ <-- これは少し速く、メモリを節約します。50,000 回の更新で数ミリ秒節約できました
マップ/セットを正しく使用していますか? つまり、すべての値または同様のものを反復しようとしないでください。また、たとえば、contains を実行してから remove を実行しないでください。削除を確認するだけです。
Double vs double を使用しているかどうかも確認してください。数万回のチェックで数ミリ秒のパフォーマンス向上に気付きました。
初期容量も正しく/適切に設定されていますか?
equals メソッドと hashCode メソッドのパフォーマンスを改善してみてください。これにより、オブジェクトの標準コンテナーの使用が高速化される可能性があります。
次の方法で、メモリを少し節約できます。
(a)より強力で幅の広いハッシュ コードを使用することで、キーを保存する必要がなくなります。
(b) 配列から自分自身を割り当て、ハッシュ テーブル エントリごとに個別のオブジェクトを作成しないようにする。
参考までに、 Numerical Recipiesハッシュ テーブルの飾り気のないJava 実装を以下に示します。CharSequence (文字列を含む) に直接キーを設定することもできますが、それ以外の場合は、オブジェクトに対して強力な 64 ビット ハッシュ関数を自分で作成する必要があります。
この実装ではキーが保存されないため、2 つのアイテムが同じハッシュ コードを持つ場合 (適切なハッシュ関数がある場合は、2^32 のオーダーまたは数十億のアイテムでハッシュした後に予想される)、次に、1 つのアイテムが他のアイテムを上書きします。
public class CompactMap<E> implements Serializable {
static final long serialVersionUID = 1L;
private static final int MAX_HASH_TABLE_SIZE = 1 << 24;
private static final int MAX_HASH_TABLE_SIZE_WITH_FILL_FACTOR = 1 << 20;
private static final long[] byteTable;
private static final long HSTART = 0xBB40E64DA205B064L;
private static final long HMULT = 7664345821815920749L;
static {
byteTable = new long[256];
long h = 0x544B2FBACAAF1684L;
for (int i = 0; i < 256; i++) {
for (int j = 0; j < 31; j++) {
h = (h >>> 7) ^ h;
h = (h << 11) ^ h;
h = (h >>> 10) ^ h;
}
byteTable[i] = h;
}
}
private int maxValues;
private int[] table;
private int[] nextPtrs;
private long[] hashValues;
private E[] elements;
private int nextHashValuePos;
private int hashMask;
private int size;
@SuppressWarnings("unchecked")
public CompactMap(int maxElements) {
int sz = 128;
int desiredTableSize = maxElements;
if (desiredTableSize < MAX_HASH_TABLE_SIZE_WITH_FILL_FACTOR) {
desiredTableSize = desiredTableSize * 4 / 3;
}
desiredTableSize = Math.min(desiredTableSize, MAX_HASH_TABLE_SIZE);
while (sz < desiredTableSize) {
sz <<= 1;
}
this.maxValues = maxElements;
this.table = new int[sz];
this.nextPtrs = new int[maxValues];
this.hashValues = new long[maxValues];
this.elements = (E[]) new Object[sz];
Arrays.fill(table, -1);
this.hashMask = sz-1;
}
public int size() {
return size;
}
public E put(CharSequence key, E val) {
return put(hash(key), val);
}
public E put(long hash, E val) {
int hc = (int) hash & hashMask;
int[] table = this.table;
int k = table[hc];
if (k != -1) {
int lastk;
do {
if (hashValues[k] == hash) {
E old = elements[k];
elements[k] = val;
return old;
}
lastk = k;
k = nextPtrs[k];
} while (k != -1);
k = nextHashValuePos++;
nextPtrs[lastk] = k;
} else {
k = nextHashValuePos++;
table[hc] = k;
}
if (k >= maxValues) {
throw new IllegalStateException("Hash table full (size " + size + ", k " + k);
}
hashValues[k] = hash;
nextPtrs[k] = -1;
elements[k] = val;
size++;
return null;
}
public E get(long hash) {
int hc = (int) hash & hashMask;
int[] table = this.table;
int k = table[hc];
if (k != -1) {
do {
if (hashValues[k] == hash) {
return elements[k];
}
k = nextPtrs[k];
} while (k != -1);
}
return null;
}
public E get(CharSequence hash) {
return get(hash(hash));
}
public static long hash(CharSequence cs) {
if (cs == null) return 1L;
long h = HSTART;
final long hmult = HMULT;
final long[] ht = byteTable;
for (int i = cs.length()-1; i >= 0; i--) {
char ch = cs.charAt(i);
h = (h * hmult) ^ ht[ch & 0xff];
h = (h * hmult) ^ ht[(ch >>> 8) & 0xff];
}
return h;
}
}
AbstractMap および/または AbstractSet を開始点として拡張できます。少し前にバイナリ トライ ベースのマップを実装するためにこれを行いました (キーは整数で、ツリーの各「レベル」はビット位置でした。左の子は 0 で、右の子は 1 でした)。キーは EUI-64 識別子であり、ほとんどの場合、上位 5 バイトは同じであるため、これはうまく機能しました。
AbstractMap を実装するには、少なくとも entrySet() メソッドを実装して、それぞれがキーと値のペアである Map.Entry のセットを返す必要があります。
セットを実装するには、AbstractSet を拡張し、size() と iterator() の実装を提供します。
しかし、それは少なくともです。get と put も実装する必要があります。これは、デフォルトのマップが変更不可能であり、get のデフォルトの実装が一致を探して entrySet を反復処理するためです。
いくつかのクラスをプロファイリングしたとおっしゃいましたが、それらの速度をチェックするためにタイミングを計ったことはありますか? メモリ使用量を確認する方法がわかりません。さまざまな実装を比較する場合は、具体的な数値を手元に用意しておくとよいようです。
私は数年前にこのようなことを経験しました - 非常に大きなマップとセット、そしてそれらの非常に多く。デフォルトの Java 実装は、あまりにも多くのスペースを消費していました。最後に、自分のコードで必要な実際の使用パターンを調べた後で、独自のロールを作成しました。たとえば、早い段階で作成された既知の大規模なオブジェクトのセットがあり、一部のマップはまばらで、他のマップは密集していました。他の構造は単調に (削除なしで) 成長しましたが、他の場所では、重複を避けるために時間とスペースを費やすよりも、「コレクション」を使用して、重複アイテムを処理するという時折ではあるが無害な余分な作業を行う方が高速でした。私が使用した実装の多くは配列ベースであり、ハッシュコードが順次割り当てられるという事実を利用していたため、密なマップの場合、ルックアップは単なる配列アクセスでした。
メッセージを奪う:
ああ、単体テストを書いて...
GNU Trove をチェックしてください:
commons -collections には、速度のために特別に構築された実装が少なくとも 1 つあります。
@thaggie のアドバイスに従って、equals/hashcode メソッドの時間を確認することで、より多くのマイレージを取得できると思われます。
Map 操作と Set 操作が CPU を高い割合で使用しているのを見たことがありますが、これは Map と Set を過剰に使用していることを示しており、データを再構築すると、上位 10% の CPU 消費者からのコレクションがほとんど排除されました。
コレクションのコピー、コレクションの繰り返し、およびコレクションのほとんどの要素にアクセスしてオブジェクトを作成するその他の操作を回避できるかどうかを確認してください。
ここにいくつかのメモといくつかの代替データ構造ライブラリへのリンクがあります: http://www.leepoint.net/notes-java/data/collections/ds-alternatives.html
また、fastutil に強い票を投じます。（別の回答とそのページで言及されています）スティックを振ることができるよりも多くの異なるデータ構造と、キーまたは値としてのプリミティブ型に最適化されたバージョンがあります。（欠点はjarファイルが巨大であることですが、おそらく必要なものだけにトリミングすることができます）
おそらく問題を引き起こしているのは、Mapまたはその背後にあるオブジェクトではありません。Set問題によっては、「オブジェクト」が Java オブジェクトではなくバイトの集まりとして格納される、よりデータベース型のスキームが必要になる場合があります。データベース (Apache Derby など) を埋め込むことも、独自の専門的なことを行うこともできます。それはあなたが実際に何をしているかに大きく依存しています。HashMap意図的に大きくて遅いわけではありません...
Commons Collections にはFastArrayList、FastHashMap、FastTreeMapがありますが、それらの価値がわかりません...
次のパッケージ (koloboke) を使用して int-int ハッシュマップを実行します。これはプロミティブ型をサポートし、2 つの int を long 変数に格納するためです。これは私にとってクールです。ころぼけ
[Joda Primities][1]トローブと同様に、プリミティブ コレクションがあります。Trove を試してみたところ、メモリ使用量がより優れていることがわかりました。