java - Java并行流最有效的列表类型是什么？

Question

我有一个List<String> toProcess，我想进一步处理

toProcess.parallelStream().map(/*some function*/).collect(Collectors.toList());

哪种初始列表最好的List类型(例如LinkedList，ArrayList等)从此多线程中获得最佳速度？

附加信息:预期的元素计数范围为10 ^ 3-10 ^ 5，但是单个元素可能会变得很大(10 ^ 5-10 ^ 6个字符)。

另外，我可以在各处使用 String[]，因为可以保证字符串的数量不会改变(结果将包含与toProcess一样多的元素)。

无论哪种方式，我都必须在最后依次遍历所有元素。目前，我使用 foreach -loop组合最终结果。可以轻松地将其更改为常规 for -loop。

Answer 1

如果确定输出元素的数量等于输入元素的数量，并且对数组感到满意，那么绝对可以使用toArray而不是收集器。如果管道始终具有固定的大小，则将使用正确的大小预先分配目标数组，并且并行操作将其结果直接存储到目标数组的正确位置:不进行复制，重新分配或合并。

如果需要List，则始终可以使用Arrays.asList包装结果，但是当然不能在结果中添加或删除元素。

收藏家

如果以上条件之一不成立，则需要与权衡不同的收集器打交道。

收集器通过以线程限制的方式对中间结果进行操作来并行工作。然后将中间结果合并为最终结果。需要考虑两个操作:1)将单个元素累加到中间结果中，以及2)将中间结果合并(或合并)成最终结果。

在LinkedList和ArrayList之间，ArrayList可能更快，但您应该对此进行基准测试以确保。请注意，默认情况下Collectors.toList使用ArrayList，尽管在将来的版本中可能会更改。

链接列表

每个要累积的元素(LinkedList.add)涉及分配一个新的列表节点并将其挂接到列表的末尾。将节点挂接到列表的速度非常快，但这涉及到每个流元素的分配，随着累积的进行，这很可能会导致少量垃圾回收。

合并(LinkedList.addAll)也非常昂贵。第一步是将源列表转换为数组。这是通过遍历列表的每个节点并将元素存储到临时数组中来完成的。然后，代码在此临时数组上进行迭代，并将每个元素添加到目标列表的末尾。如上所述，这导致为每个元素分配新节点。因此，合并操作非常昂贵，因为它会在源列表中的每个元素上迭代两次，并为每个元素分配资源，这可能会带来垃圾回收开销。

ArrayList

每个元素的累加通常涉及将其附加到ArrayList所包含的数组的末尾。这通常很快，但是如果阵列已满，则必须重新分配并复制到更大的阵列中。 ArrayList的增长策略是将新数组分配为比当前数组大50％，因此重新分配的发生与所添加元素数的对数成正比，这还不错。但是，所有元素都必须复制过来，这意味着较早的元素可能需要多次复制。

合并ArrayList可能比LinkedList便宜得多。将ArrayList转换为数组涉及从源到临时数组的大量元素复制(而不是一次)。如有必要，将调整目标数组的大小(在这种情况下可能会调整大小)，这需要所有元素的批量复制。然后，将源元素从临时阵列批量复制到目标，该目标已预先调整大小以适应它们。

讨论

鉴于以上情况，看来ArrayList会比LinkedList快。但是，即使收集到ArrayList也需要一些不必要的重新分配和许多元素的复制，可能需要多次。 Collectors.toList可能会在将来进行优化，以将元素累积到为快速追加访问而优化的数据结构中，最好是已预先设置大小以容纳预期数量的元素。支持快速合并的数据结构也是可能的。

如果您要做的只是遍历最终结果，那么滚动具有这些属性的自己的数据结构应该不会太困难。如果不需要成为完整的List，则应该可以进行大幅简化。它可以累积到预先确定大小的列表中以避免重新分配，并且合并会将它们简单地收集到树结构或列表列表中。有关想法，请参见JDK的SpinedBuffer(私有实现类)。