Scala学习系列-集合2：用好List

Posted on Edited on In Views:

List是我们使用最为广泛集合类型，用好List在一定程序度来讲是进入Scala集合世界的第一步，本篇我们从原理、使用和性能的角度来详细介绍如何用好Scala中的List。

List的性质

列表是不可变的

列表是递归的链表

列表内部是递归的，它的数据结构是链表

列表元素是协变的

List的类型

抽象类List

1
2
3
4
5
6
7
8
9
10
sealed abstract class List[+A] extends AbstractSeq[A]
                                  with LinearSeq[A]
                                  with Product
                                  with GenericTraversableTemplate[A, List]
                                  with LinearSeqOptimized[A, List[A]]
                                  with Serializable {
  def isEmpty: Boolean
  def head: A
  def tail: List[A]
}

case类::

1
2
3
4
final case class ::[B](override val head: B, private[scala] var tl: List[B]) extends List[B] {
  override def tail : List[B] = tl
  override def isEmpty: Boolean = false
}

对象Nil

1
2
3
4
5
6
7
8
9
10
11
12
case object Nil extends List[Nothing] {
  override def isEmpty = true
  override def head: Nothing =
    throw new NoSuchElementException("head of empty list")
  override def tail: List[Nothing] =
    throw new UnsupportedOperationException("tail of empty list")
  // Removal of equals method here might lead to an infinite recursion similar to IntMap.equals.
  override def equals(that: Any) = that match {
    case that1: scala.collection.GenSeq[_] => that1.isEmpty
    case _ => false
  }
}

List的模式匹配

列表可以使用模式匹配解开，列表模式可以逐一对应到列表表达式。我们既可以用List(…)这样的模式来匹配列表的所有元素，也可以用::操作符和Nil逐步将列表解开。

示例变量：

1
2
val fruit = "apples" :: "oranges" :: "pears" :: Nil
val statuses = List(500, 404)

示例1：

1
val a :: b :: rest = fruit

示例2：

1
2
3
4
5
val List(a, b, c) = fruit // 可行
val List(_, b, c) = fruit // 可行
val List("apples", b, c) = fruit // 可行

val List("N/A", b, c) = fruit // 不可行

示例3：

1
2
3
4
5
6
7
val msg = statuses match {
  case List(404, 500) => "not found & error"
  case List(500, 404) => "error & not found"
  case List(500, x) => s"Error followed by $x"
  case List(e, x) => s"$e was followed by $x"
  case _ => "will not get here"
}

示例4：

1
2
3
4
val msg = statuses match {
  case x if x contains(500) => "has error"
  case _ => "okay"
}

示例5：

1
2
3
4
5
val fruit = "apples" :: "oranges" :: "pears" :: Nil
val msg = fruit match {
  case Nil => "N/A"
  case x :: xs => x
}

List中的方法

初阶方法

下表列出了List接口中的一些常用的初阶方法，其中有些方法是在List中直接定义的，有些则是继承自其它接口中的方法，更多可用的方法还有待继续探索。

方法名 示例 说明 时间复杂度
isEmpty: Boolean scala> List(1, 2).isEmpty
res3: Boolean = false		 检查列表是否为空列表 常量
length: Int scala> List(1, 2).length
res2: Int = 2		 返回列表长度 O(n)，n为列表长度
::[B >: A](x: B): List[B] scala> 1 :: List(2, 3)
res0: List[Int] = List(1, 2, 3)		 在列表前部添加元素 常量
:::[B >: A](prefix: List[B]): List[B] scala> List(1, 2) ::: List(3, 4)
res1: List[Int] = List(1, 2, 3, 4)		 拼接两个链表 O(n)，n为参数prefix的长度
head: A scala> List(1, 2).head
res4: Int = 1		 返回列表中第一个元素 常量
tail: List[A] scala> List(1, 2, 3).tail
res5: List[Int] = List(2, 3)		 返回列表中除第一个元素外的所有其它元素 常量
init: Repr scala> List(1, 2, 3).init
res6: List[Int] = List(1, 2)		 返回除最后一个元素外的所有其它元素 O(n)，n为列表长度
last: A scala> List(1, 2, 3).last
res7: Int = 3		 返回最后一个元素 O(n)，n为列表长度
apply(n: Int): A scala> List(1, 2, 3).apply(1)
res15: Int = 2		 返回指定索引位置的元素 O(n)，n为索引位置
indices: Range scala> List(1, 2, 3).indices
res18: scala.collection.immutable.Range = Range 0 until 3		 创建一个表示列表索引的Range
take(n: Int): List[A] scala> List(1, 2, 3).take(2)
res9: List[Int] = List(1, 2)		 返回列表的前n个元素 O(n)，n为要获取的元素个数
drop(n: Int): List[A] scala> List(1, 2, 3).drop(2)
res10: List[Int] = List(3)		 丢弃列表中前n个元素 O(n)，n为要丢弃掉的元素个数
splitAt(n: Int): (List[A], List[A]) scala> List(1, 2, 3).splitAt(1)
res14: (List[Int], List[Int]) = (List(1),List(2, 3))		 从指定位置切分列表 O(n)，n为切分位置的索引
reverse: List[A] scala> List(1, 2, 3).reverse
res8: List[Int] = List(3, 2, 1)		 将列表中元素按顺序反转 O(n)，n为列表长度
flatten[B]: CC[B] scala> List(Set(1, 2),Set(1, 2)).flatten
res16: List[Int] = List(1, 2, 1, 2)
zipWithIndex[A1 >: A, That]: That scala> List(1, 2, 3).zipWithIndex
res17: List[(Int, Int)] = List((1,0), (2,1), (3,2))
zip[A1 >: A, B, That] (that: GenIterable[B]): That scala> List(1, 2, 3).zip(List(“a”, “b”))
res19: List[(Int, String)] = List((1,a), (2,b))		 对两个列表执行拉链操作 O(n)，n为长度较小的列表长度
unzip[A1, A2](CC[A1], CC[A2]) scala> List((1,”a”), (2,”b”)).unzip
res21: (List[Int], List[String]) = (List(1, 2),List(a, b))		 对列表执行解拉链操作 O(n)，n为列表长度
copyToArray[B >: A](xs: Array[B], start: Int, len: Int) 将列表中的元素复制到数组，start为数组的起始索引

高阶方法

fold操作

如下图，List和LinearSeqOptimized都间接继承自TraversableOnce：

  • TraversableOnce中同时定义了fold、foldLeft和foldRight三个方法；
  • LinearSeqOptimized提供了优化过的foldLeft和foldRight实现；
  • List中直接定义了foldRight；
  • 这样对于List而言，fold、foldLeft和foldRight分别来自TraversableOnce、LinearSeqOptimized和List中的定义（如，下图中绿色字体所标识）；

我们先来看TraversableOnce.fold()的定义（如下），它直接调用了foldLeft，对于List而言，也就是LinearSeqOptimized中定义的foldLeft()：

1
def fold[A1 >: A](z: A1)(op: (A1, A1) => A1): A1 = foldLeft(z)(op)

对于List.foldRight()（如下），它通过将列表进行反转操作之后再进行foldLeft()来实现，也最终落实到了LinearSeqOptimized中定义的foldLeft()，（注意：因为要先将列表进行反转操作，反转操作需要一定的开销，所以在使用这个方法时要考虑到这一点）：

1
2
override def foldRight[B](z: B)(op: (A, B) => B): B =
  reverse.foldLeft(z)((right, left) => op(left, right))

接下来，我们看LinearSeqOptimized.foldLeft()的定义（如下）：通过迭代，将op()函数的计算结果作为每次迭代的临时结果，临时结果又作为下一次迭代的输入，以最后一次op()函数的计算结果作为最终结果并返回：

1
2
3
4
5
6
7
8
9
10
override /*TraversableLike*/
def foldLeft[B](z: B)(@deprecatedName('f) op: (B, A) => B): B = {
  var acc = z
  var these = this
  while (!these.isEmpty) {
    acc = op(acc, these.head)
    these = these.tail
  }
  acc
}

总结如下：

方法名 图示 说明 时间复杂度
fold() 1.方法的“零值”数据类型A1必须是当前列表元素下界（即，必须是列表元素同类型或为其父类型）；
2.方法的输出结果的数据类型与零值的数据类型A1是一致的；
foldLeft() 1.方法的“零值”数据类型B可以是任何数据类型；
2.方法的输出结果的数据类型与“零值”的数据类型B是一致的；
3.方法迭代op()函数是按列表由前向后进行的；
4.op: (B, A) => B
foldRight() 1.方法的“零值”数据类型B可以是任何数据类型；
2.方法的输出结果的数据类型与“零值”的数据类型B是一致的；
3.方法迭代op()函数是按列表由后向前进行的，因为需要先进行列表的反转，因此需要考虑反转操作带来的性能开销；
4.op: (A, B) => B：参数类型与foldLeft()中op() 参数类型相反，这是为了保持代表零值的类型和中间聚合的类型，靠右侧，以代表是右向进行的；

reduce操作

我们先来看TraversableOnce.reduce()的定义（如下），它直接调用了reduceLeft，对于List而言，也就是LinearSeqOptimized中定义的reduceLeft()：

1
def reduce[A1 >: A](op: (A1, A1) => A1): A1 = reduceLeft(op)

对于LinearSeqOptimized.reduceLeft()（如下），它直接使用的了foldLeft()进行实现：

1
2
3
4
override /*TraversableLike*/
def reduceLeft[B >: A](@deprecatedName('f) op: (B, A) => B): B =
  if (isEmpty) throw new UnsupportedOperationException("empty.reduceLeft")
  else tail.foldLeft[B](head)(op)

对于LinearSeqOptimized.reduceRight()（如下），它采用了递归调用op()函数的方式进行实现，没有进行反转的操作，所以该方法相对于foldRight()会有一定执行效率优势，但考虑到采用递归的方式，所以对于大规模的数据可能会存在一定的性能风险：

1
2
3
4
5
override /*IterableLike*/
def reduceRight[B >: A](op: (A, B) => B): B =
  if (isEmpty) throw new UnsupportedOperationException("Nil.reduceRight")
  else if (tail.isEmpty) head
  else op(head, tail.reduceRight(op))

总结如下：

方法名 图示 说明 时间复杂度
reduce() 1.方法的“零值”数据类型A1必须是当前列表元素下界（即，必须是列表元素同类型或为其父类型）；
2.方法的输出结果的数据类型与零值的数据类型A1是一致的；
reduceLeft() 参考foldLeft()图示 1.使用foldLeft()进行实现的；
2.方法的“零值”数据类型B可以是任何数据类型；
3.方法的输出结果的数据类型与“零值”的数据类型B是一致的；
4.方法迭代op()函数是按列表由前向后进行的；
5.op: (B, A) => B
reduceRight() 参考foldRight()图示 1.使用递归的方式进行实现的；
2.方法的“零值”数据类型B可以是任何数据类型；
3.方法的输出结果的数据类型与“零值”的数据类型B是一致的；
4.op: (A, B) => B：参数类型与reduceRight()中op() 参数类型相反，这是为了保持代表零值的类型和中间聚合的类型，靠右侧，以代表是右向进行的；

scan操作

scan操作的语义不同于fold和reduce操作：fold和reduce操作最终返回的是最后一次迭代中op函数结果，而scan操作则返回的是由每一次迭代中op函数结果所组成的一个集合，零值为集合中的第一项，即它记录了每一次迭代的结果。

TraversableLike.scan()：

1
def scan[B >: A, That](z: B)(op: (B, B) => B)(implicit cbf: CanBuildFrom[Repr, B, That]): That = scanLeft(z)(op)

TraversableLike.scanLeft()：

1
2
3
4
5
6
7
8
def scanLeft[B, That](z: B)(op: (B, A) => B)(implicit bf: CanBuildFrom[Repr, B, That]): That = {
  val b = bf(repr)
  b.sizeHint(this, 1)
  var acc = z
  b += acc
  for (x <- this) { acc = op(acc, x); b += acc }
  b.result
}

TraversableLike.scanRight()，该方法先进行一次反转，再进行了一次迭代计算，最后进行了一次结果的拼装：

1
2
3
4
5
6
7
8
9
10
11
def scanRight[B, That](z: B)(op: (A, B) => B)(implicit bf: CanBuildFrom[Repr, B, That]): That = {
  var scanned = List(z)
  var acc = z
  for (x <- reversed) {
    acc = op(x, acc)
    scanned ::= acc
  }
  val b = bf(repr)
  for (elem <- scanned) b += elem
  b.result
}

总结如下：

方法名 图示 说明 时间复杂度
scan() 1.方法的“零值”数据类型A1必须是当前列表元素下界（即，必须是列表元素同类型或为其父类型）；
2.方法的输出结果是元素类型与零值的数据类型A1是一致的元素组成的集合；
scanLeft() 参考foldLeft()图示 1.方法的“零值”数据类型B可以是任何数据类型；
2.方法的输出结果是元素类型与零值的数据类型B是一致的元素组成的集合；
3.方法迭代op()函数是按列表由前向后进行的；
4.op: (B, A) => B
scanRight() 参考foldRight()图示 1.使用三次迭代的方式进行实现的；
2.方法的“零值”数据类型B可以是任何数据类型；
3.方法的输出结果是元素类型与零值的数据类型B是一致的元素组成的集合；
4.op: (A, B) => B：参数类型与scanLeft()中op() 参数类型相反，这是为了保持代表零值的类型和中间聚合的类型，靠右侧，以代表是右向进行的；

高阶方法汇总

方法名 示例 说明 时间复杂度
map[B, That](f: A => B): That
flatMap[B, That] (f: A => GenTraversableOnce[B]): That
foreach[U](f: A => U)
filter(p: A => Boolean): Repr
partition(p: A => Boolean): (Repr, Repr)
find(p: A => Boolean): Option[A]
takeWhile(p: A => Boolean): List[A]
dropWhile(p: A => Boolean): List[A]
span(p: A => Boolean): (List[A], List[A])
forall(p: A => Boolean): Boolean
exists(p: A => Boolean): Boolean
sortWith(lt: (A, A) => Boolean): Repr

ListBuffer类型

TODO

Notes

本文基于Scala2.12.13

参考

1.《Programming in Scala Third Edition》16章、22章