如何对使用 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

您正在遍历 array（大小 100000）的所有元素，而您需要做的就是在您创建的列表中找到数字 0 到 100（假设互斥）的频率，所以有效地迭代 100 次为：

int[] counts = new int[100];
IntStream.range(0,100).forEach(i -> counts[i] = Collections.frequency(l,i));

顺便说一句，如果您要遍历整个数组以将其转换为列表，则更简单的方法是计算同一循环中元素的出现次数。

int[] counts = new int[100];
for( int i = 0 ; i < array.length ; i ++){
    counts[array[i]]++; // same asssumption (array[i] < 100)
}

或以流表示

Arrays.stream(array).forEach(i -> counts[i]++);

Answer 2

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 中的每个位置只扫描一次，但即使那样也会非常浪费。你能想出一种方法来一次收集所有频率计数吗？提示：不要想太多。

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

How does one do asymptotic analysis of code that uses JDK streams API?

java

complexity-theory

java-stream