2

class のオブジェクトがたくさんありますPuzzle。と をオーバーライドequals()しhashCode()ました。ユーザーに解決策を提示するときが来たら、(私が定義した基準によって) "類似" しているすべてのパズルを除外して、ユーザーにはそれぞれのパズルが 1 つだけ表示されるようにします。

類似度は推移的です。

例：

Result of computations:
A    (similar to A)
B    (similar to C)
C
D

この場合、A または D および B または C のみがユーザーに表示されますが、2 つの類似したパズルは表示されません。2 つの類似したパズルは、同じように有効です。両方がユーザーに表示されないことだけが重要です。

これを実現するために、重複を禁止する ADT を使用したいと考えました。ただし、代わりに類似性に関する値を返すようにequals()andメソッドを変更したくありません。この場合に使用できるのようなものhashCode()はありますか? または、これを行うべき別の方法はありますか？EqualatorComparator

私が取り組んでいるクラスは、文字のグリッドを維持するパズルです。(スクラブルのように。) パズルに同じ単語が含まれていても、方向が異なる場合、類似していると見なされます。したがって、パズルを解くには次のようにします。

                                    (2, 2): A           
                                    (2, 1): C           
                                    (2, 0): T

次のようになります。

                    (1, 2): A           
                    (1, 1): C           
                    (1, 0): T
4

5 に答える 5

2

equalsそれに応じてオーバーライドするラッパークラスを使用しますhashCode。

private static class Wrapper {
    public static final Puzzle puzzle;
    public Wrapper(Puzzle puzzle) { 
        this.puzzle = puzzle; 
    }
    @Override 
    public boolean equals(Object object) {
        // ...
    }
    @Override 
    public int hashCode() {
        // ...
    }
}

そして、すべてのパズルを包み、それらをマップに入れ、再び取り出します...

public Collection<Collection<Puzzle>> method(Collection<Puzzles> puzzles) {
    Map<Wrapper,<Collection<Puzzle>> map = new HashMap<Wrapper,<Collection<Puzzle>>();
    for (Puzzle each: puzzles) {
        Wrapper wrapper = new Wrapper(each);
        Collection<Puzzle> coll = map.get(wrapper);
        if (coll == null) map.put(wrapper, coll = new ArrayList<Puzzle>());
        coll.add(puzzle);
    }
    return map.values();
}
于 2010-01-01T05:20:25.227 に答える
2

オブジェクト間の類似性を測定する方法がわかりました。つまり、それらはMetric Spaceを形成します。

問題は、あなたの空間も通常の 3 次元空間のようなユークリッド空間か、それとも整数か、そのようなものかということです。もしそうなら、あなたが持っているどんなに多くの次元でも バイナリスペースパーティションを使うことができます.

(問題は、基本的に、オブジェクトと n 次元の実数ベクトルとの間に準同型性があるかということです。そうであれば、n 次元空間内の点の近さを測定する手法を使用できます。)

ユークリッド空間でない場合は、より大きな問題が発生します。プログラマーが最もよく知っている非ユークリッド空間の例は、文字列間のレーベンシュタイン距離です。

あなたの問題が、文字列が既存の文字列のリストにどれほど似ているかを確認することに似ている場合、O(n 2 ) 時間なしでそれを行うアルゴリズムを知りません。多分そこにいくつかあります。

しかし、もう 1 つの重要な質問は次のとおりです。時間はどれくらいありますか。オブジェクトの数は？時間がある場合、またはデータ セットが十分に小さくて O(n 2 ) アルゴリズムが実用的である場合は、オブジェクトのリストを繰り返し処理して、特定のしきい値を下回っているかどうかを確認するだけです。もしそうなら、それを拒否してください。

AbstractCollectionをオーバーロードし、Add 関数を置き換えるだけです。ArrayList などを使用します。あなたのコードは次のようになります

class SimilarityRejector<T> extends AbstractCollection<T>{
     ArrayList<T> base;
     double threshold;

    public SimilarityRejector(double threshold){
        base = new ArrayList<T>();
        this.threshold = threshold;
    }

    public void add(T t){
       boolean failed = false;
       for(T compare : base){
          if(similarityComparison(t,compare) < threshold) faled = true;
       }
       if(!failed) base.add(t);
     }

    public Iterator<T> iterator() {
        return base.iterator();
    }

    public int size() {
        return base.size();
    }
}

など。明らかに、T は、比較を実行できるクラスのサブクラスである必要があります。ユークリッド メトリックがある場合は、他のすべての項目を通過するのではなく、スペース パーティションを使用できます。

于 2010-01-01T05:21:13.593 に答える
2
  1. Comparator を使用して TreeSet を作成する
  2. すべての要素をセットに追加します
  3. すべての重複が取り除かれます
于 2010-04-30T20:56:33.857 に答える
0

私見、最もエレガントな方法はGili（カスタムコンパレータを備えたTreeSet）によって説明されました。

しかし、自分で作るのが好きなら、この最も簡単で明確な解決策のようです：

/**
 * Distinct input list values (cuts duplications)
 * @param items items to process
 * @param comparator comparator to recognize equal items
 * @return new collection with unique values
 */
public static <T> Collection<T> distinctItems(List<T> items, Comparator<T> comparator) {
    List<T> result = new ArrayList<>();

    for (int i = 0; i < items.size(); i++) {
        T item = items.get(i);

        boolean exists = false;
        for (int j = 0; j < result.size(); j++) {
            if (comparator.compare(result.get(j), item) == 0) {
                exists = true;
                break;
            }
        }

        if (!exists) {
            result.add(item);
        }
    }

    return result;
}
于 2014-07-30T17:14:53.177 に答える
0

通常、「類似性」は推移的な関係ではありません。したがって、最初のステップは、これを類似性ではなく同等性の観点から考えることです。同等性は再帰的、対称的、推移的です。

ここでの簡単なアプローチは、問題の等価関係に従って equals() メソッドと hashCode() メソッドが実装されているパズル ラッパーを定義することです。

それができたら、ラップされたオブジェクトを java.util.Set にドロップすると、重複が除外されます。

于 2010-04-30T21:14:46.920 に答える