Simplified the actual problem to focus on comparing/removing performance.
Given a set S with n elements , find the most optimal way to compare each element to all others until a condition is met that decides if and which item to remove. I experience long runtimes when n is high (e.g. n=3000 has a runtime of 2500ms on an intel i5-6500 cpu)
An element is a Tuple object (itv, t) where itv holds an integer interval value (between 0 and 4, inclusive) and t holds an integer total benefit value.
The condition: Given Tuple s and another Tuple s', if itv == itv', then if t <= t' remove s, else remove s'.
A naïve example. S={(1,20),(0,40),(1,35)}
Compare (1,20) with (0,40): itv != itv', continue.
Compare (1,20) with (1,35): itv == itv', t < t', remove (1,20) from S.
Compare (0,40) with (1,34): itv != itv', return S.
Due to Java's constraints on removing elements while iterating, for-loops are wildly inefficient and I currently use a nested foreach-loop inside an Iterator loop. However, I still feel like it underperforms. This thought is mostly because the code looks terrible, in my opinion.
Below is my implementation. It tries to reduce the amount of unnecessary comparisons as much as possible. My code uses an outer Iterator for comparing the main Tuple to the others. In the case that the interval matches and the main Tuple's total benefit is worse, the inner loop is stopped, the main Tuple is removed and we continue with the next Iterator item. If the inner Tuple is worse, however, then the inner Tuple is marked for deletion and will be deleted at the end of the outer loop iteration.
Does anyone see any glaring mistakes, have any comments about performance (expensive calls) or refactoring for code clarity?
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;
}