0
0

Scala Collections 提示和技巧

鸟窝 发表于 2015年07月02日 14:41 | Hits: 1716
Tag: Scala

原文: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的元素后就不会再增加了。
两个表达式并不等价。

自动简化是否可能?这里有两条黄金法则,可以用在有副作用的代码上:

  1. 尽可能的避免副作用
  2. 否则将副作用嗲吗从纯代码中分离开

对于上面的例子,我们需要去掉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(...)
  1. 将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)
  1. 将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/

0     0

评价列表(0)