Java集合性能

Question

我刚试了一个关于礼貌的测试例子。任务是：“.给定N个整数数组A，返回A中没有出现的最小正整数(大于0)”。

加：

• N是范围1.100,000内的整数；
• 数组A的每个元素都是−1,000,000.1,000,000范围内的整数。

我的第一次尝试是典型的Java 8解决方案：

public int solution(int[] A) {

     Set<Integer> l = Arrays
            .stream(A)
            .boxed()
            .filter(i -> i > 0)
            .collect(Collectors.toSet());

    return IntStream
            .iterate(1, a -> a + 1)
            .filter(i -> !l.contains(i))
            .findFirst()
            .getAsInt();
}

所有的测试都是正确的，但是对中等大小的测试数组的测试遇到了超时。

第二次尝试(普通的旧java)：

public int solution(int[] A) {

    boolean[] B = new boolean[1000001];

    for (int a : A) {
        if (a > 0) {
            B[a] = true;
        }
    }

    for (int i = 1; i <= 1000000; i++) {
        if (!B[i]) {
            return i;
        }
    }

    return 1;
}

这个版本速度快得多，特别是对于短数组A。

问题：

• 我的第一次尝试是不是遗漏了什么？
• 有调整的选择吗？
• 对伪善的测试是否过早，实际上，这种差异预计会消失，几乎完全消失吗？
• 有谁有更好的Java 8解决方案吗？

测试结果第一版：

example1▶第一个示例测试✔OK 1. 0.108 s OK

example2▶第二个示例测试✔OK 1. 0.104 s OK

example3▶第三例测试✔OK 1. 0.104 s OK

extreme_single▶▶✔1. 0.100 s OK 2. 0.104 s OK 3. 0.104 s OK 4. 0.100 s OK

▶简单测试✔OK 1. 0.100 s OK 2. 0.104 s OK 3. 0.100 s OK

extreme_min_max_value极小和极大值✔OK 1. 0.100 s OK 2. 0.104 s OK

positive_only▶洗牌序列0.100，然后102.200✔OK 1. 0.100 s OK 2. 0.104 s OK

negative_only▶洗牌序列-100 . -1✔OK 1. 0.100 s OK

length=10005 (带负)✘超时错误运行时间: 0.136秒，时间限制: 0.100秒。1. 0.136 s超时错误，运行时间: 0.136秒，时间限制: 0.100秒.2. 0.128 s超时错误，运行时间: 0.128秒，时间限制: 0.100秒.3. 0.144 s超时错误，运行时间: 0.144秒，时间限制: 0.128秒.

large_1混沌+序列1，2，.，40000 (无负)✔OK 1. 0.588 s OK

large_2▶洗牌序列1，2，.，100000 (不减)✔OK 1. 0.748 s OK 2. 0.660 s OK

large_3▶混沌+多-1，1，2，3(含负)✔OK 1. 0.444 s OK

测试结果第二版：

example1▶第一个示例测试✔OK 1. 0.004 s OK

example2▶第二个示例测试✔OK 1. 0.004 s OK

example3▶第三例测试✔OK 1. 0.004 s OK

extreme_single▶▶✔1. 0.004 s OK 2. 0.008 s OK 3. 0.004 s OK 4. 0.008 s OK

▶简单测试✔OK 1. 0.004 s OK 2. 0.004 s OK 3. 0.008 s OK

extreme_min_max_value极小和极大值✔OK 1. 0.008 s OK 2. 0.004 s OK

positive_only▶洗牌序列0.100，然后102.200✔OK 1. 0.008 s OK 2. 0.004 s OK

negative_only▶洗牌序列-100 . -1✔OK 1. 0.008 s OK

length=10005 (与负)▶介质混沌序列✔OK 1. 0.024 s OK 2. 0.024 s OK 3. 0.032 s OK

large_1混沌+序列1，2，.，40000 (无负)✔OK 1. 0.220 s OK

large_2▶洗牌序列1，2，.，100000 (不减)✔OK 1. 0.244 s OK 2. 0.244 s OK

large_3▶混沌+多-1，1，2，3(含负)✔OK 1. 0.172 s OK

底线：，特别是小型数组的测试，只需简单的java，就快两个数量级。对于大型数组，它的“唯一”因子为3。

编辑：

根据这些评论，我试图深入研究这个问题，并尝试：

public int solution(int[] A) {

boolean[] B = new boolean[1000001];

for (int a : A) {
    if (a>0){
        B[a] = true;
    }
}

 return IntStream
        .iterate(1, a -> a + 1)
        .filter(i -> !B[i])
        .findFirst()
        .getAsInt();

}

结果：

example1▶第一个示例测试✔OK 1. 0.096 s OK

example2▶第二个示例测试✔OK 1. 0.096 s OK

example3第三个示例测试✔OK 1. 0.096 s OK折叠✔测试

extreme_single▶▶✔1. 0.096 s OK 2. 0.096 s OK 3. 0.096 s OK 4. 0.096 s OK

▶简单测试✔OK 1. 0.100 s OK 2. 0.096 s OK 3. 0.100 s OK

extreme_min_max_value极小和极大值✔OK 1. 0.096 s OK 2. 0.100 s OK

positive_only▶洗牌序列0.100，然后102.200✔OK 1. 0.096 s OK 2. 0.096 s OK

negative_only洗牌序列-100 . -1✔OK 1. 0.096 s OK折叠allPerformance测试

length=10005 (带负)✘超时错误运行时间: 0.116秒，时间限制: 0.112秒。1. 0.116 s超时错误，运行时间: 0.116秒，时间限制: 0.112秒.2. 0.116 s超时错误，运行时间: 0.116秒，时间限制: 0.100秒.3. 0.124秒没问题

large_1混沌+序列1，2，.，40000 (无负)✔OK 1. 0.340 s OK

large_2▶洗牌序列1，2，.，100000 (不减)✔OK 1. 0.408 s OK 2. 0.372 s OK

large_3▶混沌+多-1，1，2，3(含负)✔OK 1. 0.272 s OK

结论：

• 对于小型测试数组，它几乎与第一个版本一样慢，因此这里的IntStream似乎是瓶颈。
• 对于大型测试数组，速度似乎是英特美的。所以我不太确定它应该告诉我什么。

编辑2:

实际上，我刚刚找到了一篇文章，部分描述了这个问题：https://jaxenter.com/java-performance-tutorial-how-fast-are-the-java-8-streams-118830.html。在这方面，作者声称流和循环在数组上运行的区别是因为流是非常新的。然而，这篇文章的日期是4年前。

Answer 1

你什么都没错过。装箱整数和检查HashSets比迭代基元数组慢。我对第二个解决方案所做的唯一改变是用一个boolean[]替换BitSet，它类似于boolean[]，但更节省空间，因为它每个元素只使用一位。

Answer 2

这两段代码有许多不同之处。我怀疑最大的区别来自于使用Set<Integer>和boolean[]，所以我编写了一个小测试：

        Set<Integer> set = new HashSet<>();
        for (int n : numbs) {
            set.add(n);
        }

vs

        boolean[] arr = new boolean[numbs.length];
        for (int n : numbs) {
            arr[n] = true;
        }

差异为20倍，1000000个数字在范围内[0,1000000]。