2

我很快写了这个片段来完成这项工作

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

粗略地说，当大小翻倍时，时间翻倍。我会采用线性增长，但仍然想知道，我们能做得更好吗？是否可以使用恒定时间映射事物？

4

3 回答 3

3

我所看到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-08T18:35:08.573 回答
1

根据@Quoi的回答，不知道在空检查之后保存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-08T19:02:25.367 回答
0

除非你能改变底层的数据结构，否则你不能比线性时间做得更好。

考虑一下：您有一个包含n 个唯一条目的列表。要映射每个必须访问的一个。假设访问成本为 1。那么必须有n次访问。因此，正如您的基准测试所指出的那样，您的复杂性为 at n * 1 = n或线性时间。

现在，如果你有一个数据结构，可以共享数据但同时提供两个接口，那么你可以实现在两者之间切换的恒定时间。显然，您的静态类型与您的示例不同。

于 2013-03-08T18:40:17.650 回答