如何映射KVP列表地图<重点，列出<Value>> ..快

我很快就写了这个片段来完成这项工作如何映射KVP列表地图<重点，列出<Value>> ..快

private void map() { 
    for (KVPair kvPair : content) { 
     String k = kvPair.getKey(); 
     String v = kvPair.getValue(); 

     if (mappedContent.containsKey(k)) { 
      List<String> values = mappedContent.get(k); 
      values.add(v); 
     } else { 
      List<String> values = new ArrayList<>(); 
      values.add(v); 
      mappedContent.put(k, values); 
     } 
    } 
}

它的工作原理和使用时跑了1K，2K，4K和8K的随机数据，我得到以下性能（平均10万个奔跑）

Running with 1,000 pairs 
    [perfRun] 100000 iterations took 3 seconds 
    [perfRun] Run time: 3758786000 ns. 1 iteration takes 37 us 
Running with 2,000 pairs 
    [perfRun] 100000 iterations took 6 seconds 
    [perfRun] Run time: 6675544000 ns. 1 iteration takes 66 us 
Running with 4,000 pairs 
    [perfRun] 100000 iterations took 13 seconds 
    [perfRun] Run time: 13337145000 ns. 1 iteration takes 133 us 
Running with 8,000 pairs 
    [perfRun] 100000 iterations took 27 seconds 
    [perfRun] Run time: 27109480000 ns. 1 iteration takes 271 us

粗略地讲，当大小双打，双打的时间。我会采取线性增长的方式，但我们仍然想，我们可以做得更好吗？用恒定的时间映射东西是否可能？

来源

2013-03-08 JAM

也许如果你告诉我们你在做什么。 – 2013-03-08 18:34:07

您是否尝试使用CommonValueMultiValueMap而不是滚动自己的？ – Alb 2013-03-08 18:34:33

，并不确切地知道，如果它的确与众不同，保存else块空校验

for (KVPair kvPair : content) { 
    String k = kvPair.getKey(); 
    List<String> values = mappedContent.get(k); 
    if (values == null) { 
     values = new ArrayList<>(); 
     mappedContent.put(k, values); 
    } 
    values.add(kvPair.getValue()); 
}

也可以使一个列表可能有多大成为一些假设后，所以您将该大小传递给列表构造函数并保存列表需要重新调整大小的时间。如果内存不是问题，则可以将content.size() + 1作为列表的大小。

来源

2013-03-08 19:02:25 A4L

表演双打。谢谢 – JAM 2013-03-08 19:42:57

太棒了！但你能告诉我你做了什么来获得这种提升吗？大小猜测还是没有其他的？ – A4L 2013-03-08 19:47:50

我运行了1,2,4,8000个随机生成的对的样本。仅对此方法计时 – JAM 2013-03-08 19:50:54

我所看到的，mappedContent.containsKey(k)其不必要的这大致需要BigO(n)，您可以通过null检查逃跑，

for (KVPair kvPair : content) { 
     String k = kvPair.getKey(); 
     String v = kvPair.getValue(); 
     List<String> values = mappedContent.get(k); 
     if (values!=null) { 
      values.add(v); 
     } else { 
      values = new ArrayList<>(); 
      values.add(v); 
      mappedContent.put(k, values); 
     } 
}

来源

2013-03-08 18:35:08

除非你可以改变底层数据结构，不，你不能这样做比线性时间更好。

考虑这个：你有一个列表n唯一的条目。映射必须访问的每一个。假设访问成本为1.那么必须有访问权限访问权限。因此，您的复杂度为n * 1 = n或您的基准指出的线性时间。

现在，如果你可以有一个数据结构来共享数据，但同时提供两个接口，那么你可以实现两者之间的切换。显然你会有不同于你的例子的静态类型。根据@ Quoi的回答

来源

2013-03-08 18:40:17 vossad01

如何映射KVP列表地图<重点，列出<Value>> ..快

回答

相关问题