LoginSignup
0
0

More than 5 years have passed since last update.

@yohei1126(Yohei Onishi)

Programming in Scala: Chapter 24 Collections in Depth

Last updated at Posted at 2017-07-27

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

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として登録されている。
      • 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を利用できる。
0
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
0
0