CODEWITHSUNDEEP
javaperformanceout-of-memorytime-complexityspace-complexity
Ivan Zandonà
Ivan Zandonà

Reputation: 154

Arraylist Intersection performance (in time and space ) in Java

I need to make million of intersections of ArrayList in java, and for this purpose I use this method:

public static ArrayList<Integer> intersection(ArrayList<Integer> a, ArrayList<Integer> b) {
        Set<Integer> aSet = new HashSet<Integer>(a);
        Set<Integer> bSet = new HashSet<Integer>(b);

        for(Iterator<Integer> it = aSet.iterator(); it.hasNext();) {
            if(!bSet.contains(it.next())) it.remove();
        }
        return new ArrayList<Integer>(aSet);
    }

In terms of time It's performant But I have a lot of memory leaks and I often go out of memory. How can I improve the function in order to be performant both in time and in space?

UPDATE

The arraylists given in input must remain unchanged.

Upvotes: 2

Views: 465

Answers (2)

Elliott Frisch
Elliott Frisch

Reputation: 201439

One solution (for performance) would be to use a SortedSet like so

public static List<Integer> intersection2(List<Integer> a, List<Integer> b) {
    SortedSet<Integer> aSet = new TreeSet<Integer>(a);
    aSet.retainAll(b);
    return new ArrayList<Integer>(aSet);
}

Another solution (for space) would be use the passed in List(s) like so (EDITED with the "new requirement" that the passed in List(s) be unchanged),

public static List<Integer> intersection3(List<Integer> a, List<Integer> b) {
    List<Integer> c = new ArrayList<Integer>(a); // <-- new requirement.
    c.retainAll(b);
    return c;
}

Upvotes: 2

Puru--
Puru--

Reputation: 1111

First of you do not need to HashSets here , you can do this with a single HashSet.

Add everything from first ArrayList to a HashSet and , iterate through second 'ArrayList' and check if each element contained in the HashSet constructed earlier, if so add it to the result ArrayList.

Upvotes: 0

Related Questions