CODEWITHSUNDEEP
javaarraylistdata-structuresset
xmen-5
xmen-5

Reputation: 1906

HashSet in place of ArrayList drawback in performance

For one of my projects, I was using an ArrayList<ArrayList<Integer>> as a graph data structure.

So the graph:

enter image description here

will be equivalent to the the list of lists below:

enter image description here

But I changed my data structure from ArrayList<ArrayList<Integer>> to Map<Integer, Set<Integer>>, so the same graph above will now be equivalent to the map:

enter image description here

One of the reason I took the choice of Set is that every list should contains only unique elements.

The choice of Map was for the ease of manipulating the data structure.

The problem is when I changed the data structure, the performance has been down almost by 2x.

Here are the most used operations in my project:

In the first implementation:

int index = someIndex();
int v1 = listoflists.get(index).get(0);
int v2 = listoflists.get(index).get(1);

In the second implementation:

int index = somIndex();
Set<Integer> sets = map.get(index);
Integer[] set =  sets.toArray(new Integer[sets.size()]);
int v1 = set[0];
int v2 = set[1];

Sometimes I need to get one, two or at most three elements.

Any idea to improve the performance of the second implementation?

Upvotes: 1

Views: 70

Answers (1)

singh30
singh30

Reputation: 1503

Integer[] set =  sets.toArray(new Integer[sets.size()]);

The above code line is adding extra complexity. Optimize it using an Iterator,

int index = somIndex();
Set<Integer> sets = map.get(index);
Iterator iterator = sets.iterator(); 

while (iterator.hasNext()) { 
   System.out.println(iterator.next()); 
}

As sometime you require only few values so iterate accordingly.

Upvotes: 1

Related Questions