Java收藏表演[副本]

Question

我刚刚试了一个关于codility的测试示例。任务是：“...给定一个由N个整数组成的数组A，返回A中没有出现的最小正整数（大于0）”。

加上：

>

n为[1..10万]范围内的整数；

数组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解决方案吗？

测试结果第一版：

▶例1第一例测试✔OK 1。0.108s正常

▶例2第二例测试✔OK 1。0.104s正常

▶例3第三例测试✔OK 1。0.104s正常

▶extreme_single单个元素✔OK 1。0.100s正常2。0.104s OK 3。0.104s确定4。0.100s正常

▶简单简单测试✔OK 1。0.100s正常2。0.104s OK 3。0.100s正常

▶extreme_min_max_value最小值和最大值✔OK 1。0.100s正常2。0.104s正常

▶正数_only洗牌序列：0...100然后102...200✔OK 1。0.100s正常2。0.104s正常

▶仅负洗牌序列-100...-1✔OK 1。0.100s正常

▶介质混沌序列长度=10005（带负）超时错误运行时间：0.136秒，时限：0.100秒。1.0.136秒超时错误，运行时间：0.136秒，时限：0.100秒。2.0.128s超时错误，运行时间：0.128秒，时限：0.100秒。3.0.144秒超时错误，运行时间：0.144秒，时限：0.128秒。

▶large_1混沌+序列1,2,...,40000（无负）✔OK 1。0.588s正常

▶large_2洗牌序列1,2,...,100000（无负）✔OK 1。0.748s正常2。0.660s正常

▶大3混沌+多-1,1,2,3（带负）✔OK 1。0.444s正常

测试结果第二版：

▶例1第一例测试✔OK 1。0.004s正常

▶例2第二例测试✔OK 1。0.004s正常

▶例3第三例测试✔OK 1。0.004s正常

▶extreme_single单个元素✔OK 1。0.004s正常2。0.008s正常3。0.004 s确定4。0.008s正常

▶简单简单测试✔OK 1。0.004s正常2。0.004s确定3。0.008s正常

▶extreme_min_max_value最小值和最大值✔OK 1。0.008s正常2。0.004s正常

▶正数_only洗牌序列：0...100然后102...200✔OK 1。0.008s正常2。0.004s正常

▶仅负洗牌序列-100...-1✔OK 1。0.008s正常

▶中混沌序列长度=10005（带负）✔OK 1。0.024秒正常2。0.024秒正常3。0.032s正常

▶large_1混沌+序列1,2,...,40000（无负）✔OK 1。0.220s正常

▶large_2洗牌序列1,2,...,100000（无负）✔OK 1。0.244s确定2。0.244s正常

▶大3混沌+多-1,1,2,3（带负）✔OK 1。0.172s正常

底线：尤其是小尺寸阵列的测试，在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();

}

结果：

▶例1第一例测试✔OK 1。0.096s正常

▶例2第二例测试✔OK 1。0.096s正常

▶例3第三例测试✔OK 1。0.096s OK折叠所有正确性测试

▶extreme_single单个元素✔OK 1。0.096s确定2。0.096s OK 3。0.096s确定4。0.096s正常

▶简单简单测试✔OK 1。0.100s正常2。0.096s OK 3。0.100s正常

▶extreme_min_max_value最小值和最大值✔OK 1。0.096s确定2。0.100s正常

▶正数_only洗牌序列：0...100然后102...200✔OK 1。0.096s确定2。0.096s正常

▶仅负洗牌序列-100...-1✔OK 1。0.096s OK折叠所有性能测试

▶介质混沌序列长度=10005（带负）超时错误运行时间：0.116秒，时限：0.112秒。1.0.116s超时错误，运行时间：0.116秒，时限：0.112秒。2.0.116s超时错误，运行时间：0.116秒，时限：0.100秒。3.0.124s正常

▶large_1混沌+序列1,2,...,40000（无负）✔OK 1。0.340s正常

▶large_2洗牌序列1,2,...,100000（无负）✔OK 1。0.408s确定2。0.372s正常

▶大3混沌+多-1,1,2,3（带负）✔OK 1。0.272s正常

结论：

• 对于小尺寸的测试数组，它几乎和第一个版本一样慢，因此这里IntStream似乎是瓶颈。
• 对于大型测试数组，速度似乎是内部的。因此我不确定它应该告诉我什么。

编辑2：

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

Answer 1

你没有错过任何东西。装箱整数和检查哈希集比迭代基元数组慢。我对第二种解决方案所做的唯一更改是用一个位集替换boolean[]，它与boolean[]类似，但更节省空间，因为每个元素只使用一个位。