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

这段代码的 Big-O 分析是什么？

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

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

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