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

Question

I want to compare two lists of objects. I need a method that returns a collection of equal objects (intersections) of lists. However, the type of the object in these lists uses a method other than .equals () for comparison (.isSimilar). Is there an optimized and efficient way to do this?

Answer 1

Built-in methods use the standard equals method to see if two objects are equal; nobody will use your own isSimilar method.

Fortunately, it is easy to program the logic for calculating the intersection itself: 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; } } 

Complexity of calculations: if there are n elements in the first list and m elements in the second list, this algorithm makes O (nm) comparisons possible. If the lists have been sorted or another data structure (for example, a hash table) can be used, the complexity can be reduced to O (n + m).

On the other hand, you can create a wrapper class for your objects and which 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 populate your lists with these wrapper objects, you can use built-in methods such as retainAll .

Answer 2

You can work around the problem of isSimilar() either by setting equals() to call isSimilar() on the element class, or using a class that extends one of the List implementations, and there you must override the contains() method to use isSimilar() instead of equals().

Answer 3

Please do not change the semantics of equals() , both for lists and for elements ...

Anyway, I think you could use the functional idioms of Guava :

• Define the class Iterable<Pair<T,T>> -object constructed using the pair List<T> , and iteration is performed from one pair of the corresponding elements to the next.
• Create a predicate for pairs that uses isSimilar() for the first and second pairs.
• Use Iterables.any(theIterableYouCreated, thePredicateYouCreated) .

Don't you have a pair? See here . In addition, you will need to handle a case of different lengths, which you can do before constructing an iterator; or you could do it differently.

Answer 4

An efficient streamlined way to do this is to write your own method for doing this. However, this will be a simple method when you compare two objects, and if they are equal, you add them to a list or another collection.

Answer 5

No solution exists. I suppose you cannot sort lists (similarities). Therefore, you need to compare each item from one list with all the others to see if it was found, to reject it. N x M, quadratic complexity.