0

此代码需要 9 分钟才能运行一组 5,600 个对象：

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

我建议的一个技巧是保持外循环和内循环的计数器。

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;

这将保存最后包含一个 logN 的操作。

背后的逻辑是：由于两个Iterator在同一个集合上，而ObjectProcessedSet的唯一目的是维护处理过的Object的记录，可以实现相同的比较索引。

例子

  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

一个应该给你一个很好的加速的解决方案是首先对集合进行排序，然后只比较集合中的相邻条目。

当然，这意味着您需要为每一个拥有一个可比较的键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 人来说，这应该非常快。

在这种情况下，您也可以制作setPairsaList以获得更多性能（尽管很少）。或者您根本不创建这组对，而只是Person直接在循环中调用您的方法来纠正对象。

于 2013-02-05T11:59:07.110 回答
0

谢谢你的好建议。

基本障碍是我的课UnDirectedPair，它有昂贵的方法equals和compareTo方法。我用剥离的裸 Pair 类替换它。这使代码在大约 10 秒内运行。

尽管如此，在集合上使用操作似乎代价高昂。对@mawia 的建议稍作修改后，集合可以完全排除在外。最终代码在2 秒内而不是 900 万 40 秒内运行 - 返回一个包含 19,471,920 个 Pair 对象的列表！

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 回答