Java compare unordered ArrayLists

Question

anybody know an efficient way to decide if two arraylists contain the same values?

Code:

ArrayList<String> dummy1= new ArrayList<String>();
list1.put("foo");
list1.put("baa");

ArrayList<String> dummy2= new ArrayList<String>();
list1.put("baa");
list1.put("foo");

dummy1 == dummy2

the challenge is that the arraylists has not the same value order..

(foo, baa) == (foo, baa) // per definition :)

i need to get this

(foo, baa) == (baa, foo) // true

so what would be your approach?

Liggitt

use for loop and ArrayList.contains() method – Viehmann

How you define efficiency? I don't think you can check if two arraylists have same elements without comparing each one of them. Hence, best you can do is O(N) – Caterwaul

Dump one array into a hash table and check if all entries in the other are found in the table? – Mcdavid

@Mcdavid Yes, although to handle duplicates you need to keep track of frequency as I do in my answer. – Flor

What @Mcdavid said, but before you check the hash table against the second sequence, do a quick size() comparison. No sense in doing all that work if the sizes differ. However, things get more complicated if you want to collapse duplicates, e.g., if (a, b) == (b, a, b), as the size() comparison becomes meaningless, and you must then check for elements that exist in the hash table, but not in the second sequence. – Desiderative

Answer 1

Just sort it first.

public  boolean equalLists(List<String> one, List<String> two){     
    if (one == null && two == null){
        return true;
    }

    if((one == null && two != null) 
      || one != null && two == null
      || one.size() != two.size()){
        return false;
    }

    //to avoid messing the order of the lists we will use a copy
    //as noted in comments by A. R. S.
    one = new ArrayList<String>(one); 
    two = new ArrayList<String>(two);   

    Collections.sort(one);
    Collections.sort(two);      
    return one.equals(two);
}

Honestly, you should check your data structure decision. This seems more like a set problem. Sorting then comparing will take O(nlog n) while a HashSet comparison will only be O(n).

Eggshell

hahaha it´s completly amazing how close-minded you can be if you are on a run ;) thank you! – Liggitt

Answer 2

The sort method runs in O(n log n) but we can do better. First perform null and size comparisons. Then use a HashMap<String, Integer> and store the frequency of a particular string as the value. Do this for both lists and check the size of the maps are the same. Then iterate through one of the maps, for each entry, check the other map contains the string and has the same frequency. This method is O(n) average case.

Flor

Not strictly speaking. Each call to map.get() is O(n). – Cyrie

map.get() is O(1) – Via

@Cyrie you have 388K reputation and according to your profile you have been a "Senior Member of Technical Staff at Oracle, developing the java compiler." In light of that, I am completely dumbfounded by the statement that strictly speaking, each call to map.get() is O(n). That's not strictly speaking, that's infinite-improbability-worst-case-speaking. Would you care to explain? (Or do we have a case of Mark Reinhold's "I am an Oracle employee, do not believe a word of what I say" here?) – Franciscafranciscan

Everyone is human, and no matter their experience and background, mistakes will be made. :-) When we talk about complexity, without stating any specific case, we typically talk about the worst case. (The fact that a really dumb algorithm might run in O(1) for some specific input is rarely interesting.) Without making assumptions about the input, we can not rule out the possibility that all elements hash to the same bucket, which is why I claim that the worst case complexity is O(n). Would you agree? That being said... – Cyrie

...hash tables are special, and the theoretical worst case scenario is rarely interesting in practice (as you hint in your comment). What we typically do is that we assume a simple uniform hashing (SUHA). This is however something that should be stated before claiming that read is O(1). Note that this is an assumption that may or may not be reasonable to make. (Think for example of software with real time constraints, safety critical applications, etc.) I've written an article on this topic here: programming.guide/hash-tables-complexity.html – Cyrie

Answer 3

Assuming that the lists contain no duplicates, you can use two temporary HashSet<String> objects for that.

Construct sets of Strings from both ArrayList<String>s that you are comparing, and then check that the first set has all items from the second list, and also the second set contains all items from the first list.

You can do it like this:

List<String> a = ...;
List<String> b = ...;
Set<String> setA = new HashSet<String>(a);
Set<String> setB = new HashSet<String>(b);
boolean same = setA.containsAll(b) && setB.containsAll(a);

If you must account for duplicates, replace HashSet<String> with HashMap<String,Integer> to make and compare the corresponding frequency counters.

Zachary

This assumes that you can collapse duplicates, e.g., (a, b) == (b, a, b) == (b, b, b, a). – Desiderative

@MikeStrobel Thanks, I edited the answer to make a note of it. – Zachary

Answer 4

The most efficient way depends on the size of the array.

• For very small lists, using contains() is probably most efficient. (Maybe for lists with between 0 to 5 elements ... I'd guess.)

• For medium to large sized lists you can either:

  • sort the both array lists and compare them pair-wise,

  • sort one list and use binary search to probe the values in the second one.

  • convert one to a HashSet and probe with the values in the second one.

The complexity analysis is not straight-forward as it depends on the likelihood that the lists are equal ... or not. The "worst case" is when the lists are equal, because that means that you have to check all elements before you can return true. In that case the complexities are O(N^2), O(NlogN), O(NlogN) and O(N) respectively.

That doesn't take into account space usage, and (in Java) the performance impact of using a lot of memory,

There is also the issue of the "constants of proportionality"; e.g. O(NlogN) can be faster than O(N) for small values of N.

In short ... there is no single solution that is always going to be best.

Esparto

the lists are small.. i got a view thousand of them ;) – Liggitt

How small? What do you mean by "i got a view thousand of them"? – Esparto

Not "view" - "few" hehe.. I had a few thousand small lists ;-) – Liggitt

Answer 5

You should sort the two ArrayLists, then do an equal comparison. However, you may need to remove duplicates (I'm not sure about your policy on duplicates).

Anthotaxy

Answer 6

Here you have a Java 8, please specify if you need a Java 7 solution.

Assumption 1: The ArrayLists are not nulls.

Its time complexity is O(N), where N is the size of any of the inputs.

Its memory complexity in addition to the input is 0(N)

In other words, its time and memory complexity are linear.

Theoretically you could have a constant O(1)memory complexity, but it would involve removing elements from the a1 while adding them to the setA1. In my opinion, this relies too much on garbage collector so hopefully this solution will be enough for you.

import java.util.*;

public class ArraySameValuesSolver {

    public boolean of(List<String> list1, List<String> list2) {
        if (list1.size() != list2.size())
            return false;
        Map<String, Integer> occ = new HashMap<>();
        list1.stream().forEach(s -> incrementOccurences(occ, s));
        for (String s: list2) {
            decrementOccurrences(occ, s);
            if (occ.get(s) < 0)
                return false;
        }
        return true;
    }

    private void incrementOccurences(Map<String, Integer> occ, String s) {
        if (!occ.containsKey(s))
            occ.put(s, 1);
        else
            occ.put(s, occ.get(s) + 1);
    }

    private void decrementOccurrences(Map<String, Integer> occ, String s) {
        if (!occ.containsKey(s))
            occ.put(s, -1);
        else
            occ.put(s, occ.get(s) - 1);
    }

}

Okajima

Answer 7

You can find your anser here,

http://code.google.com/p/guava-libraries/wiki/CollectionUtilitiesExplained

By Using Compare chain,

http://docs.guava-libraries.googlecode.com/git/javadoc/com/google/common/collect/ComparisonChain.html

Hope this will work for you.

Regards Ashok Gudise.

Ferren

Answer 8

  public boolean isListEquals( List listA , List listB ) {
    boolean result = false;

    if ( ( listA == listB ) ) {
      result = true;
      return result;
    }

    if ( ( listA == null ) || ( listB == null ) ) {
      return result;
    }

    if ( listA.size() != listB.size() ) {
      return result;
    }

    List listC = new ArrayList( listA );
    listC.removeAll( listB );
    if ( listC.size() > 0 ) {
      return result;
    }

    result = true;
    return result;
  }

Lotti