代码之家 › 专栏 › 技术社区 › Ido Weinstein

将大量排序映射合并到一个排序的MAP- Java中提高性能

sortedmap merge performance java

0

Ido Weinstein · 技术社区 · 15 年前

我有一个方法将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 回复 | 直到 15 年前

1

2

Michael Borgwardt 15 年前

我看不出您的代码有什么问题;您真正能做的就是尝试 SortedMap . 第一个是 ConcurrentSkipListMap 然后看看 Commons Collections , Google Collections 和 GNU Trove . 后者可以产生非常好的结果,尤其是当您的地图的键和值是原始类型时。

2

Fried Hoeben 15 年前

是否要求输入为SortedMap?对我来说,如果输入只是一个集合或列表,那么看起来会更容易。这可能会加快创建输入,并可能使对所有包含的映射的迭代更快。

除此之外,我认为提高这段代码性能的最有可能的途径是提高CompareTo()在被合并的排序映射中实现值的速度。

3

1

nd. 15 年前

你的代码是最好的。但是,在我看来,数据结构的总体设计需要进行一些彻底的修改:您正在使用 SortedMap<?, SortedMap<?, ?> ,但未使用父映射的键。

要用嵌套元素表示树吗?您的任务是展平树吗?如果是这样,请创建支持您的方法的树类,或者使用智能方法合并键:

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 用作排序映射键的项与其他项比较 内斯迪克 对象,通过比较其每个条目。存在于所有元素中但条目数更多的嵌套键被认为更大。因此,你的关系是这样的:

嵌套键(1、2、3)<嵌套键(1、2、4)
嵌套键(1、3、3)<嵌套键(2、1、1)
嵌套键(1、2、3)<嵌套键(2)

如果只使用一个使用NestedKey作为其键的SortedMap,则 .values() set自动返回所有条目,变平。但是,如果您只想使用sortedmap的一部分,那么必须使用 .subMap . 例如,如果您想要所有嵌套键在2到3之间的条目,请使用 .subMap(new NestedKey(2), new NestedKey(3))