Arrays.parallelSetAll()的时间复杂度是多少？

Question

我刚才读到:关于java 8的一切 ,java 8添加了Arrays.parallelSetAll()

int[] array = new int[8];
AtomicInteger i= new AtomicInteger();
Arrays.parallelSetAll(array, operand -> i.incrementAndGet());

[编辑]对于阵列中相同数量的元素,在同一台机器上是O(1)还是恒定时间复杂度？方法名称表示什么样的性能改进？

Answer 1

首先,它永远不会是O(1),更多的澄清如下:

我正在使用它n = array.length,在你的情况下8,然而这无关紧要,因为它也可能是一个非常大的数字.

现在观察通常你会这样做:

for (int i = 0; i < n; i++) {
    array[i] = i.incrementAndGet();
}

这对Java 8来说更容易:

Arrays.setAll(array, v -> i.incrementAndGet());

观察他们都花了O(n)时间.

现在考虑到你并行执行代码,但不保证它是如何执行它的,你不知道它在引擎盖下做的并行化的数量,如果有的话,对于这么低的数字.

因此,它仍然需要O(n)时间,因为你不能证明它将在n个线程上并行化.

编辑,作为额外的,我观察到你似乎认为并行化一个动作意味着任何O(k)将会聚到O(1),其中k = n或k = n^2等等
.实际情况并非如此,因为你可以证明你永远不会有k处理器核心.

一个直观的论点是你自己的计算机,如果你很幸运它可能有8个核心,因此在完美的并行化条件下你可以达到的最大时间是O(n/8).
我已经可以听到未来的人们嘲笑我们只有8个CPU内核......

Answer 2

是的O(N).调用Arrays.parallelSetAll(...)涉及分配以设置总数array.length组元素.即使这些分配分布在P处理器上,分配的总数也与数组的长度成线性比例.采取N作为该阵列的长度,和数学是显而易见的.

要意识到的是P......可用处理器的数量......对于在一台计算机上执行任何程序而言将是一个常量.(或者如果它不是常量,则会有一个常量上限.)并且一个计算的唯一目的是将值赋给数组只在单个计算机上执行时才有意义.