1

Javaで2次元ハッシュマップを効率的に作成するための最良の方法はどれですか？私が話していることの例を示すために：私は集団的知性に関連するいくつかのアルゴリズムを開発しています。これらのアルゴリズムは、要素のペア間の相関を計算することによって機能します。

これらの値をキャッシュしないと、同じペアで複数回計算されるため、パフォーマンスが低下します。（アルゴリズムはO（n ^ 2）になる可能性がありますが、O（n ^ 3）になる可能性があるため、HashMapを使用して値を格納することを検討していました。複数回使用する。

このようなデータ構造をJavaで実装するための最も効率的な方法はどれですか？O（1）を使用して要素のペアによって生成された値をキャッシュして削除することは可能ですが、明示的なクラスを使用することはとにかく重すぎるようです。

Javaでは不十分であることが判明した場合は、C / C ++に切り替える必要があるため、これらの言語に関連するアイデアも歓迎します。

ありがとう

4

3 に答える 3

4

The easiest way to do this is to define a Pair class. It should be immutable (hash keys should not change), and hashCode() should be consistent with equals.

Something like (method implementations omitted):

public class Pair() {
  int a, b;

  public Pair(int a, int b);

  public int getA();

  public int getB();

  public boolean equals(Object obj);

  public int hashCode();
}

Notes:

  • If you don't want ints, sub in whatever type you want, or make your Pair class generic if you want it to be flexible.

  • It would be up to you whether (x, y) == (y,x).

With this in hand, you can have a HashMap<Pair, SomethingElse> as your cache.

于 2010-02-08T04:56:05.050 に答える
0

次のようなものを使用して両方のアイテムのハッシュコードを連結することにより、問題を部分的に解決しました。

private long computeKey(Object o1, Object o2)
{
    int h1 = o1.hashCode();
    int h2 = o2.hashCode();

    if (h1 < h2)
    {
        int swap = h1;
        h1 = h2;
        h2 = swap;
    }

    return ((long)h1) << 32 | h2;
}

HashMapアイテムの無駄でいっぱいになるのを避けるために、アルゴリズムがアイテムを必要としなくなったときにそれらを削除するために、指定された要素ですでにキャッシュされているすべての要素を保存する最も効率的な方法を理解する必要があります。これは、この種のアルゴリズムでは、反復ごとに2つのアイテムがマージされ、使用済みのアイテムから削除されますが、新しく生成されたアイテムが追加されるためです。

于 2010-02-11T05:12:33.727 に答える
0

Googleコレクションは双方向ハッシュマップをサポートしています。BiMapを参照してください。

（ところで、GoogleコレクションはApacheコレクションよりもマインドシェアを増やしているようです。）

更新：@danbenと@sateeshの説明に注意してください。xを指定してayを取得する必要がある場合、またはyを指定してxを取得する必要がある場合は、BiMapで十分です。しかし、本当に（x、y）ポイントを検索して、キャッシュされた情報を含む値を取得したいようです。その場合は、@danbenの提案に従ってください。

于 2010-02-08T04:32:57.927 に答える