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