Comparing two array lists

Question

I have the following array lists

List<Long> ids = new ArrayList<Long>();
List<Long> empIds = new ArrayList<Long>();

Now I need to compare these 2 arrays and check if any value in ids is there in empIds. If yes I need to exit with a boolean true. I have done this in the following way.

for (Long id : ids) {
    if (empIds.contains(id)) {
        checker = true;
        break;
    }
}

But this takes a lot of time. Can anybody please help me to optimize this?

What is the size of the arrays? and please share some time output. I dont think there is a simpler way — Abdullah Ahçı, Jun 29 '16 at 05:36

score 4 · Accepted Answer · edited Jun 29 '16 at 05:23

4

You can put empIds in a HashSet to improve the search time :

Set<Long> empIdsSet = new HashSet<Long>(empIds);
for (Long id : ids) {
    if (empIdsSet.contains(id)) {
        checker = true;
        break;
    }
}

Each call to empIdsSet.contains(id) would take expected constant time (O(1)), which is better than the linear time required by each call to empIds.contains(id).

edited Jun 29 '16 at 05:23

shachar

641
5
12

answered Jun 29 '16 at 05:18

Eran

387,369
54
702
768

1

This would assume that the time needed to hash the list does not matter. – Tim Biegeleisen Jun 29 '16 at 05:19
2

@TimBiegeleisen The time to hash the list is linear, so the overall time is still better than the original code. – Eran Jun 29 '16 at 05:20
1

Too bad this got marked as a duplicate. This solution performs much faster than `Collections.disjoint` (which probably runs in quadratic time - similar to the OP's code) – Michael Markidis Jun 29 '16 at 05:42

Comparing two array lists

1 Answers1