java - TreeSet 与 Java 8 Streams 性能对比

Question

哪种方式处理不同且已排序的集合最有效？

1. 使用 TreeSet 增强循环

Set<MyObj> ret = new TreeSet<>();
for (Foo foo : foos)
    ret.add(new MyObj(foo));

---

2. 简单流

List<MyObj> ret = foos.stream().map(MyObj::new)
                      .distinct().sorted()
                      .collect(Collectors.toList());

---

3. TreeSet 流

Set<MyObj> ret = foos.stream().map(MyObj::new)
                     .collect(Collectors.toCollection(TreeSet::new));

---

第一种方式似乎最不优雅但易于阅读。第二种方式让我担心 distinct 和 sorted 会处理流两次。最后一种方式感觉还可以，但是流中的 TreeSet 开销是多少？

有什么线索吗？谢谢。

Answer 1

初步分析

从 Stream API 源代码来看，我的初步猜测是:对于许多项目，简单流 (2) 应该是最快的，明显优于 TreeSet 版本 (1)，然后 TreeSet 流 (3) 应该稍微跟上在后面。对于短数据集，(1) 可能比 (2) 好，后者又比 (3) 好，因为 Stream 创建会增加一些开销。 distinct-sorted 流的工作原理大致如下:

Set<MyObj> set = new HashSet<>();
List<MyObj> result = new ArrayList<>();
for (Foo foo : foos) {
    MyObj myObj = new MyObj(foo);
    if(set.add(myObj))
        result.add(myObj);
}
result.sort(null);
return result;

让我们将此实现添加为 (4)。它使用 HashSet 检查结果是否不同，将它们添加到中间容器中，然后对其进行排序。这应该比维护 TreeSet 更快，因为我们不需要在每次插入后保持顺序(TreeSet 需要这样做，可能会重新平衡树)。实际的 Stream 实现效率会稍低一些，因为它不能就地对结果列表进行排序。相反，它会创建中间容器，对其进行排序，然后使用一系列 list.add 调用将结果转储到最终列表中。

结果可能取决于初始 foos 集合中的元素数量以及不同元素的数量。我称之为多样性:多样性 = 1 表示大致每个元素都不同； diversity = 0.5 表示每个元素大约重复两次。此外，结果可能在很大程度上取决于初始元素顺序:当输入数据被预排序或接近预排序时，排序算法可能会快一个数量级。

实验设置

所以让我们按以下方式参数化我们的测试:

• 大小(foos 中的元素数量):10、1000、100000
• 多样性(不同部分的分数):1、0.5、0.2
• 预排序:真、假

我假设 Foo 只包含一个 int 字段。当然，结果可能在很大程度上取决于 Foo 类的 compareTo、equals 和 hashCode 实现，因为版本 (2 ) 和 (4) 使用 equals 和 hashCode 而版本 (1) 和 (3) 使用 compareTo。我们将简单地做到这一点:

@Override
public int hashCode() {
    return x;
}

@Override
public boolean equals(Object o) {
    return this == o || (o != null && getClass() == o.getClass() && x == ((Foo) o).x);
}

@Override
public int compareTo(Foo o) {
    return Integer.compare(x, o.x);
}

可以通过以下方式生成预排序元素:

foos = IntStream.range(0, size)
                .mapToObj(x -> new Foo((int)(x*diversity)))
                .collect(Collectors.toList());

可以通过以下方式生成随机元素:

foos = new Random().ints(size, 0, (int) (size * diversity))
                   .mapToObj(Foo::new)
                   .collect(Collectors.toList());

使用JMH 1.13和JDK 1.8.0_101，VM 25.101-b13 64bit进行测量

结果

预排序(所有时间均以 μs 为单位):

diversity size      (1)      (2)      (3)      (4)
  1         10      0.2      0.5      0.3      0.2
  1       1000     48.0     36.0     53.0     24.2
  1     100000  14165.7   4759.0  15177.3   3341.6
0.5         10      0.2      0.3      0.2      0.2
0.5       1000     36.9     23.1     41.6     20.1
0.5     100000  11442.1   2819.2  12508.7   2661.3
0.2         10      0.1      0.3      0.2      0.2
0.2       1000     32.0     13.0     29.8     16.7
0.2     100000   8491.6   1969.5   8971.9   1951.7

未预分类:

diversity size      (1)      (2)      (3)      (4)
  1         10      0.2      0.4      0.2      0.3
  1       1000     72.8     77.4     73.6     72.7
  1     100000  21599.9  16427.1  22807.8  16322.2
0.5         10      0.2      0.3      0.2      0.2
0.5       1000     64.8     46.9     69.4     45.5
0.5     100000  20335.2  11190.3  20658.6  10806.7
0.2         10      0.1      0.3      0.2      0.2
0.2       1000     48.0     19.6     56.7     22.2
0.2     100000  16713.0   5533.4  16885.0   5930.6

讨论

我最初的猜测大体上是正确的。对于预排序数据，当我们有 100,000 个元素时，(2) 和 (4) 会好几倍。当我们有很多重复项时，差异会变得更大，因为它们不会增加排序时间，而且重复插入到 HashSet 比重复插入到 TreeSet 更有效。对于随机数据，与 TimSort 算法(Java 用于对列表和数组进行排序)相比，TreeSet 性能对输入数据顺序的依赖性要小得多。对于小型数据集，简单的 TreeSet 速度很快，但使用 (4) 版本也可能具有竞争力。

基准测试的源代码和原始结果可用 here .