Week6学习笔记

Other Collections

我们已经知道List是线性的：取第一个元素是比取中间或者最后一个元素要快得更多的。但是我们有一个可选的Sequence Implementation，即Vector

This one has more evenly balanced access patterns than list.

因为Vector和List的数据结构是不一样的。List采用类似链表的结构，但是Vector采用的是树结构。

So a vector of up to 32 elements is just an array, where the elements are stored in sequence.

Vector这种结构可以更好地利用到系统Cache，并且查找速度会很快。但是如果我们只需要取第一个节点即head，List的性能还是要比Vector好的，因为Vector还需要向下查找最左端的那个节点。

Seq是Iterable的一个子类。
Array和String支持同样的Seq的操作，可以被隐式地转换为Seq，它们不能继承于Seq，因为它们是直接使用Java里面的结构。
Array[T]相当于Java中的T[],初始化之后就长度不可变，Java中数组支持协变，但是Scala中数组不支持协变。

Ranges

三种操作

to inclusive
until exclusive
by to determine step value

一些简单function

  def combinations(M : Int, N : Int): immutable.Seq[(Int, Int)] = (1 to M) flatMap (x => (1 to N) map (y => (x, y)))

  def scalarProduct(xs : Vector[Double], ys : Vector[Double]): Double = (xs zip ys) map (xy => xy._1 * xy._2) sum
  
  // 一个可选的方式是使用 `pattern matching function value`
  def scalarProduct(xs: Vector[Double], ys: Vector[Double]): Double = (xs zip ys).map {
    case (x, y) => x * y
  }.sum
  
  // 求质数
  def isPrime(n : Int) : Boolean = (2 until n) forall (x => n % x == 0)

Combinatorial Search and For-Expressions

LinearSeq和IndexedSeq都是继承与Seq，但是两者构造List底层数据结构是不一样的
List继承于LinearSeq，Vector,Range继承于IndexedSeq

    val names: Array[String] = for (p <- persons if p.age > 20) yield p.name
    val names: Array[String] = persons filter (_.age > 20) map (_.name)
    
    // 使用 {} 可以写多个条件
    for {
      i <- 1 to 10
      j <- 1 to 10
      if isPrime(i + j)
    } yield (i, j)
    
  def scalarProduct(xs: Vector[Double], ys: Vector[Double]): Double =
    (for ((x, y) <- (xs zip ys)) yield x * y).sum

Combinatorial Search Example

Set

Set是无序的
没有重复元素
The fundamental operation on set is contains

`N-Queens` (N皇后问题)

  def queens(n: Int): Set[List[Int]] = {

    def isSafe(col: Int, queens: List[Int]): Boolean = {
      queens.indices forall ((p: Int) => {
        val r = queens.length - p - 1
        (queens(p) != col) && ((queens.length - r).abs != (col - queens(p)).abs)
      }
        )
    }

    def placeQueens(k: Int): Set[List[Int]] = {
      if (k == 0)
        Set(List())
      else
        for {
          queens <- placeQueens(k - 1)
          col <- 0 until n
          if isSafe(col, queens)
        } yield col :: queens                // 这里有点坑，因为运用的是 :: 所以最后一个元素是在最左边
    }

    placeQueens(n)
  }

Maps

Maps are Iterables.
Maps extend iterables of key/value pairs. 构造map的时候可以采取(key, value)形式
Maps are functions. Class Map[key, value] also extends the function type Key => Value, so maps can be used everywhere functions can.

The Option Type

    // map get key 返回一个Option类型
    
    trait Option[+A]
    case class Some[+A](value: A) extends Option[A]
    object None extends Option[Nothing]

Sorted and GroupBy

    val fruit = List("apple", "pear", "orange", "pineapple")
    fruit sortWith (_.length < _.length) // List("pear", "apple", "orange", "pineapple")
    fruit.sorted // List("apple", "orange", "pear", "pineapple")

Map example

A polynomial can be seen as a map from exponents to coefficients.

class Poly(terms0: Map[Int, Double]) {
  def this(bindings: (Int, Double)*) = this(bindings.toMap)

  val terms: Map[Int, Double] = terms0 withDefaultValue 0.0

  def +(other: Poly) = new Poly(terms ++ (other.terms map adjust))

  def adjust(term: (Int, Double)): (Int, Double) = {
    val (exp, coeff) = term
    exp -> (coeff + terms(exp))
  }

  override def toString: String =
    (for ((exp, coeff) <- terms.toList.sorted.reverse)
      yield coeff + "x ^ " + exp) mkString " + "
}

  //上面 + 函数可以替换为下面，并且效果更高
  def +(other: Poly) = new Poly((other.terms foldLeft terms)(addTerm))

  def addTerm(terms: Map[Int, Double], term: (Int, Double)) : Map[Int, Double] = {
    terms + (term._1 -> (terms(term._1) + term._2))
  }