如何将KVP列表映射到Map<Key，List<Value>> ..快地
如何将KVP列表映射到Map<Key，List<Value>> ..快地
提问于 2013-03-09 02:31:17
我很快就写了这段代码来完成这项工作。
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的随机数据时，我得到了以下性能(平均100,000次运行)
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粗略地说，当大小加倍时，时间也会加倍。我会采用线性增长，但仍然想知道，我们能做得更好吗？有没有可能使用常量时间来映射事物？
Stack Overflow用户
发布于 2013-03-09 02:40:18
除非你能改变底层的数据结构，否则你不能做得比线性时间更好。
考虑一下:您有一个包含n个唯一条目的列表。要映射每一个，则必须访问其中一个。假设访问开销为1，那么必须有n次访问。因此，正如您的基准测试所指出的那样，您具有at n *1=n的复杂性，或者线性时间。
现在，如果你有一个可以共享数据的数据结构，但同时提供了两个接口，那么你就可以在两者之间实现恒定的时间切换。显然，你会有不同于你的例子的静态类型。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/15300863
复制相关文章
相似问题
腾讯云开发者
