What is the efficient algorithm / way to find intersection between 2 array lists. ( I am using java 8 )

Question

I have 2 array lists which contains a custom object Stock.

public class Stock{

    private String companyName;
    private double stockPrice;

    // getters and setters 
}

List1 contains Stock objects . List2 also contains stock objects.

List 1 and list 2 are same in size. There are some stock objects in list 1 which are same as present in list 2. I need to get those same objects which re present in list 1 out of list 2. i.e. in another words get the intersection of list 1 and list 2 in list 2. I am trying to find out if there is any direct way in Java 8 which gives this result in an efficient way .Or if not , how to construct an efficient algorithm in terms of time complexity and space complexity ? Help is highly appreciated.

when you say same Stock object, you mean `==` would work? or do you have an equal method on your object? Or how do you define that 2 stocks are equal? — Bentaye, Nov 05 '18 at 10:50
I would have an equals and hashcode method overriden in Stock class which would distinguish between two objects if the stock company name ,stock price and the timestamp is equal. — CodeMaster, Nov 05 '18 at 10:52
@Lalit Have a look at this: https://stackoverflow.com/questions/31683375/java-8-lambda-intersection-of-two-lists — Bentaye, Nov 05 '18 at 10:55
I have tried list1.retainAll(list2), however I want to know the efficient algorithm with time complexity either O(n) or lesser and definately not O(n2) — CodeMaster, Nov 05 '18 at 10:55
I have already checked out List intersect = list1.stream() .filter(list2::contains) .collect(Collectors.toList()); However can it give O(n) or lesser? — CodeMaster, Nov 05 '18 at 10:57
Possible duplicate of https://stackoverflow.com/questions/5283047/intersection-and-union-of-arraylists-in-java — Naman, Nov 05 '18 at 10:59
The solution above is not preferrable, because it is using a loop and it would be better to use the standard java API. or Java 8 feature. — CodeMaster, Nov 05 '18 at 11:03

Nagendra Varma · Accepted Answer · 2018-11-05T11:05:06.607

0

List<T> intersect = list1.stream()
    .filter(list2::contains)
    .collect(Collectors.toList());

CREDIT: Fat_FS answer at Intersection and union of ArrayLists in Java.

Make sure you override equals and hashcode methods (assuming you wanted to look at the contents of the objects for equality comparison)

Convert list to set for better performance

edited Nov 05 '18 at 11:05

answered Nov 05 '18 at 10:54

Nagendra Varma

2,215
3
17
26

Thanks Nagendra, I am a little confused here with this step , if you can please write small snippet it would be great. I have already checked that link. – CodeMaster Nov 05 '18 at 10:58
It simply creates a stream of list1, filter out the elements which are not present in list2 and collects the filtered elements into 'intersect' link – Nagendra Varma Nov 05 '18 at 11:02
That is true, however what is the time complexity of the operation? And when to convert list to set for better performance? Can you please paste the code snippet please? Appreciate your help. – CodeMaster Nov 05 '18 at 11:05
1

@Lalit you can just replace `.filter(list2::contains)` with `.filter(new HashSet<>(list2) ::contains)`, to get a better time complexity. I leave it as an exercise for your to find out, at which size of `list2` it starts to pay off… – Holger Nov 05 '18 at 14:06
Thanks @Holger . Thanks all. – CodeMaster Nov 05 '18 at 14:13
@Holger In extension to this , I want to remove all the intersection objects from the list as a result of above operation and i tried something like the below : stocksSentToConsumerList.removeAll(stocksSentToConsumerList.stream() .filter((priceUpdateQueueCopy)::contains).collect(Collectors.toList())); Is there any efficient way to do this operation in terms of time complexity? – CodeMaster Nov 06 '18 at 10:03
@Lalit just use `stocksSentToConsumerList.removeAll(priceUpdateQueueCopy)` or `stocksSentToConsumerList.removeAll(new HashSet<>(priceUpdateQueueCopy))`, depending on the size of `priceUpdateQueueCopy`. – Holger Nov 06 '18 at 10:39
@Holger : removeAll is O(n2) right which seems expensive? – CodeMaster Nov 06 '18 at 11:01
@Lalit no, for a `List`, it’s O(n) times the lookup complexity of the specified collection argument, so when using `stocksSentToConsumerList.removeAll(priceUpdateQueueCopy)`, it’s O(n×m), which is fair when the argument is known to be a small collection. Otherwise, use `stocksSentToConsumerList.removeAll(new HashSet<>(priceUpdateQueueCopy))`, where the lookup of the hash set is O(1), so the complexity of `removeAll` is O(n) then. Or, if you consider the cost of the hash set construction, it’s O(n+m). – Holger Nov 06 '18 at 12:52
@Holger Thanks Holger. I would highly appreciate if you can have a look at this link and provide your valuable inputs on the same please? The above question was relevant for the below activity Link :- https://codereview.stackexchange.com/questions/207134/producer-consumer-design-and-implementation-using-java-8 – CodeMaster Nov 07 '18 at 11:09

What is the efficient algorithm / way to find intersection between 2 array lists. ( I am using java 8 )

1 Answers1