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会有什么开销吗？

任何提示？谢谢。

- Guillaume F.

---

你的集合为什么是类型为 Foo，而它们包含的是 MyObj？ - user3707125

TreeSet没有使用int和float的构造函数。你确定你不是想说HashSet吗？ - F. Lumnitz

在示例2中，为什么要调用.distinct？你说“...处理不同的...”，那么难道不是所有的都已经是不同的了吗？ - Todd Sewell

性能在这里真的很重要吗？确保你不会陷入过早优化的陷阱。 - Todd Sewell

@GuillaumeF。你能提供第一个案例的确切代码而不进行简化吗？不清楚new TreeSet(size, 1.0f)是什么意思。 - ZhekaKozlov

Answer 1

初步分析

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

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 可能会重新平衡树）。实际的流实现可能会更少效，因为它不能就地对结果列表进行排序。相反，它会创建中间容器，对其进行排序，然后使用一系列 list.add 调用将结果转储到最终列表中。

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

实验设置

因此让我们按以下方式参数化我们的测试：

• 大小（foos 中的元素数）：10、1000、100000
• 多样性（不同元素的比例）：1、0.5、0.2
• 预排序：true、false

我假设 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 64 位进行测量

结果

预排序（所有时间单位均为μ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

讨论

我的初始猜测普遍是正确的。对于预排序的数据（2）和（4），当我们有100,000个元素时，它们的效率比较高。当我们有许多重复项时，差异变得更加明显，因为它们不会增加排序时间，而将重复项插入到HashSet中比将重复项插入到TreeSet中更加高效。对于随机数据，差异并不那么显著，因为TreeSet的性能与输入数据的顺序关系远不如TimSort算法（Java用于对列表和数组进行排序的算法）。对于小数据集，简单的TreeSet很快，但使用（4）版本也可能具有竞争力。

基准测试的源代码以及原始结果可以在这里找到。

- Tagir Valeev

---

显然，您随意修改了(1)，因为问题的代码甚至无法编译。这不仅仅是一个笔误，因为问题甚至提到了TreeSet不存在的“maximum load”。所以您测量的不是OP描述的内容。除此之外，这些变体是不可比较的，因为它们执行完全不同的操作，有些产生List，有些产生TreeSet。由于这些不同的结果可能会极大地影响后续操作的性能，因此将它们的创建孤立地进行比较是没有用的。 - Holger

关于(4)，我会先填充HashSet，然后通过new ArrayList<>(set)一次性创建ArrayList。这样可以避免对ArrayList进行容量增加操作。 - Holger

@Holger，我在（4）中想大致演示流的工作原理，而不是建议最优解决方案。事实上，这个问题有一些不清楚的地方。你可以考虑在问题评论中建议编辑OP。 - Tagir Valeev

@TagirValeev，非常感谢您提供的所有细节。我从问题中删除了自定义构造函数(1)，所以现在您的答案完全适用。我按照您的示例测试了各种情况，并成功将代码性能提高了约40％，非常好。干杯！ - Guillaume F.

Answer 2

没有分析输入很难给出好的答案。不管怎样，我会分享我的结果：

我将Foo设为一个包含单个long的容器，并将MyObj设为单个Foo的容器。此外，我使所有测试都以将数据复制到普通数组中结束。我还添加了两种方法：

4)。简单数组

@Benchmark
public void simpleArray(Blackhole bh) {
    MyObj[] ret = new MyObj[foos.size()];
    for (int i=0;i<foos.size();i++)
        ret[i] = new MyObj(foos.get(i));
    Arrays.sort(ret);
    int lastDistinct = 0;
    for (int i = 1; i < ret.length; i++) {
        if (ret[i].equals(ret[lastDistinct])) {
            continue;
        }
        lastDistinct++;
        ret[lastDistinct] = ret[i];
    }
    MyObj[] ret2 = new MyObj[lastDistinct + 1];
    System.arraycopy(ret, 0, ret2, 0, lastDistinct + 1);
    bh.consume(ret2);
}

5). 翻转了（2）中distinct 和 order的顺序：

@Benchmark
public void simpleStream_distinctAfterSort(Blackhole bh) {
    List<MyObj> ret = foos.stream().map(MyObj::new)
            .sorted().distinct()
            .collect(Collectors.toList());
    bh.consume(ret.toArray(new MyObj[ret.size()]));
}

测试设置:

public static final int MAX_SIZE = 10_000;
public static final long ELEM_THRESHOLD = MAX_SIZE * 10;
private List<Foo> foos;

@Setup
public void init() throws IOException, IllegalAccessException, InstantiationException {
    foos = new ArrayList<>(MAX_SIZE);
    for (int i = 0; i < MAX_SIZE; i++) {
        foos.add(new Foo(ThreadLocalRandom.current().nextLong(ELEM_THRESHOLD)));
    }
}

现在来看不同大小和阈值的结果：

Size=10_000
Threshold=Size*10
Benchmark                                         Mode  Cnt    Score   Error  Units
StreamBenchmark5.enhancedLoop_TreeSet            thrpt    2  478,978          ops/s
StreamBenchmark5.simpleArray                     thrpt    2  591,287          ops/s
StreamBenchmark5.simpleStream                    thrpt    2  407,556          ops/s
StreamBenchmark5.simpleStream_distinctAfterSort  thrpt    2  533,091          ops/s
StreamBenchmark5.treeSetStream                   thrpt    2  492,709          ops/s

Size=10_000
Threshold=Size/10
StreamBenchmark5.enhancedLoop_TreeSet            thrpt    2   937,908          ops/s
StreamBenchmark5.simpleArray                     thrpt    2   593,983          ops/s
StreamBenchmark5.simpleStream                    thrpt    2  3344,508          ops/s
StreamBenchmark5.simpleStream_distinctAfterSort  thrpt    2   560,652          ops/s
StreamBenchmark5.treeSetStream                   thrpt    2  1000,585          ops/s

Size=500_000
Threshold=Size*10
Benchmark                                         Mode  Cnt  Score   Error  Units
StreamBenchmark5.enhancedLoop_TreeSet            thrpt    2  1,809          ops/s
StreamBenchmark5.simpleArray                     thrpt    2  4,009          ops/s
StreamBenchmark5.simpleStream                    thrpt    2  2,443          ops/s
StreamBenchmark5.simpleStream_distinctAfterSort  thrpt    2  4,141          ops/s
StreamBenchmark5.treeSetStream                   thrpt    2  2,040          ops/s

Size=500_000
Threshold=Size/10
Benchmark                                         Mode  Cnt   Score   Error  Units
StreamBenchmark5.enhancedLoop_TreeSet            thrpt    2   5,724          ops/s
StreamBenchmark5.simpleArray                     thrpt    2   4,567          ops/s
StreamBenchmark5.simpleStream                    thrpt    2  19,001          ops/s
StreamBenchmark5.simpleStream_distinctAfterSort  thrpt    2   4,840          ops/s
StreamBenchmark5.treeSetStream                   thrpt    2   5,407          ops/s

Size=1_000_000
Threshold=Size/100
Benchmark                                         Mode  Cnt   Score   Error  Units
StreamBenchmark5.enhancedLoop_TreeSet            thrpt    2   4,529          ops/s
StreamBenchmark5.simpleArray                     thrpt    2   2,402          ops/s
StreamBenchmark5.simpleStream                    thrpt    2  35,699          ops/s
StreamBenchmark5.simpleStream_distinctAfterSort  thrpt    2   2,232          ops/s
StreamBenchmark5.treeSetStream                   thrpt    2   4,889          ops/s

根据重复的数量不同，可以看到最好的算法也会有所变化。最平衡的方法是TreeSet（3），然而最快的方法几乎总是简单的流式处理（使用与输入数据对应的order和distinct）。

如果您愿意尝试一下，这里是测试源代码。您需要JMH。

- user3707125

---

非常感谢您提供如此详细的答案，您和Tagir都非常有帮助。干杯！ - Guillaume F.