根据条件将元素与集合中的其他元素进行比较

Question

将实际问题简化为集中于比较/删除性能。

给定一组包含n个元素的S，找到最优的方法将每个元素与所有其他元素进行比较，直到满足决定是否删除和删除哪个项的条件为止。当n较高时，我会经历长的运行时(例如，在英特尔i5-6500 cpu上，n=3000的运行时为2500 is )。

元素是一个元组对象( itv，t)，其中itv持有整数间隔值(0到4之间，包括在内)，t持有整数的总收益值。

条件:给出s和另一个元组s'，如果itv == itv'，则t <= t‘t’删除，否则删除双倍‘。

一个幼稚的例子。S={(1,20)，(0,40)，(1,35)}

1. 比较(1,20)和(0,40)：itv != itv'，继续。
2. 比较(1,20)和(1,35)：itv == itv'，t< t'，从S中移除(1,20)。
3. 比较(0,40)和(1,34)：itv != itv'，返回S。

由于Java在迭代时删除元素的限制，for-循环效率很低，我目前在Iterator循环中使用了嵌套的foreach-循环。然而，我仍然觉得它表现不佳。在我看来，这种想法主要是因为代码看起来很糟糕。

以下是我的执行情况。它试图尽可能减少不必要的比较量。我的代码使用外部Iterator将主元组与其他元组进行比较。但是，如果内部元组更差，则内部元组被标记为删除，并将在外部循环迭代结束时被删除。

有没有人看到任何明显的错误，对性能有任何评论(昂贵的调用)，或者为了代码清晰而重构？

public static HashSet<Tuple> compareAndRemove(HashSet<Tuple> set) {
    HashSet<Tuple> bestTuples = new HashSet<>(set.size()); //Return set
    Collection<Tuple> tupleRemovals = new HashSet<>(); //Tuples to remove this iteration
    Iterator<Tuple> s_iter;

    do {
        set.removeAll(tupleRemovals);
        removedElements += tupleRemovals.size();
        tupleRemovals = new HashSet<>();

        s_iter = set.iterator();
        if (s_iter.hasNext()) {
            Tuple s = s_iter.next();
            if (!s_iter.hasNext()) { //Last element; nothing to compare anymore
                bestTuples.add(s);
                s_iter.remove();
                break;
            }

            //Compare with other
            boolean removeMainTuple = false;
            for (Tuple s_prime : set) {
                boolean equalIntervals = true;
                if (s.equals(s_prime)) continue; //Skip same element

                //Check interval
                if (s.itv == s_prime.itv) {
                    //Decide which Tuple to discard
                    if (s.t <= s_prime.t) {
                        removeMainTuple = true; //Remove Iterator element
                        break;
                    } else {
                        tupleRemovals.add(s_prime); //Remove foreach element
                    }
                }
            }
            //Move current item to return set if it was the best
            if (!removeMainTuple) {
                bestTuples.add(s);
            }
            s_iter.remove();
        }
    } while (s_iter.hasNext());

    bestTuples.addAll(set);

    return bestTuples;
}

Answer 1

在您只想找到最佳元组的情况下，代码可以简单得多：

• 为Tuple的每个值找到具有最佳t的itv (听起来像是Map的任务)
• 将最好的一组Tuple放入一组，并将其返回

public static Set<Tuple> bestTuples(Set<Tuple> set) {

    Map<Integer, Tuple> bestTuplesByItv = new HashMap<Integer, Tuple>();
    Tuple bestTupleSoFar;
    for (Tuple t: set) {
        if ((bestTupleSoFar = bestTuplesByItv.get(t.itv)) == null || t.t > bestTupleSoFar.t) {
            bestTuplesByItv.put(t.itv, t);
        }
    }

    Set<Tuple> bestTuples = new HashSet<Tuple>();
    bestTuples.addAll(bestTuplesByItv.values());

    return bestTuples;

}

这也应该更快--您的解决方案有一些嵌套的循环，O(n^2)，但是上面的建议只遍历整个set一次。我的直觉告诉我，从一个集合中删除东西比仅仅用我们想要的东西做一个新的集合要慢，但是我不确定HashSet。

因为Map的值来自HashSet，所以所有的值都保证具有唯一的散列值。因为是这样的，所以我们不需要一个LinkedHashMap --普通的HashMap可以正常工作(LinkedHashMap创建链接列表来处理哈希冲突，但这是不必要的，因为我们没有任何)。

但是，您的代码似乎在对作为参数传入的Set进行变异--如果这是所需的行为，这是对上面代码的简单修改--只需清除set中的值并在返回之前添加我们想要的值：

public static Set<Tuple> compareAndRemove(Set<Tuple> set) {

    Map<Integer, Tuple> bestTuplesByItv = new HashMap<Integer, Tuple>();
    Tuple bestTupleSoFar;
    for (Tuple t: set) {
        if ((bestTupleSoFar = bestTuplesByItv.get(t.itv)) == null || t.t > bestTupleSoFar.t) {
            bestTuplesByItv.put(t.itv, t);
        }
    }

    set.clear();
    set.addAll(bestTuplesByItv.values());

    return set;

}