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
    \$\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\$ – Vogel612 Sep 22 '17 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\$ – user1692342 Sep 23 '17 at 0:07
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\$
  • \$\begingroup\$ Slona containsAll is a O(n2) operation. \$\endgroup\$ – user1692342 Sep 23 '17 at 0:09
  • \$\begingroup\$ In the question, the code firstSet.equals(secondSet) internally calls code very similar to the code in this answer. \$\endgroup\$ – Jenna Sloan Sep 23 '17 at 0:13
  • \$\begingroup\$ stackoverflow.com/questions/5552219/… \$\endgroup\$ – user1692342 Sep 23 '17 at 0:18
1
\$\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).

New contributor
JFFIGK is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct.
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.