0

このコードは、5,600 個のオブジェクトのセットに対して実行に 9 分かかります。

public Set<UnDirectedPair<T>> getAllUndirectedPairs(Set<T> setObjects) {
    Set<T> setObjectsProcessed = new TreeSet();
    Set<UnDirectedPair<T>> setPairs;
    setPairs = new TreeSet();
    Iterator<T> setObjectsIteratorA = setObjects.iterator();
    Iterator<T> setObjectsIteratorB;
    T currTA;
    T currTB;
    while (setObjectsIteratorA.hasNext()) {
        currTA = setObjectsIteratorA.next();
        setObjectsProcessed.add(currTA);
        setObjectsIteratorB = setObjects.iterator();
        while (setObjectsIteratorB.hasNext()) {
            currTB = setObjectsIteratorB.next();
            if (!setObjectsProcessed.contains(currTB) && !currTA.equals(currTB)) {
                setPairs.add(new UnDirectedPair(currTA, currTB));
            }
        }
        setObjectsProcessed.add(currTA);
    }
    return setPairs;

}

実行時間を劇的に短縮する方法をお探しですか...アイデアですか?

[背景] セットには人物が含まれています。セット内に重複があります (同一人物ですが、入力時のエラーにより属性がわずかに異なります)。私は 2 人を取り、必要な修正を行うメソッドを持っています。したがって、準備段階として、これらのメソッドに供給される (Person, Person) のペアのセットを作成する必要があります。

4

3 に答える 3

1

私が提案する 1 つのトリックは、外側ループと内側ループの両方のカウンターを維持することです。

int outerCount=0;
while (setObjectsIteratorA.hasNext()) {
    currTA = setObjectsIteratorA.next();
    setObjectsProcessed.add(currTA);
    setObjectsIteratorB = setObjects.iterator();
    int innerCount=0;
    while (setObjectsIteratorB.hasNext()) {
        currTB = setObjectsIteratorB.next();
        if (innerCount++>outerCount && !currTA.equals(currTB)) {
            setPairs.add(new UnDirectedPair(currTA, currTB));
        }
    }
 outerCount++;
    setObjectsProcessed.add(currTA);
}
return setPairs;

これにより、最後のcontains、logN、操作が保存されます。

背後にあるロジックは次のとおりです。2 つの Iterator が同じセット上にあり、ObjectProcessedSet の唯一の目的は、処理されたオブジェクトの記録を維持することであるため、インデックスで同じ比較を行うことができます。

例

  Set1={1,1,2,4,5}
  Iterator1 iteratorOuter=Set1.Iterator();


  int outerCount=0;
  while(iteratorOuter.hasNext()){
           Iterator2 iteratorInner=Set1.Iterator();
           int currA=iteratorOuter.next();
      while(iteratorInner.hasNext()){
           int CurrB=iteratorInner.next();
           //Now here if CurraA=4 and CurrB=2 it is obvious it has been processed
          //If currB =5 it is obviously has not been processed.
     }
  }
于 2013-02-05T11:47:46.993 に答える
0

良い提案をありがとう。

基本的な障害は、UnDirectedPair高価equalsでcompareTo方法のある私のクラスでした。私はそれを剥ぎ取られた裸のペアクラスに置き換えました。これにより、コードは約10秒で実行されました。

それでも、セットでの操作の使用にはコストがかかるように思われました。@mawiaの提案を少し変更すると、セットを完全に除外することができます。最終的なコードは、 9分40秒ではなく2秒未満で実行されます-19,471,920ペアオブジェクトのリストを返します!!

public List<Pair<T>> getAllUndirectedPairsAsList(Set<T> setObjects) {
    List<T> listObjects = new ArrayList();
    listObjects.addAll(setObjects);

    List<Pair<T>> listPairs = new ArrayList();
    Iterator<T> listIterator1 = listObjects.listIterator();
    Iterator<T> listIterator2;
    int count = 1;
    T object1;
    while (listIterator1.hasNext()) {
        object1 = listIterator1.next();
        listIterator2 = listObjects.listIterator(count++);
        while (listIterator2.hasNext()) {
            listPairs.add(new Pair(object1, listIterator2.next()));
        }
    }
    return listPairs;
}
于 2013-02-05T20:41:21.480 に答える
0

かなり良いスピードアップをもたらすはずの1つの解決策は、最初にセットをソートしてから、セット内の隣接するエントリのみを比較することです。

もちろん、これは、それぞれに同等のキーPerson（たとえば、名前）が必要であることを意味し、このキーはすべての複製で同じである必要があります。

次に、コードは次のようになります。

SortedSet<Person> persons = new TreeSet<>(...);
Person last = null;
for (Person current : persons) {
  if (last != null) {
    setPairs.add(new UnDirectedPair(last, current));
  }
  last = current;
}

Personが実装されていない（または間違っComparableたフィールドで比較している）場合は、Comparatorを作成するときにを指定できますTreeSet。

このソリューションはO（n * log n）で実行され、後で作業するのはO（n）ペアのみです。たった5600人の場合、これは非常に速いはずです。

この場合、パフォーマンスを向上させるためにを作成することもできます（ごくわずかですがsetPairs）。Listまたは、ペアのセットをまったく作成せずPerson、ループ内でオブジェクトを直接修正するためのメソッドを呼び出すだけです。

于 2013-02-05T11:59:07.110 に答える