Programming in Scala: Chapter 24 Collections in Depth


# 24.10 Array

* Scala の Array は Java の Array と1対1で対応する。
  * Array[Int] -> int[]

* ジェネリックのサポート

```
scala> val as = new Array[String](3)
as: Array[String] = Array(null, null, null)

scala> as(1) = "ss"

scala> as(2) = 1
<console>:13: error: type mismatch;
 found   : Int(1)
 required: String
       as(2) = 1
```

---

* sequence 操作をサポートしている。

```
scala> val a1 = Array(1,2,3)
a1: Array[Int] = Array(1, 2, 3)

scala> val a2 = a1 map (_ * 3)
a2: Array[Int] = Array(3, 6, 9)

scala> val a3 = a2 filter (_ % 2 != 0)
a3: Array[Int] = Array(3, 9)

scala> a3.reverse
res0: Array[Int] = Array(9, 3)
```

---

* Scala の Seq と互換性がある。Seq[T] が必要な場所で、Array[T]を渡すことができる。
  * これは implicit conversion で実現されている。Array が Seq として扱われる時は、Seq のサブクラス WrappedArray にラップされる。

```
scala> val seq:Seq[Int] = Array[Int](1,2,3)
seq: Seq[Int] = WrappedArray(1, 2, 3)
scala> seq.toArray
res3: Array[Int] = Array(1, 2, 3)
```

---

* ジェネリクスのサポート	
	* Array[T] はランタイムで Java のプリミティブ型の配列（int[]など）に対応。
	* ジェネリック配列は、プリミティブもしくはObjet配列より、3-4倍遅い。これは、ジェネリック配列にアクセスする際に、実際の型を決定する処理が入るため。パフォーマンスが重要な場面では、ジェネリクス配列は使ってはいけない。

---

* ジェネリクス配列を生成するためには、コンパイラに型の情報を少し教える必要がある。
	* 以下は、引数で渡された vector の偶数番地の要素を配列で返すメソッド。
	* 型パラメタTに対応する実際の型は実行時に消されるため、以下はコンパイルエラーになる。

```
> def evenElem[T](xs: Vector[T]): Array[T] = {
    val arr = new Array[T]((xs.length + 1)/2)
    for (i <- 0 until xs.length by 2)
      arr(i / 2) = xs(i)
    arr
  }
> error: cannot find class tag for element type T
       val arr = new Array[T]((xs.length + 1)/2)
```

---

* ClassTag で実行時に型パラメタの型に関するヒントを教える必要がある。
	* このClassTagは、21.6で説明のあったコンテキスト境界を利用している。
	* コンパイラが、プリミティブ型のClassTagを自動作成してくれる。

```
> import scala.reflect.ClassTag
> def evenElems[ T: ClassTag]( xs: Vector[ T]): Array[ T] = {
    val arr = new Array[ T](( xs.length + 1) / 2)
    for (i <- 0 until xs.length by 2)
      arr( i / 2) = xs( i)
    arr
  }
evenElems: [T](xs: Vector[T])(implicit evidence$1: scala.reflect.ClassTag[T])Array[T]
> evenElems(Vector(1,2,3,4,5))
res4: Array[Int] = Array(1, 3, 5)
> evenElems( Vector(" this", "is", "a", "test", "run"))
res5: Array[String] = Array(" this", a, run)
```

---

# 24.11 String

* String も Seq に変換可能。String は直接 Seq 互換であるわけではなく、2つの implicit conversion を利用して、変換している。

---

* 以下は高優先度の変換。StringからStringOpsへ。

```
scala> val str = "hello"
str: String = hello

scala> str.reverse
res6: String = olleh

scala> str.map(_.toUpper)
res7: String = HELLO

scala> str drop 3
res8: String = lo

scala> str slice(1,4)
res9: String = ell
```

---

* 以下は、低優先度の変換。StringからWrappedString（immutable.IndexSeqのサブクラス）へ。

```
scala> val s: Seq[Char] = str
s: Seq[Char] = hello
```

---

# 24.12 Performance Characteristics

* 性能比較テーブルは、[Scala公式ドキュメント](http://docs.scala-lang.org/ja/overviews/collections/performance-characteristics.html)を参照。
* Haoyi 氏（Scala.jsの初期のcontributor）によるベンチマーク: 
	* [Benchmarking Scala Collections](http://www.lihaoyi.com/post/BenchmarkingScalaCollections.html)
	* [Benchmark code](http://www.lihaoyi.com/post/BenchmarkingScalaCollections.html#benchmark-code)

---

## Take Aways

* Hayoi 氏のベンチマークで「Take Aways」のセクションにサマリが記載されている。

* Arrays は最高
  * unboxed な プリミティブ型入れるは、boxed 版よりメモリ使用量が 1/4〜1/5。これは
	  * （例）Array[Int] vs Array[java.lang.Integer]
  * 2つのArray（boxed版であっても） の結合は immutableなListやVectorの結合よりパフォーマンスが良い。これはイシュー[SI-4442](https://issues.scala-lang.org/browse/SI-4442)として登録されている。
	  * fancyなPersistent Data Structorをくっつけるより、コピーする方が速い。
	  * 病的なまでに要素1個1個を作らない限りは、Arrayの方が速い。（pathological build-up-element-by-element use case）

---

* Sets と Map は遅い
	* 全体的にSetやMapの操作はVectorよ10倍遅い。
		* これはハッシュ計算や同一性チェックにコストがかかるため。
	* もし要素数が比較的小さく、パフォーマンスが課題なら、各要素に整数IDを割り当て、SetとMapをVector[T]で代替することを考えるべき。要素が全部ユニークだとわかっているなら、Array、Vector、Listでも良い。

---

* Lists vs Vectors
	* メモリ使用量
		* ListはVectorの2倍のメモリを使う。VectorはArrayと比較的近い。
	* 性能
		* :+ による要素の追加：ListはVectorより5-15倍速い
		* .tailを使った要素の破棄：Listの方が50-60倍速い。
		* indexによる要素のlookupはVectorでもOK。Listの場合 O(n)。普通のListは高コスト。
		* iterationは同じくらい。
	* まとめ
		* 少しずつ要素を作ったり、削除したり、するならListが良い。
		* indexで参照するならVectorが必須。
		* Vectorで要素ごとの追加・削除は遅い。Listを使うべき。

---

* Lists VS mutable.Buffer
	* mutable.Bufferの方がindexによるlookupが速い。
	* Listはpersistent、Listのコピーに操作を加えても、コピー元には影響しない。mutable.Bufferはこれができない。
	* Listは最後の要素がiteration順序の最初に追加される。mutable.Bufferは最初の要素が最初に追加される。
	* mutable.BufferはListの半分のメモリオーバヘッド。

---

* Vectors はそこまで良いわけではない
	* 要素数が少ないvectorを作ると、1/5がオーバヘッド。要素数が多い場合は問題なし。
	* 要素ごとの追加はList、mutable.Bufferより5-15倍遅い。Arrayより40倍遅い。
	* indexによるlookupは、Arrayやmutable.Bufferよりかなり遅い。
	* Vecotorの結合はListより2倍速い。Arrayより10倍遅い。
	* 多目的なコレクションとしては"acceptable"
		* おかしな使い方しなければだいだい平均的な結果。
		* ただし、「理想的」なデータ構造と比べると共通の処理がかなり遅い。Vectorへの要素追加より5-15倍遅い。Arrayへのindex lookupよりかなり遅い。など。

---

# 24.13 Equality

* 異なるカテゴリのコレクションであれば、内容の如何にかかわらず、常に不一致。
* 同じカテゴリのコレクションであれば、内容が同じの場合に同一とみなす。

```
> List(1,2,3) == Vector(1,2,3)
res10: Boolean = true

> import scala.collection.immutable.{HashSet, TreeSet}
> HashSet(1,2) == TreeSet(2,1) 
res14: Boolean = true
```

* mutable collectionの場合、評価のタイミングによっては内容が異なる可能性がある。

---

# 24.14 Views

* コレクションの変換（map、filter）を行う方法として、strictとlazyがある。
	* strict：全要素と一緒に新しいコレクションを作る。
	* lazy：変換後のコレクションのプロキシだけ作り、その要素は必要になった時に作る。 
* デフォルトのコレクション変換は strict だが、strictはパフォーマンスに問題がある場合あり。
	* 以下の場合、1回目のmapの結果が生成された後、2回目のmapが生成される。途中結果はリソースの無駄。
	* 単一モジュール内であれば2つのmapを1つにまとめることもできるが、それぞれ別のモジュールにある場合、それもできない。

```
> val v = Vector( 1 to 10: _*)
v: scala.collection.immutable.Vector[Int] = Vector(1, 2, 3, 4, 5, 6, 7, 8, 9, 10)
> v map (_ + 1) map (_ * 2)
res15: scala.collection.immutable.Vector[Int] = Vector(4, 6, 8, 10, 12, 14, 16, 18, 20, 22)
```

---

* この問題は view を利用した遅延評価で解決できる。以下の例では、変換元の vector から view を取得して、それに対して上記と同じ2回のmapを実行している。
	* （注）個別メソッド view、map、map、force の呼び出しを順番に行った場合の時系列的な変化は書籍を参照。
	* 2つのmapは即座に実行されない。forceが実行された時に strict な変換として即座に評価される。

```
> (v.view map (_ + 1) map (_ * 2)). force
res16: Seq[Int] = Vector(4, 6, 8, 10, 12, 14, 16, 18, 20, 22)
```

---

## view を使いたい理由(1) パフォーマンス

以下の回文を見つけるコードにおいて、

```
> def isPalindrome( x: String) = x == x.reverse
> def findPalindrome( s: Seq[ String]) = s find isPalindrome
```

以下の場合、999,999 文字が中間結果に格納されてしまう。

```
> findPalindrome( words take 1000000)
```

viewを使うと、中間結果は生成されない。

```
> findPalindrome( words.view take 1000000)
```

---

## view を使いたい理由 (2) mutable sequence

* view によって sequence の部分に対して変換をかけることができる。
* 以下の例の場合、viewでarrの部分sequenceであるsubarrを作成し、arrのうちsubarrの部分だけnegate（否定の意味）メソッドによる変換をかけている。

```
> val arr = (0 to 9). toArray
arr: Array[Int] = Array(0, 1, 2, 3, 4, 5, 6, 7, 8, 9)
> val subarr = arr.view.slice( 3, 6)
subarr: scala.collection.mutable.IndexedSeqView[
> def negate( xs: collection.mutable.Seq[ Int]) =
    for (i <- 0 until xs.length) xs( i) = -xs( i)
negate: (xs: scala.collection.mutable.Seq[Int])Unit
> negate (subarr)
> arr
res20: Array[Int] = Array(0, 1, 2, -3, -4, -5, 6, 7, 8, 9)
```

---

## strict と lazy の使い分け

* 小さいコレクションに対しては、strict 変換による中間成果物の生成より、lazy変換の方がオーバヘッドが大きい。よってstrictで良い。
* 副作用がある変換の場合、lazy 変換はわかりづらい。strictにするべき。
  * Scala 2.8までは、Range型(以下のfor文内）は遅延評価が適用され、viewのように振る舞う。以下のforは後者のmapと同値であり、実際にはactorが作成されない。
  * 2.8 以降は、コレクションの lazy 変換は streams と view だけになった。

```
> val actors = for (i <- 1 to 10) yield actor { ... }
> val actors = (1 to 10) map (i => actor { ... }）
```

---

## viewを使って良い場合

* 純粋関数なコード・・・副作用のないコレクション変換
* mutable なコレクションへの明示的な変更

# 24.15 Iterators

* Iterator はコレクションの要素を1つずつ操作する方法を提供する。
* 基本的な操作
	* `hasNext`：次の要素がある場合は true
	* `next`：次の要素を返し、内部状態を次へ進める。

```
> val it = Iterator(" a", "number", "of", "words")
it: Iterator[String] = non-empty iterator
> while (it.hasNext) println( it.next())
 a
number
of
words
```

---

* 上記のループは forach や for で簡潔に書ける。

```
> it foreach println
> for (elem <- it) println(elem)
```

* iteratorはコレクションと共通したメソッドを提供する。ただし、itereatorは、メソッドを呼び出すと内部状態が変わる。
* （例）iteratorとコレクションのforeach の違い
	* iterator の `foreach` は、最後の要素に来るとループが止まる。その後にnextを呼ぶと `NoSuchElementException` を返す。
	* コレクションの foreach はコレクション内の要素の数は変更しない。

```
scala>val it = Iterator(" a", "number", "of", "words")
it: Iterator[String] = non-empty iterator

scala> it foreach println
 a
number
of
words

scala> it foreach println
val l = List(1,2,3,4)
l: List[Int] = List(1, 2, 3, 4)

scala> l foreach println
1
2
3
4

scala> l foreach println
1
2
3
4
```

---

## Buffered Iterator

* BufferedIteratorはIteratorの次の次の要素を見たい時に使う。
* （例）以下の場合、最初の要素がスキップされる。

```
// This won't work
> def skipEmptyWordsNOT(it: Iterator[ String]) = {
    while (it.next().isEmpty) {}
  }
```

* BufferedIteratorの場合、headで、iteratorを先に進めずに、最初の要素をheadで取得できる。

```
> def skipEmptyWords( it: BufferedIterator[ String]) = while (it.head.isEmpty) { it.next() }
```

---

# 24.16 Creating collections from scratch

省略

---

# 24.17 Conversions between Java and Scala collections

* `collection.JavaConversions._` を importすることで、JavaとScalaのコレクションを相互に変換する implicit conversionを利用できる。