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

Question

У меня есть метод, который получает 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;
}

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

Answer 1

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

Answer 2

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

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

Answer 3

Ваш код настолько хорош, насколько это возможно. Тем не менее, мне кажется, что общий дизайн структуры данных нуждается в пересмотре: вы используете 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() set автоматически возвращает все записи, расплющенные. Однако, если вы хотите использовать только части SortedMap, то вы должны использовать .subMap, Например, если вы хотите, чтобы все записи с NestedKeys находились в диапазоне от 2 до 3, используйте .subMap(new NestedKey(2), new NestedKey(3))