Intersection and union of ArrayLists in Java

Question

Are there any methods to do so  I was looking but couldn t find any   Another question  I need these methods so I can filter files   Some are AND filters and some are OR filters  like in set theory   so I need to filter according to all files and the unite intersects ArrayLists that holds those files   Should I use a different data structure to hold the files  Is there anything else that would offer a better runtime

User · Answer

If the objects in the list are hashable  i e  have a decent hashCode and equals function   the fastest approach between tables approx  size   20 is to construct a HashSet for the larger of the two lists   public static  lt T gt  ArrayList lt T gt  intersection Collection lt T gt  a  Collection lt T gt  b        if  b size    gt  a size              return intersection b  a         else           if  b size    gt  20  amp  amp    a instanceof HashSet                 a   new HashSet a                     ArrayList lt T gt  result   new ArrayList            for  T objb   b                if  a contains objb                     result add objb                                   return result

User · Answer

One-liners since Java 8  import static java util stream Stream concat  import static java util stream Collectors toList  import static java util stream Collectors toSet   Union if there are no duplicates    return concat a stream    b stream    collect toList      Union and distinct    return concat a stream    b stream    distinct   collect toList      Union and distinct if Collection Set return type    return concat a stream    b stream    collect toSet      Intersect if no duplicates    return a stream   filter b  contains  collect toList      If collection b is huge and not O 1   then pre-optimize filter performance by adding 1 line before return  Copy to HasSet  import java util Set         b   Set copyOf b    Intersect and distinct    return a stream   distinct   filter b  contains  collect toList

User · Answer

If you had your data in Sets you could use Guava s Sets class

User · Answer

First  I am copying all values of arrays into a single array then I am removing duplicates values into the array  Line 12  explaining if same number occur more than time then put some extra garbage value into  j  position  At the end  traverse from start-end and check if same garbage value occur then discard   public class Union   public static void main String   args        int arr1    1 3 3 2 4 2 3 3 5 2 1 99       int arr2    1 3 2 1 3 2 4 6 3 4       int arr3   new int arr1 length arr2 length        for int i 0 i lt arr1 length i            arr3 i  arr1 i        for int i 0 i lt arr2 length i            arr3 arr1 length i  arr2 i       System out println Arrays toString arr3         for int i 0 i lt arr3 length i                  for int j i 1 j lt arr3 length j                          if arr3 i   arr3 j                   arr3 j  99999999             line  12                     for int i 0 i lt arr3 length i                  if arr3 i   99999999              System out print arr3 i

User · Answer

You can use CollectionUtils from apache commons

User · Answer

Unions and intersections defined only for sets  not lists  As you mentioned   Check guava library for filters  Also guava provides real intersections and unions   static  lt E gt  Sets SetView lt E  gt union Set lt   extends E gt  set1  Set lt   extends E gt  set2   static  lt E gt  Sets SetView lt E gt  intersection Set lt E gt  set1  Set lt   gt  set2

User · Answer

retainAll   method use for finding common element  i e intersection list1 retainAll list2

User · Answer

After testing  here is my best intersection approach   Faster speed compared to pure HashSet Approach  HashSet and HashMap below has similar performance for arrays with more than 1 million records   As for Java 8 Stream approach  speed is quite slow for array size larger then 10k   Hope this can help   public static List lt String gt  hashMapIntersection List lt String gt  target  List lt String gt  support        List lt String gt  r   new ArrayList lt String gt         Map lt String  Integer gt  map   new HashMap lt String  Integer gt         for  String s   support            map put s  0             for  String s   target            if  map containsKey s                 r add s                       return r    public static List lt String gt  hashSetIntersection List lt String gt  a  List lt String gt  b        Long start   System currentTimeMillis         List lt String gt  r   new ArrayList lt String gt         Set lt String gt  set   new HashSet lt String gt  b        for  String s   a            if  set contains s                 r add s                       print  intersection     r size      -    String valueOf System currentTimeMillis   - start        return r     public static void union List lt String gt  a  List lt String gt  b        Long start   System currentTimeMillis        Set lt String gt  r  new HashSet lt String gt  a       r addAll b       print  union     r size      -    String valueOf System currentTimeMillis   - start

User · Answer

Intersection of two list of different object based on common key - Java 8    private List lt User gt  intersection List lt User gt  users  List lt OtherUser gt  list             return list stream                    flatMap OtherUser - gt  users stream                            filter user - gt  user getId                                    equalsIgnoreCase OtherUser getId                       collect Collectors toList

User · Answer

I was also working on the similar situation and reached here searching for help  Ended up finding my own solution for Arrays  ArrayList AbsentDates   new ArrayList       Will Store Array1-Array2  Note   Posting this if it can help someone reaching this page for help   ArrayList lt String gt  AbsentDates   new ArrayList lt String gt      This Array will store difference       public void AbsentDays                 findDates  April    2017     Array one with dates in Month April 2017             findPresentDays     Array two carrying some dates which are subset of Dates in Month April 2017              for  int i   0  i  lt  Dates size    i                       for  int j   0  j  lt  PresentDates size    j                           if  Dates get i  equals PresentDates get j                               Dates remove i                                                                                         AbsentDates   Dates                               System out println AbsentDates

User · Answer

I think you should use a Set to hold the files if you want to do intersection and union on them  Then you can use Guava s Sets class to do union  intersection and filtering by a Predicate as well  The difference between these methods and the other suggestions is that all of these methods create lazy views of the union  intersection  etc  of the two sets  Apache Commons creates a new collection and copies data to it  retainAll changes one of your collections by removing elements from it

User · Answer

If the number matches  than I am checking it s occur first time or not with help of  indexOf    if the number matches first time then print and save into in a string so  that when the next time same number matches then it s won t print because due to  indexOf    condition will be false    class Intersection   public static void main String   args       String s         int   array1    1  2  5  5  8  9  7 2 3512451 4 4 5  10       int   array2    1  0  6  15  6  5 4  1 7  0 5 4 5 2 3 8 5 3512451            for  int i   0  i  lt  array1 length  i                        for  int j   0  j  lt  array2 length  j                                char c  char  array1 i                   if array1 i      array2 j   amp  amp s indexOf c   -1                                       System out println  Common element is      array1 i                     s  c

User · Answer

retainAll will modify your list  Guava doesn t have APIs for List  only for set    I found ListUtils very useful for this use case    Use ListUtils from org apache commons collections if you do not want to modify existing list   ListUtils intersection list1  list2

User · Answer

In Java 8  I use simple helper methods like this   public static  lt T gt  Collection lt T gt  getIntersection Collection lt T gt  coll1  Collection lt T gt  coll2       return Stream concat coll1 stream    coll2 stream                 filter coll1  contains               filter coll2  contains               collect Collectors toSet        public static  lt T gt  Collection lt T gt  getMinus Collection lt T gt  coll1  Collection lt T gt  coll2       return coll1 stream   filter not coll2  contains   collect Collectors toSet        public static  lt T gt  Predicate lt T gt  not Predicate lt T gt  t        return t negate

User · Answer

public static  lt T gt  Set lt T gt  intersectCollections Collection lt T gt  col1  Collection lt T gt  col2        Set lt T gt  set1  set2      if  col1 instanceof Set            set1    Set  col1        else           set1   new HashSet lt  gt  col1              if  col2 instanceof Set            set2    Set  col2        else           set2   new HashSet lt  gt  col2              Set lt T gt  intersection   new HashSet lt  gt  Math min set1 size    set2 size           for  T t   set1            if  set2 contains t                 intersection add t                        return intersection      JDK8   Probably Best Performance   public static  lt T gt  Set lt T gt  intersectCollections Collection lt T gt  col1  Collection lt T gt  col2        boolean isCol1Larger   col1 size    gt  col2 size        Set lt T gt  largerSet      Collection lt T gt  smallerCol       if  isCol1Larger            if  col1 instanceof Set                largerSet    Set lt T gt   col1            else               largerSet   new HashSet lt  gt  col1                     smallerCol   col2        else           if  col2 instanceof Set                largerSet    Set lt T gt   col2            else               largerSet   new HashSet lt  gt  col2                     smallerCol   col1             return smallerCol stream                filter largerSet  contains               collect Collectors toSet         If you don t care about performance and prefer smaller code just use   col1 stream   filter col2  contains  collect Collectors toList

User · Answer

This post is fairly old  but nevertheless it was the first one popping up on google when looking for that topic   I want to give an update using Java 8 streams doing  basically  the same thing in a single line   List lt T gt  intersect   list1 stream        filter list2  contains       collect Collectors toList      List lt T gt  union   Stream concat list1 stream    list2 stream         distinct        collect Collectors toList       If anyone has a better faster solution let me know  but this solution is a nice one liner that can be easily included in a method without adding a unnecessary helper class method and still keep the readability

User · Answer

You can use the methods  CollectionUtils containsAny and CollectionUtils containsAll from Apache Commons

User · Answer

Here s a plain implementation without using any third-party library  Main advantage over retainAll  removeAll and addAll is that these methods don t modify the original lists input to the methods   public class Test        public static void main String    args  throws Exception            List lt String gt  list1   new ArrayList lt String gt  Arrays asList  A    B    C             List lt String gt  list2   new ArrayList lt String gt  Arrays asList  B    C    D    E    F              System out println new Test   intersection list1  list2            System out println new Test   union list1  list2               public  lt T gt  List lt T gt  union List lt T gt  list1  List lt T gt  list2            Set lt T gt  set   new HashSet lt T gt              set addAll list1           set addAll list2            return new ArrayList lt T gt  set              public  lt T gt  List lt T gt  intersection List lt T gt  list1  List lt T gt  list2            List lt T gt  list   new ArrayList lt T gt              for  T t   list1                if list2 contains t                     list add t                                    return list

User · Answer

The solution marked is not efficient  It has a O n 2  time complexity  What we can do is to sort both lists  and the execute an intersection algorithm as the one below    private  static ArrayList lt Integer gt  interesect ArrayList lt Integer gt  f  ArrayList lt Integer gt  s         ArrayList lt Integer gt  res   new ArrayList lt Integer gt          int i   0  j   0       while  i    f size    amp  amp  j    s size                if  f get i   lt  s get j                 i               else if  f get i   gt  s get j                  j               else                res add f get i                 i      j                           return res       This one has a complexity of O n log n   n  which is in O n log n    The union is done in a similar manner  Just make sure you make the suitable modifications on the if-elseif-else statements    You can also use iterators if you want  I know they are more efficient in C    I dont know if this is true in Java as well

User · Answer

You can use commons-collections4 CollectionUtils  Collection lt Integer gt  collection1   Arrays asList 1  2  4  5  7  8   Collection lt Integer gt  collection2   Arrays asList 2  3  4  6  8    Collection lt Integer gt  intersection   CollectionUtils intersection collection1  collection2   System out println intersection       2  4  8   Collection lt Integer gt  union   CollectionUtils union collection1  collection2   System out println union       1  2  3  4  5  6  7  8   Collection lt Integer gt  subtract   CollectionUtils subtract collection1  collection2   System out println subtract       1  5  7

User · Answer

Final solution     all sorted items from both public  lt T gt  List lt T gt  getListReunion List lt T gt  list1  List lt T gt  list2        Set lt T gt  set   new HashSet lt T gt         set addAll list1       set addAll list2       return new ArrayList lt T gt  set        common items from both public  lt T gt  List lt T gt  getListIntersection List lt T gt  list1  List lt T gt  list2        list1 retainAll list2       return list1       common items from list1 not present in list2 public  lt T gt  List lt T gt  getListDifference List lt T gt  list1  List lt T gt  list2        list1 removeAll list2       return list1

User · Answer

Collection  so ArrayList also  have   col retainAll otherCol     for intersection col addAll otherCol     for union   Use a List implementation if you accept repetitions  a Set implementation if you don t   Collection lt String gt  col1   new ArrayList lt String gt         a  b  c     Collection lt String gt  col1   new TreeSet lt String gt     col1 add  a    col1 add  b    col1 add  c     Collection lt String gt  col2   new ArrayList lt String gt         b  c  d  e     Collection lt String gt  col2   new TreeSet lt String gt     col2 add  b    col2 add  c    col2 add  d    col2 add  e     col1 addAll col2   System out println col1      output for ArrayList   a  b  c  b  c  d  e    output for TreeSet   a  b  c  d  e

User · Answer

Here is a way how you can do an intersection with streams  remember that you have to use java 8 for streams     List lt foo gt  fooList1   new ArrayList lt  gt  Arrays asList new foo    new foo      List lt foo gt  fooList2   new ArrayList lt  gt  Arrays asList new foo    new foo      fooList1 stream   filter f - gt  fooList2 contains f   collect Collectors toList       An example for lists with different types  If you have a realtion between foo and bar and you can get a bar-object from foo than you can modify your stream   List lt foo gt  fooList   new ArrayList lt  gt  Arrays asList new foo    new foo      List lt bar gt  barList   new ArrayList lt  gt  Arrays asList new bar    new bar       fooList stream   filter f - gt  barList contains f getBar    collect Collectors toList

User · Answer

list1 retainAll list2  - is intersection   union will be removeAll and then addAll   Find more in the documentation of collection ArrayList is a collection  http   download oracle com javase 1 5 0 docs api java util Collection html

[java] Intersection and union of ArrayLists in Java

Examples related to java

Examples related to list

Examples related to union

Examples related to intersection