Javaでの文字列インデックス付きコレクション

Question

Javaを使用し、v1.6と仮定します。

ユニークなインデックスが文字列で、一意でない値がintであるコレクションがあります。 できるだけ早くこのコレクションに対して何千ものルックアップを実行する必要があります。

私は現在HashMap<String, Integer>を使用していますが、Integer to intのboxing/unboxingがこれをより遅くしていることが心配です。

私は、int[]と結合されたArrayList<String>を使用することを考えていました。

すなわち、代わりの：

int value = (int) HashMap<String, Integer>.get("key"); 

私は

int value = int[ArrayList<String>.indexOf("key")]; 

任意の考えを行うことができますか？これを行うより速い方法がありますか？

p.s.私はコレクションを一度しか作成せず、一度変更することがありますが、サイズがわかるたびにArrayListの代わりにString[]を使用しますが、indexOfを複製する方法がわかりません。

Answer 1

Unboxingは高速です - 割り当ては必要ありません。それはプールされたものを使用しない限り、新しいオブジェクトを割り当てる必要があるので、ボクシングは潜在的に遅いです。

本当に問題はありますか？これが重要なヒットであることが実際に証明されるまで、コードを複雑にしないでください。私は非常にそれが疑わしいです。

プリミティブ型で使用できるコレクションライブラリがありますが、プロファイリングして問題が発生することを確認するまで、JREの通常のHashMapに固執します。検索結果が,の場合は、まったく問題になるとは限りません。同様に、追加ベースではなくルックアップベースの場合（つまり、追加するより頻繁にフェッチする場合）、ボクシングコストは特に重要ではなく、安価であるだけです。

値をintに変換するキャストではなく、intValue()を使用することをお勧めします。これにより、何が起こっているのかが明確になります。

EDIT：コレクションは十分に大きい場合HashMap.get(key)がArrayList.indexOf(key)より速くなり、コメントで質問に答えるために。実際に5つのアイテムしか持っていない場合は、リストの方が速いかもしれません。私はそれが事実ではないと仮定します。

本当にボクシング/アンボクシングをしたくない場合は、Trove（TObjectHashMap）を試してみてください。考慮するCOLTもありますが、そこに正しいタイプが見つかりませんでした。

Answer 2

私は、 HashMapははるかに高速なルックアップを提供しますが、正しく答えるにはベンチマークが必要です。

EDIT：さらに、ボクシングは含まれていません。すでに格納されているオブジェクトのアンボックス化のみです。このステップでは、オブジェクトの割り当てが行われていないため、非常に高速です。だから、私はこれがあなたにもっと速いスピードを与えるとは思わないが、ベンチマークを実行するべきだ。

Answer 3

ここで少し問題があります。リストに要素を重複させることができます。 2番目の方法を実際にやりたければ、代わりにSetを使うことを検討してください。

あなたは2つのパフォーマンステストを行って、どちらかが他のものより高速かどうかを確認しましたか？

編集：もちろん、最も一般的なSet型（HashSet）自体はHashMapによってサポートされているので、セットへの切り替えはあまり賢明な変更ではないかもしれません。

Answer 4

私はあなたの "キー"の一致を見つけるためにあなたのArrayListをスキャンすることは、あなたのボクシング/ unboxing懸念よりもはるかに遅くなると思う。

Answer 5

List.indexOfは通常、リストO（n）のリニアスキャンを行います。バイナリ検索はO（log n）でジョブを実行します。ハッシュテーブルはO（1）でそれを行います。

メモリに多数のIntegerオブジェクトがあることが問題になる可能性があります。しかし、String（Stringとchar[]の両方）についても同じことが当てはまります。独自のカスタムDBスタイルの実装を行うこともできますが、最初にベンチマークを行うことをお勧めします。

Answer 6

box/unboxを使用しないことで得られるパフォーマンスの向上は、indexOfメソッドを使用する必要があるforループによって消去されることがあります。

ハッシュマップを使用します。また、（int）キャストは必要ありません。コンパイラがそれを処理します。

配列事が配列内のアイテムの数が少ない大丈夫だろうが、そのようにHashMapのは...

あなたはそれが速い配列でルックアップするために作る（このことができる唯一の方法ではない実際の提案はあまりにも多くの問題があるので）配列のインデックスとして動作するStringのhashCodeを使用する場合です - でも、それについて考えることはありません！ （私はあなたがそれについて語るgoogleを介して何かを見つけるかもしれないので、私はそれを言及するだけです...なぜ彼らがそれについて悪いことを説明していない場合はそれについてもう読んでいない！）

Answer 7

それは確かにボトルネック、私はPrimitive Collections for Javaを提案します;特に、ObjectKeyIntMapはあなたが望むもののように見えます。

Answer 8

地図を一度作成するだけで問題がなければ、perfect hashing（たとえばBob Jenkins' code）を調べるとよいでしょう。

Answer 9

ルックアップのマップ解除はunboxingを行いません。後で結果にアクセスすると遅くなります。

SimpleIntのように、intのゲッターを使って小さなラッパーを導入することをお勧めします。変換なしでintを保持します。コンストラクタは高価ではなく、全体として整数よりも安価です。

public SimpleInt 
{ 
    private final int data; 

    public SimpleInt(int i) 
    { 
     data = i; 
    } 

    // getter here 
    .... 
}