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太多了。但也许我错了。我不认为使用HashMap可以工作，因为我需要在每次迭代中都得到它们，而且map.values()应该得到一个ArrayList的支持。

否则，我应该尝试其他更优化的集合库吗？比如谷歌的，或者阿帕奇的。

编辑：

你有点证实了我的疑虑：

我是否会在尝试并行化的过程中得到提升？也许可以使用一个计算多对夫妻相似性的执行者池。但我不知道同步和数据结构上的锁是否最终会减慢它的速度。

利用这两种内容的标签图的点积计算相似度。地图是两个HashMap<Tag, Float>..。此外，我已经在TLongFloatHashMap中缓存了相似之处(来自特洛伊集合)，以避免在以后的迭代中重新计算它，在迭代中，Long键被计算为两个内容的哈希代码(对于这对内容是唯一的，以便hash(c1, c2) == hash(c2, c1))，因此其他的内容都已经调优足够了。

EDIT2:

为了让你更好地理解，我会发布一些代码。这用于计算用于存储两个元素之间的相似性的散列：

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

在阅读了http://nlp.stanford.edu/IR-book/information-retrieval-book.html的第6章之后，我得到了以下的想法

    public class WHN implements Comparable<WHN>{
        private HierarchNode node;
        private float weight;

        public HierarchNode getNode() {return node;}
        public float getWeight() {return weight;}

        public WHN(HierarchNode node, float weight) {this.node = node;this.weight = weight;}

        public int compareTo(WHN o) {return Float.compare(this.weight, o.weight); }
    }

    Map<Tag,<SortedMap<Float,HierarchNode>> map = new HashMap<Tag,List<WHN>> 
    for (HierarchNode n : cluster){
    for (Map.Entry tw : n.tags.entrySet()){
        Tag tag = tw.getKey();
        Float weight = tw.getValue();
        if (!map.ContainsKey(tag)){
            map.put(tag,new ArrayList<WHN>();
        }
        map.get(tag).add(new WHN(n,weight));
    }
    for(List<WHN> l: map.values()){
        Collections.Sort(l);
    }
}

然后，对于每个节点:您可以将搜索限制在每个标记的N个最高权重元素的联合(称为冠军列表)上。

或者，您可以为每个节点保留一个时态点积，并为每个标记更新点积，但只能循环遍历权重高于原始节点权重的某个部分的节点(您可以使用Collection.binarySearch找到开始)。

我建议你读这本书的其余部分，因为它可能包含一个更好的算法。

Answer 2

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

Answer 3

冒着声明显而易见的风险，您可能会通过使用这个伪代码来加快速度：

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

merge the two clusters

不过它仍然是O(n²)。如果需要将每个元素与每个其他元素进行比较，以找出哪一对最接近，则不能超过O(n²)。

尽管如此，如果您多次调用这些结果，那么在一个可排序的映射中缓存这些结果就可以找到优化。

编辑:如果相似性是相当简单的东西(例如，一维值，例如高度)，那么您可以首先对数组中的项进行排序，因此该元素最类似于element1，后者最类似于元素或element2。在这种情况下，您可以加速到O(n lg n)。

EDIT2:给定相关代码，您的基准测试结果非常可疑。我无法想象，在这种情况下，这两种情况比调用相关代码所花费的时间更长(即使假设缓存大部分时间都被击中)，这也称为O(n²)时间。另外，如果get()是瓶颈，spong在首先将这些转换为数组方面做得很好。