Programming in Scala: Chapter 24 Collections in Depth

  • 0
    いいね
  • 0
    コメント

    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を利用できる。