0
Scala Collections 提示和技巧
原文:Scala Collections Tips and Tricks,
作者Pavel Fatin是JetBrains 的一名员工,为神器IntelliJ IDEA开发Scala插件。
受其工作Scala Collections inspections)的启发,他整理了这个关于Java Collections API技巧的列表。
一些技巧只在一些微妙的实现细节中体现,但是大部分技巧都是一般的常识,但是在大部分情况下被忽视了。
性和谐提示和技巧很有价值,可以帮你深入理解Scala Collections,可以是你的代码更快更简洁。
图例 Legend
为了使下面的例子更容易理解,这里列出了一些约定:
- seq— 一个Seq-based的集合, 比如Seq(1, 2, 3)
- set— 一个Set实例, 比如Set(1, 2, 3)
- array— 一个数组, 比如Array(1, 2, 3)
- option— 一个Option, 比如Some(1)
- map— 一个Map, 比如Map(1 -> "foo", 2 -> "bar")
- p— 一个断言predicate函数,类型T => Boolean, 比如_ > 2
- n— 一个整数
- i— 一个索引
- f, g— 简单函数,A => B
- x, y— 一些字面值(arbitrary values)
- z— 初始值或者缺省值
组合Composition
记住,尽管这些技巧都是独立和自包含的,我们还是可以将它们组合起来逐步迭代得到一个更高级的表达式,比如下面的例子,在一个Seq中检查一个元素是否存在:
123456789 |
seq.filter(_ == x).headOption != None// Via seq.filter(p).headOption -> seq.find(p)seq.find(_ == x) != None// Via option != None -> option.isDefinedseq.find(_ == x).isDefined// Via seq.find(p).isDefined -> seq.exists(p)seq.exists(_ == x)// Via seq.exists(_ == x) -> seq.contains(x)seq.contains(x) |
我们可以依赖”substitution model of recipe application“ (SICP))来简化复杂的表达式。
副作用 Side effects
”Side effects“是一个基础概念,在函数式编程语言中会有这个概念。 Scala有一个PPT专门介绍:Side-effect checking for Scala
基本上,”Side effects“是这样一个动作, 除了返回一个值外,外部函数或者表达式还观察到此动作还有以下行为之一:
- 有输入输出操作 (比如文件,网络I/O)
- 对外部变量有修改
- 外部对象的状态有改变
- 抛出异常
当一个函数或者表达式有以上任何一种情况时,我们就说它有副作用(Side effects),否则我们就说它是"纯"的函数或者表达式 (pure)。
side effects有什么大不了的?当有副作用时,计算的顺序不能随便改变。 比如下面两个"纯" (pure)表达式:
12 |
val x = 1 + 2val y = 2 + 3 |
因为它们没有副作用,两个表达式可以互换位置,先x后y和先y后x的效果一样。
如果有副作用 (有控制台输出):
12 |
val x = { print("foo"); 1 + 2 }val y = { print("bar"); 2 + 3 } |
两个表达式不能互换位置,因为一旦互换位置,输出结果的顺序变了。
所以副作用的一个影响就是会减少可能的转换的数量(reduces the number of possible transformations),包括可能的简化和优化。
同样的原因可适用用Collection相关的表达式上。看一个外部的builder变量(副作用方法append):
1 |
seq filter { x => builder.append(x); x > 3 } headOption |
原则上seq.filter(p).headOption可以简化为seq.find(p),但是副作用阻止我们这么做. 如果你尝试这么做:
1 |
seq find { x => builder.append(x); x > 3 } |
结果和前一个表达式并不一样。 前一个表达式计算后所有大于3的元素都增加到builder中了, 后一个表达式在找到第一个大于3的元素后就不会再增加了。
两个表达式并不等价。
自动简化是否可能?这里有两条黄金法则,可以用在有副作用的代码上:
- 尽可能的避免副作用
- 否则将副作用嗲吗从纯代码中分离开
对于上面的例子,我们需要去掉builder或者将它从纯代码中隔离。 考虑到builder是第三方的对象,我们无法去除,那我们通过隔离的方式实现:
12 |
seq.foreach(builder.append)seq.filter(_ > 3).headOption |
这样我们就可以用到本文中的技巧进行替换:
12 |
seq.foreach(builder.append)seq.find(x > 3) |
干的漂亮!自动简化也成为可能,一个额外好处是由于清晰的隔离,代码更容易理解。
一个不太明显的好处是,代码变得更健壮。如上面的例子,副作用针对不同的Seq实现,副作用的结果也不相同, 比如Vector和Stream, 副作用隔离可以让我们避免这种不确定的行为。
Sequence
本节中的技巧针对Seq以及它的子类, 而一些转换可以应用于其它集合类,如Set,Option,Map,甚至Iterator类,因为它们提供了相近的接口。
创建Creation
显示创建集合
12345 |
// BeforeSeq[T]()// AfterSeq.empty[T] |
有时候可以节省内存(重用empty对象)和CPU (length check浪费)。
也可应用于Set,Option,Map,Iterator.
Length
对于数组,优先使用length而不是size。
12345 |
// Beforearray.size// Afterarray.length |
length和size基本是同义词。在Scala 2.11中,Array.size是通过隐式转换实现的。因此每次调用时,一个中间包装类会被创建,除非你允许jvm的escape analysis。这会产生多余的GC对象,影响性能。
不要对检查empty的属性取反
1234567 |
// Before!seq.isEmpty!seq.nonEmpty// Afterseq.nonEmptyseq.isEmpty |
同样适用于Set,Option,Map,Iterator
不要通过计算length来检查empty
123456789 |
// Beforeseq.length > 0seq.length != 0seq.length == 0// Afterseq.nonEmptyseq.nonEmptyseq.isEmpty |
一方面已经有检查empty的方法,另一方面,,比如LinearSeq和子类List,会花费O(n)的时间计算length(IndexedSeq花费O(1))。
同样适用于Set,Map
不要直接使用length来比较
1234567891011 |
// Beforeseq.length > nseq.length < nseq.length == nseq.length != n// Afterseq.lengthCompare(n) > 0seq.lengthCompare(n) < 0seq.lengthCompare(n) == 0seq.lengthCompare(n) != 0 |
同上一条,计算length有时候非常昂贵,有可能将花费从O(length)减少到O(length min n)。
对于无限的stream来说,上面的技巧是绝对必要的。
等价 Equality
不要使用==比较数组:
12345 |
// Beforearray1 == array2// Afterarray1.sameElements(array2) |
因为==只是比较实例对象,而不是里面的元素。
同样适用于Iterator
不要检查不同分类(categories)的集合的相等性
12345 |
// Beforeseq == set// Afterseq.toSet == set |
不要使用sameElements来比较有序集合
12345 |
// Beforeseq1.sameElements(seq2)// Afterseq1 == seq2 |
不要手工检查相等性
12345 |
// Beforeseq1.corresponds(seq2)(_ == _)// Afterseq1 == seq2 |
使用内建的方法。
Indexing
不要使用index得到第一个元素
12345 |
// Beforeseq(0)// Afterseq.head |
不要使用index得到最后一个元素
12345 |
// Beforeseq(seq.length - 1)// Afterseq.last |
不要显式检查index的边界
12345 |
// Beforeif (i < seq.length) Some(seq(i)) else None// Afterseq.lift(i) |
不要仿造headOption
123456 |
// Beforeif (seq.nonEmpty) Some(seq.head) else Noneseq.lift(0)// Afterseq.headOption |
不要仿造lastOption
123456 |
// Beforeif (seq.nonEmpty) Some(seq.last) else Noneseq.lift(seq.length - 1)// Afterseq.lastOption |
小心indexOf和lastIndexOf参数类型
1234567 |
// BeforeSeq(1, 2, 3).indexOf("1") // compilableSeq(1, 2, 3).lastIndexOf("2") // compilable// AfterSeq(1, 2, 3).indexOf(1)Seq(1, 2, 3).lastIndexOf(2) |
不要构造index的Range
12345 |
// BeforeRange(0, seq.length)// Afterseq.indices |
不要手工使用index来zip集合
12345 |
// Beforeseq.zip(seq.indices)// Afterseq.zipWithIndex |
检查元素的存在 Existence
不要用断言equality predicate 来检查存在
12345 |
// Beforeseq.exists(_ == x)// Afterseq.contains(x) |
同样应用于Set,Option,Iterator
小心contains参数类型
12345 |
// BeforeSeq(1, 2, 3).contains("1") // compilable// AfterSeq(1, 2, 3).contains(1) |
不要用断言inequality predicate 来检查不存在
12345 |
// Beforeseq.forall(_ != x)// After!seq.contains(x) |
同样应用于Set,Option,Iterator
不要统计元素的数量来检查存在
123456789 |
// Beforeseq.count(p) > 0seq.count(p) != 0seq.count(p) == 0// Afterseq.exists(p)seq.exists(p)!seq.exists(p) |
同样应用于Set,Map,Iterator
不要借助filter来检查存在
1234567 |
// Beforeseq.filter(p).nonEmptyseq.filter(p).isEmpty// Afterseq.exists(p)!seq.exists(p) |
同样应用于Set,Option,Map,Iterator
Filtering
不要对断言取反
12345 |
// Beforeseq.filter(!p)// Afterseq.filterNot(p) |
同样应用于Set,Option,Map,Iterator
不要借助filter统计元素数量
12345 |
// Beforeseq.filter(p).length// Afterseq.count(p) |
调用filter会产生一个临时集合,影响GC和性能。
同样应用于Set,Option,Map,Iterator
不要借助filter找到元素的第一个值
12345 |
// Beforeseq.filter(p).headOption// Afterseq.find(p) |
同样应用于Set,Option,Map,Iterator
Sorting
不要手工按一个属性排序
12345 |
// Beforeseq.sortWith(_.property < _.property)// Afterseq.sortBy(_.property) |
不要手工按照identity排序
1234567 |
// Beforeseq.sortBy(it => it)seq.sortBy(identity)seq.sortWith(_ < _)// Afterseq.sorted |
一步完成排序反转
123456789 |
// Beforeseq.sorted.reverseseq.sortBy(_.property).reverseseq.sortWith(f(_, _)).reverse// Afterseq.sorted(Ordering[T].reverse)seq.sortBy(_.property)(Ordering[T].reverse)seq.sortWith(!f(_, _)) |
Reduction
不要手工计算sum
1234567 |
// Beforeseq.reduce(_ + _)seq.fold(z)(_ + _)// Afterseq.sumseq.sum + z |
其它可能用的方法reduceLeft,reduceRight,foldLeft,foldRight
同样应用于Set,Iterator
不要手工计算product
1234567 |
// Beforeseq.reduce(_ * _)seq.fold(z)(_ * _)// Afterseq.productseq.product * z |
同样应用于Set,Iterator
不要手工搜索最小值和最大值
1234567 |
// Beforeseq.reduce(_ min _)seq.fold(z)(_ min _)// Afterseq.minz min seq.min |
1234567 |
// Beforeseq.reduce(_ max _)seq.fold(z)(_ max _)// Afterseq.maxz max seq.max |
同样应用于Set,Iterator
不要仿造forall
123456 |
// Beforeseq.foldLeft(true)((x, y) => x && p(y))!seq.map(p).contains(false)// Afterseq.forall(p) |
同样应用于Set,Option(for the second line),Iterator
不要仿造exists
123456 |
// Beforeseq.foldLeft(false)((x, y) => x || p(y))seq.map(p).contains(true)// Afterseq.exists(p) |
Rewriting
合并连续的filter调用
12345 |
// Beforeseq.filter(p1).filter(p2)// Afterseq.filter(x => p1(x) && p2(x)) |
或seq.view.filter(p1).filter(p2).force
同样应用于Set,Option,Map,Iterator
合并连续的map调用
12345 |
// Beforeseq.map(f).map(g)// Afterseq.map(f.andThen(g)) |
或seq.view.map(f).map(g).force
同样应用于Set,Option,Map,Iterator
filter完后再排序
12345 |
// Beforeseq.sorted.filter(p)// Afterseq.filter(p).sorted |
在调用map前不要显式调用反转reverse
12345 |
// Beforeseq.reverse.map(f)// Afterseq.reverseMap(f) |
不要显示反转得到迭代器
12345 |
// Beforeseq.reverse.iterator// Afterseq.reverseIterator |
不要通过将集合转成Set得到不重复集合
12345 |
// Beforeseq.toSet.toSeq// Afterseq.distinct |
不要仿造slice
12345 |
// Beforeseq.drop(x).take(y)// Afterseq.slice(x, x + y) |
同样应用于Set,Map,Iterator
不要仿造splitAt
123456 |
// Beforeval seq1 = seq.take(n)val seq2 = seq.drop(n)// Afterval (seq1, seq2) = seq.spiltAt(n) |
不要仿造span
123456 |
// Beforeval seq1 = seq.takeWhile(p)val seq2 = seq.dropWhile(p)// Afterval (seq1, seq2) = seq.span(p) |
不要仿造partition
123456 |
// Beforeval seq1 = seq.filter(p)val seq2 = seq.filterNot(p)// Afterval (seq1, seq2) = seq.partition(p) |
不要仿造takeRight
12345 |
// Beforeseq.reverse.take(n).reverse// Afterseq.takeRight(n) |
不要仿造flatten
123456 |
// Before (seq: Seq[Seq[T]])seq.flatMap(it => it)seq.flatMap(identity)// Afterseq.flatten |
同样应用于Set,Map,Iterator
不要仿造flatMap
12345 |
// Before (f: A => Seq[B])seq.map(f).flatten// Afterseq.flatMap(f) |
同样应用于Set,Option,Iterator
不需要结果时不要用map
12345 |
// Beforeseq.map(...) // the result is ignored// Afterseq.foreach(...) |
同样应用于Set,Option,Map,Iterator
不要产生临时集合
1.使用view
12345 |
// Beforeseq.map(f).flatMap(g).filter(p).reduce(...)// Afterseq.view.map(f).flatMap(g).filter(p).reduce(...) |
- 将view转换成一个同样类型的集合
12345 |
// Beforeseq.map(f).flatMap(g).filter(p)// Afterseq.view.map(f).flatMap(g).filter(p).force |
如果中间的转换是filter,还可以
1 |
seq.withFilter(p).map(f) |
- 将view转换成另一种集合
12345 |
// Beforeseq.map(f).flatMap(g).filter(p).toList// Afterseq.view.map(f).flatMap(g).filter(p).toList |
还有一种“transformation + conversion”方法:
1 |
seq.map(f)(collection.breakOut): List[T] |
使用赋值操作符
1234567891011 |
// Beforeseq = seq :+ xseq = x +: seqseq1 = seq1 ++ seq2seq1 = seq2 ++ seq1// Afterseq :+= xseq +:= xseq1 ++= seq2seq1 ++:= seq2 |
Scala有一个语法糖,自动将x <op>= y转换成x = x <op> y. 如果op以:结尾,则被认为是右结合的操作符。
一些list和stream的语法:
12345678910111213 |
// Beforelist = x :: listlist1 = list2 ::: liststream = x #:: liststream1 = stream2 #::: stream// Afterlist ::= xlist1 :::= list2stream #::= xstream1 #:::= stream2 |
同样应用于Set,Map,Iterator
Set
大部分的Seq的技巧也可以应用于Set。另外还有一些只针对Set的技巧。
不要使用sameElements比较未排序的集合
12345 |
// Beforeset1.sameElements(set2)// Afterset1 == set2 |
同样应用于Map
不要手工计算交集
123456 |
// Beforeset1.filter(set2.contains)set1.filter(set2)// Afterset1.intersect(set2) // or set1 & set2 |
不要手工计算diff
123456 |
// Beforeset1.filterNot(set2.contains)set1.filterNot(set2)// Afterset1.diff(set2) // or set1 &~ set2 |
Option
Option并不是集合类,但是它提供了类似的方法和行为。
大部分针对Seq的技巧也适用于Option。这里列出了一些特殊的只针对Option的技巧。
Value
不要使用None和Option比较
1234567 |
// Beforeoption == Noneoption != None// Afteroption.isEmptyoption.isDefined |
不要使用Some和Option比较
1234567 |
// Beforeoption == Some(v)option != Some(v)// Afteroption.contains(v)!option.contains(v) |
不要使用实例类型来检查值的存在性
12345 |
// Beforeoption.isInstanceOf[Some[_]]// Afteroption.isDefined |
不要使用模式匹配来检查值的存在
12345678 |
// Beforeoption match { case Some(_) => true case None => false}// Afteroption.isDefined |
同样适用于Seq,Set
对于检查存在性的属性不要取反
123456789 |
// Before!option.isEmpty!option.isDefined!option.nonEmpty// Afterseq.isDefinedseq.isEmptyseq.isEmpty |
不要检查值的存在性再处理值
12345678910 |
// Beforeif (option.isDefined) { val v = option.get ...}// Afteroption.foreach { v => ...} |
Null
不要通过和null比较来构造Option
12345 |
// Beforeif (v != null) Some(v) else None// AfterOption(v) |
不要显示提供null作为备选值
12345 |
// Beforeoption.getOrElse(null)// Afteroption.orNull |
Rewriting
将mapwithgetOrElse转换成fold
12345 |
// Beforeoption.map(f).getOrElse(z)// Afteroption.fold(z)(f) |
不要仿造exists
12345 |
// Beforeoption.map(p).getOrElse(false)// Afteroption.exists(p) |
不要手工将option转换成sequence
123456 |
// Beforeoption.map(Seq(_)).getOrElse(Seq.empty)option.getOrElse(Seq.empty) // option: Option[Seq[T]]// Afteroption.toSeq |
Map
同上,这里只列出针对map的技巧
不要使用lift替换get
12345 |
// Beforemap.lift(n)// Aftermap.get(n) |
因为没有特别的需要将map值转换成一个Option。
不要分别调用get和getOrElse
12345 |
// Beforemap.get(k).getOrElse(z)// Aftermap.getOrElse(k, z) |
不要手工抽取键集合
123456789 |
// Beforemap.map(_._1)map.map(_._1).toSetmap.map(_._1).toIterator// Aftermap.keysmap.keySetmap.keysIterator |
不要手工抽取值集合
1234567 |
// Beforemap.map(_._2)map.map(_._2).toIterator// Aftermap.valuesmap.valuesIterator |
小心使用filterKeys
12345 |
// Beforemap.filterKeys(p)// Aftermap.filter(p(_._1)) |
因为filterKeys包装了原始的集合,并没有复制元素,后续处理得小心。
小心使用mapValues
12345 |
// Beforemap.mapValues(f)// Aftermap.map(f(_._2)) |
同上。
不要手工filter 键
12345 |
// Beforemap.filterKeys(!seq.contains(_))// Aftermap -- seq |
使用赋值操作符重新赋值
1234567891011 |
// Beforemap = map + x -> ymap1 = map1 ++ map2map = map - xmap = map -- seq// Aftermap += x -> ymap1 ++= map2map -= xmap --= seq |
补充
除了以上的介绍,建议你看一下官方文档Scala Collections documentation。
还有
最后一段是作者的谦虚话,欢迎提供意见和建议。
原文链接: http://colobu.com/2015/07/02/Scala-Collections-Tips-and-Tricks/