あなたの実装には、特に非効率的なものはありません。私はあなたのハッシュ/ルックアップ戦略に実際に従っていないことを認めますが、あなたの状況でそれがパフォーマンスに優れていると言うなら、私はあなたを信じます.
私が期待する唯一の違いは、の値配列からキーを移動することですEntry。
これを持つ代わりに：
class Entry {
long[] values;
}
//...
if ( entry.values[key_index] == key ) { //...
これを試して：
class Entry {
long key;
long values[];
}
//...
if ( entry.key == key ) { //...
メンバーにアクセスして境界チェックを行い、配列の値を取得するというコストが発生する代わりに、メンバーにアクセスするだけのコストが発生するはずです。
配列より高速なランダム アクセス データ型はありますか?
この質問への回答が気になったので、テスト環境をセットアップしました。これは私の配列インターフェースです：
interface Array {
long get(int i);
void set(int i, long v);
}
この「配列」は、インデックスが範囲外の場合、未定義の動作をします。私は明白な実装をまとめました：
class NormalArray implements Array {
private long[] data;
public NormalArray(int size) {
data = new long[size];
}
@Override
public long get(int i) {
return data[i];
}
@Override
public void set(int i, long v) {
data[i] = v;
}
}
そして、コントロール:
class NoOpArray implements Array {
@Override
public long get(int i) {
return 0;
}
@Override
public void set(int i, long v) {
}
}
最後に、最初の 10 個のインデックスがハードコードされたメンバーである「配列」を設計しました。メンバーは、スイッチを介して設定/選択されます。
class TenArray implements Array {
private long v0;
private long v1;
private long v2;
private long v3;
private long v4;
private long v5;
private long v6;
private long v7;
private long v8;
private long v9;
private long[] extras;
public TenArray(int size) {
if (size > 10) {
extras = new long[size - 10];
}
}
@Override
public long get(final int i) {
switch (i) {
case 0:
return v0;
case 1:
return v1;
case 2:
return v2;
case 3:
return v3;
case 4:
return v4;
case 5:
return v5;
case 6:
return v6;
case 7:
return v7;
case 8:
return v8;
case 9:
return v9;
default:
return extras[i - 10];
}
}
@Override
public void set(final int i, final long v) {
switch (i) {
case 0:
v0 = v; break;
case 1:
v1 = v; break;
case 2:
v2 = v; break;
case 3:
v3 = v; break;
case 4:
v4 = v; break;
case 5:
v5 = v; break;
case 6:
v6 = v; break;
case 7:
v7 = v; break;
case 8:
v8 = v; break;
case 9:
v9 = v; break;
default:
extras[i - 10] = v;
}
}
}
このハーネスでテストしました：
import java.util.Random;
public class ArrayOptimization {
public static void main(String[] args) {
int size = 10;
long[] data = new long[size];
Random r = new Random();
for ( int i = 0; i < data.length; i++ ) {
data[i] = r.nextLong();
}
Array[] a = new Array[] {
new NoOpArray(),
new NormalArray(size),
new TenArray(size)
};
for (;;) {
for ( int i = 0; i < a.length; i++ ) {
testSet(a[i], data, 10000000);
testGet(a[i], data, 10000000);
}
}
}
private static void testGet(Array a, long[] data, int iterations) {
long nanos = System.nanoTime();
for ( int i = 0; i < iterations; i++ ) {
for ( int j = 0; j < data.length; j++ ) {
data[j] = a.get(j);
}
}
long stop = System.nanoTime();
System.out.printf("%s/get took %fms%n", a.getClass().getName(),
(stop - nanos) / 1000000.0);
}
private static void testSet(Array a, long[] data, int iterations) {
long nanos = System.nanoTime();
for ( int i = 0; i < iterations; i++ ) {
for ( int j = 0; j < data.length; j++ ) {
a.set(j, data[j]);
}
}
long stop = System.nanoTime();
System.out.printf("%s/set took %fms%n", a.getClass().getName(),
(stop - nanos) / 1000000.0);
}
}
結果はやや驚くべきものでした。TenArray は、NormalArray よりも非常に高速に実行されます (サイズが 10 以下の場合)。オーバーヘッドを (NoOpArray 平均を使用して) 差し引くと、TenArray は通常の配列の約 65% の時間を取っていることがわかります。したがって、配列の最大サイズがわかっている場合は、配列の速度を超える可能性があると思います。switch は、配列よりも境界チェックが少ないか、より効率的な境界チェックを使用していると思います。
NoOpArray/set took 953.272654ms
NoOpArray/get took 891.514622ms
NormalArray/set took 1235.694953ms
NormalArray/get took 1148.091061ms
TenArray/set took 1149.833109ms
TenArray/get took 1054.040459ms
NoOpArray/set took 948.458667ms
NoOpArray/get took 888.618223ms
NormalArray/set took 1232.554749ms
NormalArray/get took 1120.333771ms
TenArray/set took 1153.505578ms
TenArray/get took 1056.665337ms
NoOpArray/set took 955.812843ms
NoOpArray/get took 893.398847ms
NormalArray/set took 1237.358472ms
NormalArray/get took 1125.100537ms
TenArray/set took 1150.901231ms
TenArray/get took 1057.867936ms
実際に配列よりも高速にできるかどうかはわかりません。明らかにこの方法では、インターフェース/クラス/メソッドに関連するオーバーヘッドが発生します。