Повышение производительности объединения множества отсортированных карт в одну отсортированную карту - Java - PullRequest
Новая
       15

Повышение производительности объединения множества отсортированных карт в одну отсортированную карту - Java

0 голосов
/ 16 декабря 2009

У меня есть метод, который получает SortedMap в качестве входных данных, эта карта содержит много объектов SortedMap, результатом этого метода должен быть один SortedMap, содержащий все элементы карт, хранящихся во входной карте. метод выглядит так: 

private SortedMap mergeSamples(SortedMap map){
  SortedMap mergedMap = new TreeMap();
  Iterator sampleIt = map.values().iterator();
  while(sampleIt.hasNext())
  {
    SortedMap currMap = (SortedMap) sampleIt.next();
    mergedMap.putAll(currMap);
  }
  return mergedMap;
}

Это убийца производительности, что я могу улучшить здесь?

Ответы [ 3 ]

2 голосов
/ 16 декабря 2009

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

Кроме того, я полагаю, что наиболее вероятным источником повышения производительности этого кода является повышение скорости реализации CompareTo () значений в объединяемых отсортированных картах.

2 голосов
/ 16 декабря 2009

Я не вижу ничего плохого в вашем коде; все, что вы можете сделать, это попробовать альтернативные реализации SortedMap. Сначала будет ConcurrentSkipListMap , а затем посмотрите Коллекции общих , Коллекции Google и GNU Trove . Последнее может дать очень хорошие результаты, особенно если ключи и значения ваших карт являются примитивными типами.

1 голос
/ 16 декабря 2009

Ваш код так же хорош, как и получает. Тем не менее, мне кажется, что общий дизайн структуры данных нуждается в некоторой переработке: вы используете SortedMap<?, SortedMap<?, ?>, но ключи родительской карты не используются.

Вы хотите выразить дерево с помощью вложенных элементов этим, и ваша задача состоит в том, чтобы сгладить дерево? Если это так, либо создайте класс Tree, который поддерживает ваш подход, либо используйте интеллектуальный способ объединения ключей: 

public class NestedKey implements Comparable<NestedKey> {

  private Comparable[] entries;

  public NestedKey(Comparable... entries) {
    assert entries != null;
    this.entries = entries;
  }

  public int compareTo(NestedKey other) {
    for(int i = 0; i < other.entries.length; i++) {
      if (i == entries.length)
        return -1; // other is longer then self <=> self is smaller than other
      int cmp = entries[i].compareTo(other.entries[i]);
      if (cmp != 0)
        return cmp;
    }
    if (entries.length > other.entries.length)
      return 1; // self is longer than others <=> self is larger than other
    else
      return 0;
  }

}

Запись NestedKey, используемая в качестве ключа для SortedMap, сравнивается с другими NestedKey объектами путем сравнения каждой из ее записей. Предполагается, что NestedKeys, присутствующие во всех элементах, но имеющие больше записей, будут больше. Таким образом, у вас есть такие отношения:

  • NestedKey (1, 2, 3)
  • NestedKey (1, 3, 3)
  • NestedKey (1, 2, 3)

Если вы используете только один SortedMap, который использует NestedKey в качестве ключей, то его набор .values() автоматически возвращает все записи, сглаженные. Однако, если вы хотите использовать только части SortedMap, вы должны использовать .subMap. Например, если вы хотите, чтобы все записи с NestedKeys находились в диапазоне от 2 до 3, используйте .subMap(new NestedKey(2), new NestedKey(3))

...