4

私のプログラムでは、Map を 2 つのキー (整数) で使用したいと考えています。私の最初のアイデアは、整数を何らかの方法で文字列に結合することでした。

String key = k1.toString()+"-"+k2.toString();

この解決策は私には良くありませんでした：1）醜い。2) 遅い (数値をテキストとして扱う)。

ここで、stackoverflow で他のアプローチを発見しました。それらは、整数を 1 つのクラス (1 つの目的クラス (MyKey)、またはより一般的なクラス (Pair)) にカプセル化することに基づいていました。

いくつかの速度テストを実行しようとしましたが、私のダミー ソリューションが最速のようです。最初のショットの後、変換整数文字列を新しいクラス (MyString) にカプセル化し、このソリューションに対してもテストを実行しようとしました。

マップの定義は次のとおりです。

Map<Pair<Integer,Integer>,String> map1 = new HashMap<>();
Map<MyKey,String> map2 = new HashMap<>();
Map<String,String> map3 = new HashMap<>();
Map<MyString,String> map4 = new HashMap<>();

テスト結果は次のとおりです（複数回実行され、安定しているようです）：

  map: put+get=total
  1: 52+154=206
  2: 29+77=106
  3: 23+49=72
  3: 17+55=72

文字列を使用したソリューションは高速です。文字列キーの直接連結は、検索時は速く、入力時は遅くなります。

私の質問は次のとおりです。

1) String を使用したソリューションの方が速いのはなぜですか? (hashCode() の 1 回の呼び出し?)

2) String を使用したソリューションであってはならない理由はありますか?

追加情報：

マップ内のレコード数は約 6000 でした。

テストは、多くの存在しないキーの値も取得しようとしました。テスト結果が変わる可能性はありますか？

私のプログラムでは、M 値が true である boolean[N] の順列を生成します。一度、特定の N,M の結果を取得します。また必要になったときのために保管しておきたいと思います。

そして、これが私の例で使用されているクラスの完全なコードです:

  class Pair<L,R> {

    private final L left;
    private final R right;

    public Pair(L left, R right) {
      this.left = left;
      this.right = right;
    }

    public L getLeft() { return left; }
    public R getRight() { return right; }

    @Override
    public int hashCode() { return left.hashCode() ^ right.hashCode(); }

    @Override
    public boolean equals(Object o) {
      if (o == null) return false;
      if (!(o instanceof Pair)) return false;
      Pair pairo = (Pair) o;
      return this.left.equals(pairo.getLeft()) &&
             this.right.equals(pairo.getRight());
    }
  }

  class MyKey {
      public Integer k1;
      public Integer k2;

      public MyKey(Integer k1, Integer k2) {
          this.k1 = k1;
          this.k2 = k2;
      }

      @Override
      public int hashCode() {
          return k1.hashCode() + 17 * k2.hashCode();
      }

      @Override
      public boolean equals(Object o) {
          if (o == this) {
              return true;
          }
          if (o == null || !(o instanceof MyKey)) {
              return false;
          }
          MyKey cp = MyKey.class.cast(o);
          return k1.equals(cp.k1) && k2.equals(cp.k2);
      }
  }

  class MyString  {
      private String value;

      public MyString(Integer k1, Integer k2) {
          value=k1+"-"+k2;
      }

      @Override
      public int hashCode() {
          return value.hashCode();
      }

      @Override
      public boolean equals(Object o) {
          return o.equals(value);
      }
  }
4

3 に答える 3

5

これは、最もパフォーマンスの高いダブル整数キーである必要があります。

class MyKey {
  public final int k1, k2;
  MyKey(int k1, int k2) { this.k1 = k1; this.k2 = k2; }
  public int hashCode() { return k1 ^ k2; }
  public boolean equals(Object o) { 
    MyKey that;
    return o instanceof MyKey && (that = (MyKey)o).k1 == k1 && that.k2 == k2;
  }

テスト結果については、マイクロベンチマークに十分注意する必要があります。ウォーミングアップ、GC-ing、JITが存在しなくなってコンパイルできないコードを注意深く書くなどのすべての呪文を実行したと思いますか？そうでない場合は、車輪の再発明を行うのではなく、GoogleCaliperを強くお勧めします。

于 2012-11-25T20:16:29.263 に答える
1

あなたが抱えている最大の問題は、文字列の構築、またはルックアップを実行するためだけのオブジェクトの作成です。

これを回避する方法は、Map または Map 値を持つことです。キーはプリミティブであるため、trove ライブラリを使用することをお勧めします。TObjectIntHashMapとTIntIntHashMap

例えば

TObjectIntHashMap<TIntIntHashMap> map = ...
int val = map.get(k1).get(k2);

このアプローチを使用すると、キーまたは値を作成するためにオブジェクトは必要ありません。

キーをペアリングする場合は、次を使用できます

TLongIntHashMap map = ...
int val = map.get(((long) k1 << 32) | k2);

例えば

long key = ((long) k1 << 32) | k2;
map.adjustOrPut(key, 1, 1); // a counter for this key.
于 2012-11-25T21:00:34.647 に答える
0

2）文字列を使用したソリューションを使用すべきではない理由はありますか？

あなたが与えられたアプローチについて尋ねるならば：

String key = k1.toString()+"-"+k2.toString();

問題は：

k1 = "a-b"
k2 = "c"

と

k1 = "a"
k2 = "b-c"

（および同様の）

同じキーを持っています。

クラスの使用について質問する場合：

これを扱うクラスを持つことはよりクリーンです。その場合、クラスは呼び出し元ではなく実装に関心があるためです。つまり、「-」と「。」のどちらを使用するかを考える必要はありません。または「＃」など、現在正しいものを変更します。変更する場合は、クラス内で変更します。ソースコードの周りに散らばっているさまざまな場所ではありません。

ハッシュコードを実装するための正しいアプローチは、データによって異なります。Eclipseは、一般的な方法を提案しています。

@Override
public int hashCode() {
    final int prime = 31;
    int result = 1;
    result = prime * result + ((k1 == null) ? 0 : k1.hashCode());
    result = prime * result + ((k2 == null) ? 0 : k2.hashCode());
    return result;
}

それは私には大丈夫に見えます。

質問1はもう少し複雑です。入力データに大きく依存します。

一般的なアドバイス：パフォーマンスを気にする必要がない限り、パフォーマンスを気にしないでください。つまり、ソリューションが遅すぎる場合にのみ、ソリューションのプロファイリングを開始し、最も重要な部分を改善します。それ以外は、読みやすさと保守性が常に最初の目標です。

于 2012-11-25T20:18:44.410 に答える