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
三种操作
-
toinclusive -
untilexclusive -
byto 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))
}
