java - 如何对使用 JDK 流 API 的代码进行渐近分析？

Question

一般来说，我知道我们必须查看源代码才能了解代码的性能。

但更具体地说，此代码在竞争性编程网站中超时。

这会找到从 0 到 100 的数字在流中出现的频率。 数组中的数字介于 0 和 100 之间。

    // Times out with int[] array containing 100000 elements.

    List<Integer> l = new ArrayList<>();
    for( int i = 0 ; i < array.length ; i ++){
        l.add(array[i]);
    }

    int[] counts = new int[100];
    Arrays.stream(array).forEach( i -> counts[i] = Collections.frequency( l, i));

此代码的 Big-O 分析是什么？我认为罪魁祸首是我使用 Streams API 的方式。

Answer 1

What is the Big-O analysis for this code ?

• 没有理由认为 Arrays.stream() 本身的成本会随着问题的大小而增加。
• Stream.forEach() 以 n * K 为界，其中 n 是数组的大小，K 是 lambda 的渐近复杂度。您的特定用途不会缩短迭代，因此没有理由期望更严格的界限
• lambda 的复杂性由 Collections.frequency() 驱动，它与集合的大小成线性比例关系，也是 n，因为它必须扫描整个事物.

总的来说，这使得 O(n²)。

这里的浪费在于为每个数组元素扫描整个集合。由于您预计每个值平均出现 1000 次，因此成本非常高，并且它与数组元素的数量成比例。我怀疑您打算为 count 中的每个位置只扫描一次，但即使那样也会非常浪费。你能想出一种方法来一次收集所有频率计数吗？提示:不要想太多。