β

Scala Collection

f(x) 60 阅读

Scala编程语言内建了丰富的集合类型:List、Vector、Array、Set、Map等等。当然还有一些众所周知的基础知识:List可以快速地在头部增加元素,但是索引起来很慢,Vector是一个很好的通用目的的集合,但是实践中这些集合处理的数据确很少。目前最好的描述这些运行时特性的 表格

1 内存

各种集合的内存占用,它比性能更容易分析,因为它的结果是确定的:你不需要多次测试来求平均值来减少误差。虽然不太常用,但是你还是可以通过直接使用反射和Java的Instrumentation API写个程序来分析一个对象的内存占用。

2 性能

下一个要关注的事情就是使用各种集合执行通用的操作要花多长时间。不像内存占用那样可以静态分析,运行时的性能通常会有噪点和随机性:JIT编译器是否启用、垃圾回收是否发生等。

构建一个 Vector 要比构建 List 慢5到15倍,具体和集合大小有关:如果你是一个一个的添加元素到集合中,使用 List 要比 Vector 快很多。如果你的代码中构建一个 Vector 变成了瓶颈,那么你应该考虑使用 List 或者 Buffer 来替换它。

使用 .append 构建一个 mutable.Buffer 看起来要比使用 :: 构建 List 要慢2到3倍,这意味着如果你想更快, List 是一个更好的选择。

最快的是预分配内存的 Array ,大约比构建 List 快4倍,比构建 mutable.Buffer 快5倍,比构建 Vector 快15倍。使用 :+ 构建 Array 需要花费更多的时间,因为它每次都要复制整个数组。

mutable.Buffer List 是最快的移除元素操作的集合。因为从 mutable.Buffer 移除元素只是改变它的size。从 List 的头部移除元素只是得到它的 .tail ,不需要做数据结构的改变。

重复地从 Map Set 移除 .head 也很慢,从 mutable.Map mutable.Set 移除元素更慢。

连接集合最快的是 mutable.Buffers Array ,它们只是简单的复制元素到一个新的集合中。 mutable.Buffer 内部使用一个数组,所以它需要重新分配更大的数组来复制数据,而数组则是将两个输入数组复制到一个更大的数组中。你使用 Array ++ Array 还是 System.arraycopy 并不重要。

迭代大部分常用的集合都很快,无论集合是 List Vector 还是 Array 。使用 while-loop head/tail 的速度是一样的,所以如果你想手写迭代来提高性能,结果可能没什么区别。

3 总结

3.1 Array超好用
一个未装箱的基本类型的数组只要装箱的数组的内存的1/4或者1/5,如果你要处理大量的基本类型的数据,使用非装箱数组会帮你省好多钱。

除了基本类型数组,即使装箱的数组要有漂亮的性能数据。连接两个数据要比连接其它集合要快,甚至比 List Vector 这些有精心设计的数据结构还要快。它表明复制整体数据事实上要比组合那些持久化数据结构都要快。所以如果你要处理一个不可变集合,有时候需要把它分成片段或者连接起来,使用数组要更快。

3.2 Set和Map都很慢
Set Map 不只是查找很慢,构建它们也很慢,移除元素也很慢,连接集合也很慢。即使操作不需要执行hash计算,比如迭代(iteration),也比迭代一个 Vector 慢19倍。所以除非你需要不能重复元素的集合才使用 Set ,需要键值对才选择 Map ,否则尽量不用它们,因为它们才是程序慢的原因。

3.3 Lists vs Vectors
选择linked形式的 List 还是tree形式的 Vector 的标准很模糊。“有效的常数时间”的定义不能理清这种模糊认识,但是通过上面的测试数据,我们可以有一个更好的判断:

如果你自己构建集合并且一个个的移除元素,迭代它们,最好使用 List 。如果你需要根据索引查找元素,则选择 Vector

3.4 Lists vs mutable.Buffer
List 除了作为不可变集合外,还经常使用 var 作为可变集合,而 mutable.Buffer 也有相同的目的,那你该用哪一个集合呢?

数据表明在一个个的处理元素时,使用 List 要比 mutable.Buffer 快:对小集合来说快2到3倍,大集合要快1.5到2倍。

3.5 Vector还算好
总体来说, Vector 还是一个可以接受的通用目的的集合。一方面,你看不到 Vector 有什么严重的性能缺陷,大部分的性能都处于中等水平;另一方面,常用操作要比理想的数据结构慢一个数量级。增量构建比 List 慢5到15,索引查找比数组慢很多,即使连接操作也比数组慢10倍。 Vector 通常是缺省的数组结构,但是如果可能的话,直接使用 List 或者 mutable.Buffer 可能会给性能带来数量级的提升。

参考资料:

Scala Collection的性能

Scala编程语言内建了丰富的集合类型:List、Vector、Array、Set、Map等等。当然还有一些众所周知的基础知识:List可以快速地在头部增加元素,但是索引起来很慢,Vector是一个很好的通用目的的集合,但是实践中这些集合处理的数据确很少。目前最好的描述这些运行时特性的 表格

作者:f(x)
精于心,简于形
原文地址:Scala Collection, 感谢原作者分享。

发表评论