Java:ArrayList 瓶颈

Question

在分析一个计算数千个元素的层次聚类的 Java 应用程序时，我意识到 ArrayList.get占用执行集群化部分所需 CPU 的一半左右。

该算法搜索两个更相似的元素(因此它是 O(n*(n+1)/2) )，这是伪代码:

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

实际上有很多 ArrayList.get参与其中。

有没有更快的方法？我认为自从ArrayList应该是一个线性引用数组，它应该是最快的方法，也许我无能为力，因为有太多简单的 get s..但也许我错了。我不认为使用 HashMap可以工作，因为我需要在每次迭代中获取它们，并且 map.values()应该由 ArrayList 支持无论如何..

否则我应该尝试其他更优化的集合库吗？就像谷歌的，或者 Apache 的..

编辑:

你在某种程度上证实了我的怀疑:(

通过尝试并行化，我的性能会得到提升吗？也许使用一组执行器来计算不止一对的相似性..但我不知道数据结构上的同步和锁定是否最终会减慢速度。

相似度是使用两个内容的标签图的点积来计算的。 map 有两张HashMap<Tag, Float> ..此外，我已经将相似之处缓存在 TLongFloatHashMap 中。 (来自 Trove 集合)以避免在以后的迭代中重新计算它，其中 Long key 被计算为两个内容的哈希码(这对于该对来说是唯一的，因此 hash(c1, c2) == hash(c2, c1) )，因此其他所有内容都已经足够调整。

编辑2:

我将发布一些代码只是为了让您更好地理解。这用于计算用于存储两个元素之间相似性的哈希值:

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

相关性的计算方式如下:

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;
        }
    }

这就是算法扫描内容的方式:

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;
            }

我会只使用一个矩阵来存储所有值，但在每次迭代中，最相似的项目都会从列表中删除，并添加一个新项目(根据所选的两个项目，它有一个新的标签映射)

Answer 1

您拥有的算法是 O(n²)。除非你有办法让你的算法比成对比较做得更好，否则性能不太可能明显提高。 :-(