set集合中添加元素最快的方法

Question

我有一个任务要在树集中添加 > 10000000 个序列元素。

如果我使用

for (long index = 0; index < 10000000; index++)
    {
        result.add(index);
    }

需要 8083 毫秒。有什么解决方案可以提高这个任务的性能吗？

https://github.com/cyberterror/TestRanges

P.S。目前最快的方法是：List<Integer> range = IntStream.range(0, 10000000).boxed().collect(Collectors.toList()); 结果为 ~ 370 ms

Answer 1

您已经以正确的顺序添加项目，TreeSet 会在每个添加的项目之后自行排序，这很复杂，LinkedHashSet 只是保持插入顺序。

因此，如果您确实需要一个 Set，请像此处那样使用 LinkedHashSet 实现：

Set<Long> result = new LinkedHashSet<Long>();
for (Long index = 0L; index != 10000000L;) { //Avoid autoboxing
    result.add(index++);
}

阅读此处： https://dzone.com/articles/hashset-vs-treeset-vs

Answer 2

TreeSet 是一个平衡的红黑树。每次添加新项目时，树都会平衡，这需要花费很多时间。尝试以不同的顺序添加项目；实际上是这样的顺序：

5 000 000 - 0 和 10 000 000 的中间（您的设置大小为 10 000 000）
2 500 000 - 0 和 5 000 000 的中间
7 500 000 - 5 000 000 和 10 000 000 的中间
0和2 500 000中间的数字
2 500 000 和 5 000 000 中间的数字
5 000 000 和 7 500 000 中间的数字
7 500 000 和 10 000 000 中间的数字
等等

这样你就可以让你的树始终保持平衡，并且不会执行额外的操作（平衡树）。只需确保计算下一个要添加的数字的算法不太复杂即可。

Answer 3

你真的需要collection吗？为了什么目的，如果是这样？实际上，使用普通数组可以大大提高性能。

   long [] ar = new long[10000000];
    for (int i = 0; i < 10000000; i++) {
        ar[i] = (long )i;
    }

...

BUILD SUCCESS
------------------------------------------------------------------------
Total time: 0.553 s

UPD: 实际上，可以使用 Arrays 实用程序对数组执行大多数操作

long [] ar = new long[10000000];
for (int i = 0; i < 10000000; i++) {
    ar[i] = (long )i;
}

long[] copyOfRange = Arrays.copyOfRange(ar, 50000, 1000000);

...

BUILD SUCCESS
------------------------------------------------------------------------
Total time: 0.521 s

Answer 4

尝试 HPPC：Java

的高性能原始集合

许可证：Apache 许可证 2.0

<dependency>
  <groupId>com.carrotsearch</groupId>
  <artifactId>hppc</artifactId>
  <version>0.7.1</version>
</dependency>

LongHashSet 在 1190 毫秒内执行：

LongSet result = new LongHashSet();
for (Long index = 0L; index < 10000000L;) {
  result.add(index++);
}

LongScatterSet 在 850 毫秒内执行：

LongSet result = new LongScatterSet();
for (Long index = 0L; index < 10000000L;) {
  result.add(index++);
}

set集合中添加元素最快的方法

The fastest way to add elements in set collection

java

treeset