提高将大量排序映射合并为一个排序映射的性能 - 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 Collections、Google 收藏和 GNU Trove 。后者可以产生非常好的结果，特别是当映射的键和值是原始类型时。

Answer 2

输入是否需要为 SortedMap？对我来说，如果输入只是一个集合或列表，这似乎会更容易。这可能会加快创建输入的速度，并且可能会使所有包含的地图的迭代速度更快。

除此之外，我认为提高此代码性能的最可能来源是提高正在合并的排序映射中的值的compareTo() 实现的速度。

Answer 3

你的代码已经尽善尽美了。但是，在我看来，数据结构的整体设计需要进行一些彻底修改：您正在使用 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;
  }

}

用作 SortedMap 的键的 NestedKey 条目与其他 NestedKey 条目进行比较> 通过比较其每个条目来对象。存在于所有元素中但具有更多条目的 NestedKey 被假定为更大。因此，您有这样的关系：

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

如果您仅使用一个使用 NestedKey 作为其键的 SortedMap，则其 .values() 集会自动返回所有条目（展平）。但是，如果您只想使用 SortedMap 的部分内容，则必须使用 .subMap。例如，如果您希望所有条目都包含 2 到 3 之间的 NestedKey，请使用 .subMap(new NestedKey(2), new NestedKey(3))