Java: ArrayList узкое место

Question

при профилировании приложения Java, которое вычисляет иерархическую кластеризацию тысяч элементов. Я понял, что ArrayList.get занимает половину процессора, необходимый в части кластеризации исполнения.

Алгоритм ищет более двух аналогичных элементов (так что O (п * (п + 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 в любом случае ..

В противном случае я должен попробовать другие библиотеки коллекции, которые более оптимизированной? Как один Google, или апача один ..

EDIT:

вы несколько подтверждающие мои сомнения :(

ли я получить импульс в Perfomance пытается распараллелить вещи Может быть, используя пул? исполнители, которые вычисляют сходство более чем на одной паре, но я не знаю, закончится ли синхронизация и блокировка на структурах данных.

Сходство рассчитывается с использованием точечного произведения карт тегов двух содержимого. На картах указаны два HashMap<Tag, Float> .. Кроме того, я уже кеширую сходства в TLongFloatHashMap (от коллекции Trove), чтобы избежать повторного вычисления его в последующих итерациях, в которых ключ 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

я получил следующую мысль после прочтения главы 6 из http://nlp.stanford.edu/IR-book/information-retrieval-book.html

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.b inarySearch)

Предлагаю вам прочитать остальную часть книги, так как она может содержать лучший алгоритм.

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²).

это сказал, если вы звоните это несколько раз, то есть оптимизация можно найти в кэшируют эти результаты в сортируемой карте.

EDIT: I f сходство - это нечто довольно простое (например, одномерное значение, такое как высота), вы можете сначала отсортировать элементы в массиве, чтобы элемент [0] был наиболее похож на элемент [1], который наиболее похож на элемент [0] или элемент [2]. В этом случае вы можете получить скорость до O(n lg n).

EDIT2: Учитывая ваш корреляционный код, результаты теста очень подозрительны. Я не могу представить себе ситуацию, в которой эти два получат больше времени, чем вызов кода корреляции (даже если кеш попадает в подавляющее большинство времени), который также называется O(n²) раз. Также spong делает очень хороший момент об их преобразовании в массивы, если get() является узким местом.

Answer 4

В вашем коде не так много сложных операций. В основном простое число читает/проверяет/записывает. Они удивительно быстры.

Вопрос заключается в том, что .get() вызов функции - это будет гораздо медленнее по сравнению с простым +, = или <= операции. Если это слишком медленно для вас, вы должны начать использовать реальные массивы или (как утверждают другие), сначала оптимизируйте свой алгоритм.

Answer 5

ArrayList.get - это инструкция if, за которой следует доступ к массиву. Там не так много оптимизировать. ArrayList.get занимает половину времени выполнения, потому что вы ничего не делаете. Важным фактором за прошедшее время является количество итераций, а не то, что находится внутри цикла.

Answer 6

Нет такой вещи, как O (n * (n + 1)/2). Ваш алгоритм равен O (n). См. Plain english explanation of Big O для более подробного объяснения.

Ben правильный: вы можете уменьшить get() звонки, получив i-й элемент за пределами внутреннего цикла.

Что вы действительно ищете, это то, что улучшается на O (n), и для этого требуется возможность сделать дополнительные предположения об элементах. Это зависит от того, что вы подразумеваете под «подобием».

два общих подхода:

• Сортировка списков и слияния. В целом это O (n log n);
• Поместите один список в Map, который имеет (почти) постоянный поиск. Это может уменьшить алгоритм в любом месте между O (n) и O (n log n) в зависимости от типа Map и характера обхода.

Но все это зависит от того, что вы подразумеваете под «подобием».

Answer 7

Если вы повторяете этот процесс, каждый раз находясь в наиболее близкой к вам паре, вам может понадобиться создать карту из i, j-пар для мер подобия - в зависимости от того, насколько процессор-интенсивный вычисляет сходство , и сколько у вас предметов и сколько у вас памяти.

Answer 8

Алгоритмическая эффективность в сторону, вы вызываете get слишком много раз. В настоящее время get называется (в порядке) 2*size*size раз. Его следует называть size+size*size/2 раз. Это только изменяет константы, но мне кажется, что вам нужно всего лишь позвонить get примерно в одну четверть столько, сколько вы сейчас.

Try:

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

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

    ... etc ... 

В зависимости от величины clusters.size(), вы могли бы еще больше уменьшить константы, выполнив:

HierarchNode[] clusterArr = clusters.toArray(new HierarchNode[clusters.size()]); 

, а затем с помощью clusterArr[j] и clusterArr[k] вместо clusters.get(k) и т.д.

(названия слегка искалечены во избежание обертывания линии)

Answer 9

Локальная оптимизация не будет учитывать много по сравнению с изменением алгоритма. Мы не уверены, что вы хотели сделать на первом месте, и поэтому мы не можем дать вам лучший/хороший ответ.

Из того, что я вижу, кажется, у вас довольно много элементов, и каждый из них содержит список (тег, вес). Итак, здесь неясно:

• «Вес» рассчитан из другого места или является статичным для соответствующего тега?
• Можем ли мы использовать Integer вместо Float, чтобы числовые вычисления были быстрее? Кстати, в вашей программе есть ошибка, что вы сравниваете одинаковое число Float (я имею в виду max == 1.0f). Однако в этом случае вы должны использовать> или < с прецизионным диапазоном.

Если есть «да», у нас есть локальная оптимизация. Но нет, пожалуйста, рассмотрите следующие методы (которые также зависят от ваших реальных данных и реальной проблемы):

• Будет ли сортировка всех элементов помощи? Это в некоторых случаях увеличивает вероятность вычисления отсечки ...
• Использовать метод динамического программирования, например. инкрементно обновлять корреляции. Вам нужно будет перебирать все элементы по одному для каждого обновления, но сэкономить много времени позже.
• Параллельный код (работает на нескольких потоках), поэтому он использует преимущества многоядерной среды. Если вы беспокоитесь о блокировке, попробуйте вместо этого использовать lock-free Map/List.