How to compare lists in java with a method other than .equals()

Question

I want to compare two lists of objects. I want a method that will return a collection of the equal objects (intersections) of the lists. However, the type of object in these lists uses a method other than .equals() to be compared (.isSimilar). Is there a streamlined and efficient way to go about this?

Streamlined yes, you write a method and you make it return what you said, et voila. — fonZ, Sep 20 '13 at 22:11
What I would do is implement a custom [retainAll][1] method that uses a custom comparator. [1]: http://docs.oracle.com/javase/6/docs/api/java/util/AbstractCollection.html#retainAll%28java.util.Collection%29 — Grammin, Sep 20 '13 at 22:19

Joni · Answer 1 · 2013-09-20T22:41:38.700

The built-in methods all use the standard equals method to see if two objects are equal; none will use your custom isSimilar method.

Luckily it's easy to program the logic for computing the intersection yourself: go through the elements in the first list, and add it to the intersection if it exists in the second list.

List<YourObject> intersection = new ArrayList<YourObject>();
for (YourObject a: list1) for (YourObject b: list2) {
    if (a.isSimilarTo(b)) {
        intersection.add(a);
        break;
    }
}

Computational complexity: if first list has n items and second list has m items this algorithm makes potentially O(nm) comparisons. If the lists were sorted or if a different data structure could be used (for example a hash table) the complexity could be reduced to O(n+m).

On the other hand, you can create a wrapper class for your objects and that uses the isSimilar method for equality:

final class YourObjectWrapper {
    YourObject value;
    public boolean equals(Object o) {
        return o instanceof YourObjectWrapper
                   ? value.isSimilarTo(((YourObjectWrapper) o).value) 
                   : false;
    }
    // don't forget to override hashCode
}

If you fill your lists with these wrapper objects you can use built-in methods like retainAll.

The issue with this is the lists will end up being quite large, and it ends up being incredibly lag-inducing. — Max Johnson, Sep 20 '13 at 22:21
Either way you'll always have to loop over every element in one list to compare it with every element in the other list. Whether you do this yourself or a built-in method does it: it has to be done. If you could sort it on similarity or something, you could cut it off pre-emptively but this doesn't seem very likely from what I can tell. — Jeroen Vannevel, Sep 20 '13 at 22:24
If you can use a hash table for the second list you don't have to compare every pair of items; you can find if an item exists in a hash table in constant time so the intersection can be built in O(n) time. But transforming the second list into a hash table takes O(m) time, so in total you get O(n+m). I don't think you can do better than that. — Joni, Sep 20 '13 at 22:34

score 1 · Answer 2 · answered Sep 20 '13 at 22:40

You can work around the isSimilar() issue either by setting equals() to call isSimilar() in the item class or by using a class that extends one of List implementations and there you should override the method contains() to use isSimilar() instead of equals().

score 1 · Answer 3 · edited May 23 '17 at 11:50

1

Please avoid changing the semantics of equals(), both for lists and for items...

Anyway, I think you might like to use Guava's functional idioms:

Define an Iterable<Pair<T,T>>-implementing class constructed with a pair of List<T>, with the iteration proceeding from one pair of corresponding elements to the next.
Create a predicate on pairs which uses isSimilar() on the first and second pair.
Use Iterables.any(theIterableYouCreated, thePredicateYouCreated).

Don't have a pair class already? See here. Also, you'll need to handle the case of different lengths, which you can do before constructing the iterator; or you could do it some other way.

edited May 23 '17 at 11:50

Community

1
1

answered Sep 21 '13 at 20:39

einpoklum

118,144
57
340
684

If you already have a Predicate that checks for equality, this approach would save you a little trouble. But when you consider that you still have to write an Iterable that builds Pairs and checks for edge cases, it's not much better than writing the whole things yourself. If you don't already have a Predicate, it becomes an exercise in wrapping your code in Google's API for the sake of saving yourself a for-loop and if-statement. Just a heads up for anyone who isn't already heavily vested in Guava. – spaaarky21 Dec 17 '13 at 18:11

score 0 · Answer 4 · answered Sep 20 '13 at 22:11

0

The efficient streamlined way to do this is to write you own method for this. That said, this would be a simple method, where you compare the two objects and if they are equal you add them to a list, or other collection.

answered Sep 20 '13 at 22:11

BlackHatSamurai

23,275
22
95
156

score 0 · Answer 5 · answered Sep 20 '13 at 22:17

0

No solution present. I take it that you cannot sort the lists (similarity). Hence you need to compare every element from one list with all of the others to see whether no similar is found, in order to reject it. N x M, quadratic complexity.

answered Sep 20 '13 at 22:17

Joop Eggen

107,315
7
83
138

How to compare lists in java with a method other than .equals()

5 Answers5