Java: ArrayList bottleneck

Question

while profiling a java application that calculates hierarchical clustering of thousands of elements I realized that ArrayList.get occupies like half of the CPU needed in the clusterization part of the execution.

The algorithm searches the two more similar elements (so it is O(n*(n+1)/2) ), here's the pseudo code:

int currentMax = 0.0f
for (int i = 0 to n)
  for (int j = i to n)
    get content i-th and j-th
      if their similarity > currentMax
        update currentMax

merge the two clusters

So effectively there are a lot of ArrayList.get involved.

Is there a faster way? I though that since ArrayList should be a linear array of references it should be the quickest way and maybe I can't do anything since there are simple too many gets.. but maybe I'm wrong. I don't think using a HashMap could work since I need to get them all on every iteration and map.values() should be backed by an ArrayList anyway..

Otherwise should I try other collection libraries that are more optimized? Like google's one, or apache one..

EDIT:

you are somewhat confirming my doubts :(

Would I obtain a boost in perfomance trying to parallelize things? Maybe using a pool of executors that calculate similarity on more than one couple.. but I don't know if synchronization and locks on data structures would end up slowing it down.

Similarity is calculated using the dot product of tag maps of the two contents. The maps are two HashMap<Tag, Float>.. in addition I already cache similarities in a TLongFloatHashMap (from Trove collections) to avoid recalculating it in later iterations in which the Long key is calculated as a hashcode of both contents (that is unique for the pair so that hash(c1, c2) == hash(c2, c1)) so everything else is already tuned up enough.

EDIT2:

I'll post a little bit of the code just to let you understand better.. This is used to calculate the hash used to store the similarity between two elements:

private long computeKey(int h1, int h2) {   
        if (h1 < h2) {
            int swap = h1;
            h1 = h2;
            h2 = swap;
        }           
        return ((long)h1) << 32 | h2;
    }

This is how correlation is calculated:

float correlation(Map<Tag, Float> map1, Map<Tag, Float>map2, HierarchNode n1, HierarchNode n2) {    
        long key = computeKey(n1.hashCode, n2.hashCode);

        if (cache.contains(key)) {
            ++hitCounter;
            return cache.get(key);
        }
        else {      
            float corr = 0.0f;

            Set<Map.Entry<Tag, Float>> entries;
            Map<Tag, Float> curMap;

            if (map1.size() < map2.size()) {
                entries = map1.entrySet();
                curMap = map2;
            }
            else {              
                entries = map2.entrySet();
                curMap = map1;
            }

            for (Map.Entry<Tag, Float> ee : entries) {
                Float f2 = curMap.get(ee.getKey());

                if (f2 != null)
                    corr += ee.getValue()*f2;
            }

            cache.put(key, corr);               
            return corr;
        }
    }

And this is how the algorithm scans the content:

for (int j = 0; j < clusters.size(); ++j) {
                skip = false;

                for (int k = j+1; k < clusters.size(); ++k) {                                   
                    float r = correlation(clusters.get(k).tags, clusters.get(j).tags, clusters.get(k), clusters.get(j));

                    if (r > max) {
                        max = r;
                        i1 = j;
                        i2 = k;
                    }

                    if (max == 1.0f) {
                        skip = true;
                        break;
                    }
                }

                if (skip)
                    break;
            }

I would have used just a matrix to store all the values, but on every iteration the most similar items are removed from the list and a new item is added (which have a new tag map depending on the two chosen)

Answer 1

The algorithm you have is O(n²). Unless you have a way to make your algorithm do something significantly better than doing pairwise comparisons, performance is unlikely to appreciably improve. :-(

Answer 2

ArrayList.get is an if statement followed by an array access. There's not much to optimize there. ArrayList.get occupies half the execution time because you're not doing anything else. The important factor in the time taken is the number of iterations not what's inside the for-loop.