Vector或MutableList/ListBuffer的性能 [英] Vector or MutableList / ListBuffer for performance

问题描述

很抱歉，如果重复的话-我做了几次搜索，却没有找到我需要的东西.

Apologies if this is a duplicate - I did a few searches and didn't quite find what I need.

我们的应用程序中有一个性能至关重要的部分，它将输入数据的Play 2.0 Enumerator (可以认为是 Stream )转换为 List(或类似名称).我们将在 Enumerator 上使用 fold 方法，问题是最有效的方法是什么.(我将在代码中使用 Stream 而不是 Enumerator ，但是思想应该是相同的.)

We have a performance critical piece of our application that converts a Play 2.0 Enumerator (can be thought of as a Stream) of incoming data to a List (or similar). We will use the fold method on Enumerator and the question is what will be the most performant way to do it. (I will use Stream instead of Enumerator in the code, but the idea should be the same.)

val incoming: Stream[Int] = ???
val result: Seq[Int] = incoming.fold(Seq.empty)(_ + _)
val result2: Seq[Int] = incoming.fold(MutableList.empty(_ += _).toSeq

所以本质上，问题是，在性能上重复添加到不可变的 Vector 与重复添加到可变的 MutableList 或 ListBuffer 相比如何?关键代码?我们只抛出了 List ，因为我们需要追加 O(1)(而不是前置).但是可变的数据结构在性能或垃圾回收方面能给我们带来任何好处吗?

So the question is essentially, how does repeatedly appending to an immutable Vector compare to repeatedly appending to a mutable MutableList or ListBuffer in performance critical code? We've thrown out just List because we need O(1) appending (not prepending). But does the mutable data-structure buy us anything in terms of performance or garbage collection?

推荐答案

最好使用 ArrayBuffer .在我的机器上，您每秒获得的附加数目约为:

You are probably best off using ArrayBuffer. On my machine, you get about the following number of appends per second:

preallocated Array[Int]    -- 830M
resized (x2) Array[Int]    -- 263M
Vector.newBuilder + result -- 185M
mutable.ArrayBuffer        -- 125M
mutable.ListBuffer         -- 100M
mutable.MutableList        --  71M
immutable.List + reverse   --  68M
immutable.Vector           --   8M

我假设您不总是存储int，并且您希望所有集合都很好，而无需额外包装，因此 ArrayBuffer 是性能最佳的解决方案，只要您只需要追加一个即可结尾.列表支持双向加法，并且是可比较的.Vector的比较速度非常慢-仅在您可以利用大量数据共享或一次创建所有内容的情况下才使用它(请参阅 Vector.newBuilder 结果，这太棒了；它是出色的数据结构，可用于访问，迭代，创建和保留更新，而不是随时更新.

I assume you're not always just storing ints, and you want all the collections goodness without extra wrappings, so ArrayBuffer is the best-performing solution as long as you only need to append to one end. The lists support bidirectional addition and are comparable. Vector is horribly slow in comparison--only use it if you can take advantage of a lot of data sharing, or create it all in one swoop (see Vector.newBuilder result, which is fantastic; it's a great data structure for access, iteration, and creation and sparing updates, not updates-all-the-time).

这篇关于Vector或MutableList/ListBuffer的性能的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！