Swapnil Swapnil - 1 month ago 8
Java Question

Compare contents of two ArrayLists efficiently

Any idea why

contains
not working here, these statement always evaluating false
firstSchema.contains(firstSchema.get(0))


List<String> firstSchema = new ArrayList<String>();
firstSchema.add(0,"test");
firstSchema.add(1,"testy");

if(!(firstSchema.contains(firstSchema))){
System.out.println("hey arraylist content matched");
}


Even No luck for

if(!(firstSchema.contains("test"))){
System.out.println("hey arraylist content matched");
}


I need to get true if any one or more or all elements from one arraylist matched with other arraylist elements

Answer

The simplest way to check if a list contains any elements from another list is to call contains() on one of the lists, passing each element as an argument in turn. Something like:

public <E> boolean slowListContains(List<E> a, List<E> b) {
  for (E element : a) {
    if (b.contains(element)) {
      return true;
    }
  }
  return false;
}

This is slow, however, because contains() is a linear operation (O(n)), and since we're calling it in a loop the slowListContains() function takes quadratic time (O(n^2)) which is poor. We can do better.

A Set (or more precisely a hash-based set such as HashSet) has an efficient contains() method which runs in less-than-linear time (constant time in the case of HashSet). Converting one or the other list into a Set will make the loop in slowListContains() much faster. Something like:

public <E> boolean fasterListContains(List<E> a, List<E> b) {
  Set<E> aSet = new HashSet<>();
  aSet.addAll(a);
  for (E element : b) {
    if (aSet.contains(b)) {
      return true;
    }
  }
  return false;
}

This isn't perfect, but it's certainly much faster than the naive solution. A slight improvement would be to always convert the smaller list into the Set, rather than the first one. You could also take arbitrary Iterable parameters rather than List parameters, then check if either of them are already a Set and if so skip the set-construction step.

Comments