3

ハッシュ マップ内のすべてのセットから共通の値を取得する最速の方法は何でしょうか?

私は 

Map<String, Set<String>>

キーを確認し、指定されたキーを持つすべてのセットを取得します。しかし、ハッシュマップからすべてのセットを取得する代わりに、すべてのセットから共通の要素 (値) を取得するより良い方法はありますか?

たとえば、ハッシュマップには、

abc:[ax1,au2,au3]
def:[ax1,aj5]
ijk:[ax1,au2]

セットから最も一般的な値であるため、 ax1andのみを抽出したいと思います。au2

4

1 に答える 1

3

注: これが最速かどうかはわかりませんが、これはこれを行う 1 つの方法です。

最初に、マップ内のすべての値セットで発生する文字列の頻度を抽出する簡単なメソッドを記述します。簡単な実装を次に示します。

Map<String, Integer> getFrequencies(Map<String, Set<String>> map) {
    Map<String, Integer> frequencies = new HashMap<String, Integer>();
    for(String key : map.keySet()) {
        for(String element : map.get(key)) {
            int count;
            if(frequencies.containsKey(element)) {
                count = frequencies.get(element);
            } else {
                count = 1;
            }
            frequencies.put(element, count + 1);
        }
    }
    return new frequencies;
}

このメソッドは、次のように簡単に呼び出すことができます。Map<String, Integer> frequencies = getFrequencies(map)

次に、マップ内で最も「一般的な」要素を取得するには、 Comparator インターフェイスfrequenciesを使用してマップ内のエントリを並べ替えるだけです。SO には、まさにそれについて議論する優れたコミュニティ wiki があります: Sort a Map<Key, Value> by values (Java)。wiki には、この問題に対する興味深い解決策が複数含まれています。それらを調べると役立つ場合があります。

以下に示すように、単にクラスを実装して呼び出すことができFrequencyMapます。

クラスにComparator<String>インターフェイスを実装させ、したがって、int compare(String a, String b)マップの要素を値 Integers の昇順でソートさせるメソッドを実装させます。

3 番目に、別のメソッドを実装し、それを呼び出してgetCommon(int threshold)しきい値を渡します。より大きい頻度値を持つマップ内のすべてのエントリは、threshold「一般的」と見なすことができ、単純なリストとして返されます。

class FrequencyMap implements Comparator<String> {

    Map<String, Integer> map;
    public FrequencyMap(Map<String, Integer> map) {
        this.map = map;
    }

    public int compare(String a, String b) {
        if (map.get(a) >= map.get(b)) {
            return -1;
        } else {
            return 1;
        } // returning 0 would merge keys
    }

    public ArrayList<String> getCommon(int threshold) {
        ArrayList<String> common = new ArrayList<String>();
        for(String key : this.map.keySet()) {
            if(this.map.get(key) >= threshold) {
                common.add(key);
            }
        }
        return common;
    }

    @Override public String toString() {
        return this.map.toString();
    }
}

したがって、FrequencyMap クラスとgetCommonメソッドを使用すると、次の数行のコードに要約されます。

    FrequencyMap frequencyMap = new FrequencyMap(frequencies);
    System.out.println(frequencyMap.getCommon(2));
    System.out.println(frequencyMap.getCommon(3));
    System.out.println(frequencyMap.getCommon(4));

質問のサンプル入力の場合、これは取得する o/p です。

// common values
[ax1, au6, au3, au2]
[ax1, au2]
[ax1]

また、この質問のために作成したコードを含む要点は次のとおりです: https://gist.github.com/VijayKrishna/5973268

于 2013-07-11T07:24:48.097 に答える