2
\$\begingroup\$

I want to compare two unordered list and currently I am doing it in the following way. Is there a better way to do this as I am repeating my code twice (for null check & then converting to a Set). Maybe there exists a library in Guava which does this? 

public class CompareUnorderedList implements BiPredicate<Object, Object> {
    private Function<Object, Object> mapping;
    public CompareUnorderedList(Function<Object, Object> mapping) {
       this.mapping = mapping;
    }
    @Override
    public boolean test(Object o1, Object o2) {
        o1 = o1 != null ? o1 : Collections.EMPTY_LIST;
        o2 = o2 != null ? o2 : Collections.EMPTY_LIST;

        Set<Object> firstSet = (List<Object>o1).stream().map(mapping).collect(Collectors.toSet());
        Set<Object> secondSet = (List<Object>o2).stream().map(mapping).collect(Collectors.toSet());
        return firstSet.equals(secondSet);
    }
}
\$\endgroup\$
2
  • 2
    \$\begingroup\$ one big issue for this is that your generic type bound is Object instead of Collection<?> or even List<?> ... why is that the case?? \$\endgroup\$ Commented Sep 22, 2017 at 23:15
  • \$\begingroup\$ @Vogel612 I am not sure. This is existing code and I was trying to find a way to reduce this :o \$\endgroup\$ Commented Sep 23, 2017 at 0:07

2 Answers 2

Reset to default
2
\$\begingroup\$

I think it would be better to not convert the List to a Set, but just check if they are the same size and if one contains all of the other (as it is done in HashSet) like so:

public static boolean test(Object o1, Object o2){
    try{
        Collection<?> c1 = (Collection<?>)o1,
                      c2 = (Collection<?>)o2;
        return (c1.size()==c2.size())&&c1.containsAll(c2);
    }
    catch(Exception e){
        return false;
    }
}
\$\endgroup\$
4
  • \$\begingroup\$ Slona containsAll is a O(n2) operation. \$\endgroup\$ Commented Sep 23, 2017 at 0:09
  • \$\begingroup\$ In the question, the code firstSet.equals(secondSet) internally calls code very similar to the code in this answer. \$\endgroup\$ Commented Sep 23, 2017 at 0:13
  • \$\begingroup\$ stackoverflow.com/questions/5552219/… \$\endgroup\$ Commented Sep 23, 2017 at 0:18
  • \$\begingroup\$ What if there are duplicates , then this will not give right, Suppose 1,2,2,2,2 and other set 2,1,1,1,1 . Both conditions will satisfy but list is not equal \$\endgroup\$ Commented Oct 13, 2020 at 10:05
2
\$\begingroup\$

I believe your solution as well as Jenna Sloan's solution is wrong.

Your solution compares the sets of both unordered lists. Thus, it removes duplicates. This implies that the following two unordered lists are equal:

{1, 2} == {1, 1, 2} // true

In other words, set equality does not consider the cardinalities of individual elements.

According to this question, containsAll does also not consider the element cardinalities. Thus, the implementation of Jenna Sloan has the same issue.

My proposal would be the following:

  1. Compare lengths of the lists and return false if they are not equal.

  2. For both lists: Count the occurences of the elements in the unordered list using a HashMap<object,int>:

    • if the hashmap does not already contain the element, set the value of the element (key) to 0
    • if the hashmap contains already the element, set the value of the element to value+1.
  3. For each element in the first HashMap, check if both HashMaps have the same value. If a value does not match, return false.
  4. Return true.

The complexity should be O(n).

\$\endgroup\$

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.