Docs.com へのサインインに使うメール アドレスまたは電話番号を入力してください。 Office など、Microsoft の他のサービスで既にお使いのアカウントがあれば、そのアカウントを入力してください。
アカウントを記憶する
または次の方法でサインインします:
サインインすると、コンテンツのダウンロードや「いいね!」をすることができ、作成者が認識します。
埋め込みコード: scala.collection 再入門(改)
サイズの選択
@Scala関西Summit2016
フローチャートは(https://gist.github.com/amaya382/84c9d15b634dcbf53ea4ef0e46d31da1)
※連絡を頂ければCCBYとします
scala.collection 再入門( 改)
脱･初中級者を目指して [ ver. 2.12.0-M5 対応版 ] @Scala関西 Summit2016
amaya@amaya382
誰
2016/10/8
ITO Ryuichi(@amaya382)
大学院で GraphProcessingEngineとか NLPとか
Scala っぽい こと
Scala 関西Summit お手伝い 組
Functional Programming in Scala 読書会( 次回は10/30)
Scala( 入門レベル) を 薄い技術書に書き まとめたい… 夏コミ(?)
tags: scala,c#, カイオーガ, きん モザ, ボカロ,splatoon,μ's
「サンプルが List を使っていたから …」と なんとなく List を使っていませんか
配列に謎の安心感を抱いて なんとなく Array を使っていませんか
「 Scala と言えばとにかく immutable」と immutable に固執していませんか
高階関数が楽しくて なんとなくチェインさせていませんか
適材適所で Collection や操作方法を選択しましょう
💪 Scalaにおける 💪 💪 アルゴリズムとデータ構造力を鍛える 💪
Contents
種類編
scala.collection を Traversable から辿ってみる
操作編
for 式？メソッドチェーン？ 色々な操作方法とその仕組み
もう一歩踏み込むための Tips編
メソッドチェーンとの良い付き合い方
遅延評価
アンチパターンと愉快な仲間たち
今回やらないこと
コレクションメソッドの細かい話
scala.collection.parallel
Gen ～
Par ～
詳しい実装の話
～ Like
その他実用性が低そうな部分
モナモナしません
scala.collection をどれ だけ把握できていますか？
Trait
Class
Seq
List
Array
Range
e.g. 1 to 10
http://docs.scala-lang.org/resources/images/collections.immutable.png
多い
どれ使えばいいの
http://docs.scala-lang.org/resources/images/collections.mutable.png
※apply の 実装により, Trait であってもデフォルト実装の Collection としての初期化が可能
探索可能トレイト
foreach できる
順序付きトレイト
インデックスで
アクセス可能
線形トレイト
ポインタで
繋がれてる
集合トレイト
ユニークな値の集まり
繰り返し可能トレイト
Iterator を使ってforeach できる
辞書トレイト
key-value な
値の集まり
デフォルト実装
HashSet
HashMap
ソート済！
索引済みトレイト
インデックスによる
ランダムアクセスに強い
Vector
immutable( デフォルト)
Pick up!
Set, Map
HashSet, HashMap
TreeSet, TreeMap
IndexedSeq
LinearSeq
Stream
Queue
Array ( 後ほど)
( 補足) Iterator / Iterable
scala> val iter = Iterator(0, 1, 2)
iter: Iterator[Int] = non-empty iterator
scala> iter.foreach(println)
0
1
2
scala>
Iterator
データ群を舐めるための抽象的なデータ構造･手法
Collection が内部的に 用いる(has-a)
Collection ごとに適切なデータの舐め方を実装する
e.g. List => head :: tail
next() / hasNext()
最終的には NoSuchElementException … 終端
Iterable
Iterator を提供できる Collection を表す Trait
全ての Scala の Collection が継承している (is-a)
ポインタが終端まで進んだ
※foreach 等には
直接は利用されないことも
状態 (ポインタ )を持つ
scala> val list = List(1, 2, 3)
list: List[Int] = List(1, 2, 3)
scala> list.iterator.foreach(println)
3
保有データを Iteratorの形でコピー
( 補足) Set と Map
小泉花陽
イエロー ,
星空凛
グリーン ,
矢澤にこ
ピンク ,
Set
keys
values
Map
Map ≒ Set の値を key に, 加えて value をポインタとして保持
ベースとなるデータ構造はほとんど等しい
immutable.{HashSet, HashMap}
scala> val x = scala.collection.immutable.HashSet(1, 2, 3)
x: scala.collection.immutable.HashSet[Int] = Set(1, 2, 3)
Hash 値で
振り分け
32
1024
※Map[ 整数, _] に特化した IntMap, LongMap もある よ
Trie(32 分木) + Hash
検索･追加･削除 が 実質 o(1)
どの操作も速い
Set, Map のデフォルト実装
使い道 : 重複のない集合 (辞書 )を immutable で使いたい時
immutable.{TreeSet, TreeMap}
赤黒木
検索･追加･削除 が o( logn )
どの操作もそれなりに速い
ソート済み
SortedSet, SortedMap のデフォルト実装
使い道 : 重複のない集合 (辞書 )を ソート済みで扱いたい時 最悪計算量を重視する時
scala> val x = scala.collection.immutable.TreeSet(1, 2, 3)
x: scala.collection.immutable.TreeSet[Int] = TreeSet(1, 2, 3)
Nil
immutable.Range
scala> val x = scala.collection.immutable.Range(1, 5, 2)
x: scala.collection.immutable.Range = Range 1 until 5 by 2
scala> val x = 1 until 5 by 2
1 until 5
1, 2, 3, 4
5 to 1 by -2
5, 3, 1
※ 注意: ver 2.8 より 前 はチェーン先が遅延 評価, 以降は正格評価
範囲を表現しているだけ
head ･tail ･ﾗﾝﾀﾞﾑｱｸｾｽ が o(1)
値を追加するようなことはできない
to, until, by, 負値( 逆順)
使い道 : 範囲の決められた値のコレクションを扱う時 e.g. ループ用のインデックス
immutable.Vector
scala> val x = scala.collection.immutable.Vector(1, 2, 3)
x: scala.collection.immutable.Vector[Int] = Vector(1, 2, 3)
scala> val x = scala.collection.immutable.IndexedSeq(1, 2, 3)
x: scala.collection.immutable.IndexedSeq[Int] = Vector(1, 2, 3)
32 分木
head ･tail ･ﾗﾝﾀﾞﾑｱｸｾｽ･更新 ･先頭追加･末尾追加･length が 実質 o(1)
カタログスペック最強 … だが定数大きめ
ﾗﾝﾀﾞﾑｱｸｾｽに強く , その他もそれなり
IndexedSeq のデフォルト 実装 Range のデフォルト変換先
使い道 : ﾗﾝﾀﾞﾑｱｸｾｽを中心に 色々な操作をする時
※java.util.Vector とは関係ありません！！！
実体はこっち
immutable.List … ::(Cons) & Nil
abstract
scala> val x = scala.collection.immutable.Traversable(1, 2, 3)
x: scala.collection.immutable.Traversable[Int] = List(1, 2, 3)
scala> val x = scala.collection.immutable.List(1, 2, 3)
x: List[Int] = List(1, 2, 3)
scala> val x = 1 :: 2 :: 3 :: Nil
list match {
case Nil =>
...
case head :: tail =>
}
head
tail
Cons
単方向連結リスト . 再帰と相性◎
head ･tail ･先頭追加 が o(1), ﾗﾝﾀﾞﾑｱｸｾｽ･末尾追加 は o(n)
使い道 : ﾗﾝﾀﾞﾑｱｸｾｽがなく , 先頭追加を主とする時 head / tail を多用する時
immutable.Stream
scala> val x = scala.collection.immutable.Stream.from(0)
x: scala.collection.immutable.Stream[Int] = Stream(0, ?)
scala> x.take(3).toList
res14: List[Int] = List(0, 1, 2)
唯一遅延評価される Collection
無限リスト
遅延評価していること以外はほぼ List
head ･tail ･先頭追加 が o(1)
toList, fold 等のタイミングで評価される
immutable.Queue
Purely Functional Data Structures
Search
FIFO そのもの
FIFO で必要な操作は 全て 均し o(1)
使い道 : FIFO を immutable で使いたい時
immutable.Stack(LIFO) はdeprecated なの でimmutable.List を使う
( 補足) immutable と関数型 データ構造
list0
list1
※ Persistent data structure ※ immutable ≠ readonly
値が変わらないこと , immutableであることが保証されている → 部分データを使いまわせる (Data sharing)
vector0
vector1
Functional Programming in Scala / Scala 関数型デザイン& プログラミング
バッファトレイト
Wrapper 的な
ArrayBuffer
mutable
Buffer
ListBuffer
Seq, LinearSeq
Queue/Stack
mutable.{HashSet, HashMap}
add(8)
scala> val x = scala.collection.mutable.HashSet(1, 2, 3)
x: scala.collection.mutable.HashSet[Int] = Set(1, 2, 3)
hash(8) = 3
4
5
6
-
8
≒ java.util.{HashSet, HashMap}
immutable と実装が異なり 単純な Hash (chain)
検索･追加･削除 が o(1)
immutable 版より定数が小さい
使い道 : 少しでも高速な Set , Map を使いたい時 データの傾向により OpenHashMap と使い分け
Conflict!
OK!
hash’(8) = 4
使い道 : 少しでも高速な Set , Map を使いたい時 データの傾向により OpenHash Map と使い分け
mutable.ArrayBuffer
≒ java.util.ArrayList
内部に配列を保持
サンプルコードでよく使われるが …
殆どの場合 immutable.List に負ける残念な子
存在意義は …
ないわけではない
末尾追加とﾗﾝﾀﾞﾑｱｸｾｽが必要な場合に活躍
末尾追加した後に toList をしない場合に活躍
mutable.ListBuffer
≒ java.util.LinkedList (←は双方向 , ListBufferは単方向リスト )
内部にリストを保持
先頭追加 と 末尾追加 を両方用いる場合には活躍 (末尾追加のみは 先頭追加 + reverse で ok)
mutable.{Queue, Stack}
scala> val x = scala.collection.mutable.Queue(1, 2, 3)
x: scala.collection.mutable.Queue[Int] = Queue(1, 2, 3)
FIFO/LIFO そのもの
immutable 版と比べ素直な実装
FIFO/LIFO で必要な操作は全て o(1)
immutable 版より定数が 小さい
使い道 : 少しでも速い FIFO/LIFO を使いたい時
scala> val x = Array(1, 2, 3)
x: Array[Int] = Array(1, 2, 3)
-2
-1
※ver 2.8 以前 ほど ではない
≒ Javaの配列
実体は Java の配列
mutable です！！！
ﾗﾝﾀﾞﾑｱｸｾｽ･更新 が o(1)
標準ライブラリの †闇の力 †によって他のコレクションと遜色なく扱える
使い道 : 要素の追加がなく , ﾗﾝﾀﾞﾑｱｸｾｽをメインに行う時
適切な Collectionを見つけてくれる凄いやつだよ
https://gist.github.com/amaya382/84c9d15b634dcbf53ea4ef0e46d31da1
※ 最新版はGist を見てください
適切に Collection操作できていますか？
Scala での Collection への アクセス
※ 勝手に分類& 命名
Index-based (Random access)
for { i <- 1 to 10 } { collection(i) }
Traversal-based (Higher-order function)
map, filter, fold, foreach, …
Task-based
再帰
Index-based
Iterator の十八番
Scala では イマイチ
「計算にインデックスの値が必要な時」 , 「不規則なアクセスをする時」に使いましょう zipWithIndex も手段の一つ (= コレクションを舐めるような操作には使わない )
Array, Vector, ArrayBuffer, …
以上！ w
Traversal-based
for { i <- 1 to 10 } { println(i) } (1 to 10).foreach { i => println(i) } { var i = 1 while (i <= 10) { println(i); i += 1 } }
コンパイラに
おまかせあれ
※ 展開 イメージ
scala.collection の醍醐味
色々なアクセスパターンが高階関数として提供されている ( map , filter , …)
for 式も実はこれ
for 式は自動的に filter/withFilter/map/flatMap/foreach に展開
filter 等はwhile ループや再帰で実装
( 末尾) 再帰はwhile ループに展開
@annotation.tailrec def sum( seq: Seq[Int], acc: Int = 0): Int = seq match { case Nil => acc case h +: t => sum(t, acc + h) } sum(1 to 100) //5050
scala.collection の 醍醐味( その2)
特に immutable.List との相性が◎
Cons に よる パターンマッチ(::, +:)
Traversal-based より自由度高め. 使い分けはケースバイケース
必ず 末尾再帰 (!) にしましょう
最適化されて whileループに展開されます (= stack safe, 関数呼出コストﾅｼ )
@annotation.tailrec をお忘れず( 末尾再帰でないとコンパイルエラー)
Task-based(cont.)
※Intellij IDEA
Useless intermediate object
(1 to 10).filter(_ % 2 == 0).length
(1 to 10).count(_ % 2 == 0)
Complex
(1 to 10).foldLeft(true)((x, y) => x && y % 2 == 0)
(1 to 10).forall(_ % 2 == 0)
Simpler chain is BETTER!!!
メソッドチェーンとの良い付き合い方 (cont.)
なぜ汎用性を捨ててまでシンプルな chainを使うのか？
可読性
実行速度
コレクションメソッドを適切に選択して使う
数は多いが IDEならサジェストしてくれることも
Searching と Filtering を意識する(e.g. exists(_==x) / contains(x))
なぜ遅延評価？
例えば , list.map (...).filter(...).map(...).take(...)
前→後 一つ一つ順番に評価する必要がある
… けどまとめたらもっと最適な評価方法があるのでは？
そこで遅延評価
Haskell, C#(LINQ) などではコレクション操作は遅延評価がデフォルト
Scala のコレクションは正格評価… だが view を使うと遅延評価できる！
Stream 以外 で使える ！
モジュール性を維持したまま遅延評価の恩恵が受けられる！
Stream ではない 遅延評価 として のview
val words = Array.fill(1000000)("しんかんせんえんせんかんし") words.take(500000).find(word => word == word.reverse) words.view.take(500000).find(word => word == word.reverse)
(1 to 1000000).map(_ + 1).take(1) (1 to 1000000).view.map(_ + 1).take(1).force
(1 to 1000000).map(_ + 1).map(_ * 2).map(_ + 1)
(1 to 1000000).view.map(_ + 1).map(_ * 2).map(_ + 1).force
※ 手動でcompose 可能だが モジュール性が失われる
Example
take による中間コレクション生成コスト踏み倒し
map による中間コレクション生成コスト 踏み倒し
遅延評価の親戚 (1)
filter 1
filter 2
filter 3
filter 4
filter 5
map 2
map 4
(1 to 5). filter { i => println(s"filter $i") i % 2 == 0 }.map { i => println(s"map$i") i * 2 } (1 to 5). with Filter { i => println(s"filter $i") i % 2 == 0 }.map { i => println(s"map$i") i * 2 }
withFilter
中間オブジェクトを生成しないすごいやつだよ
直後が withFilter map flatMap foreach に限定される
(1 to 5).withFilter(_%2 == 0)
:FilterMonadic[Int, IndexedSeq[Int]]
遅延評価の親戚 (2)
list0.zip(list1).map(p => p._1 + p._2)
(list0, list1) .zipped.map(_ + _)
{Tuple2, Tuple3}#zipped
zip 処理とその後の処理を一気に実行
アンチパターンと愉快な仲間たち (別名 : 時間調整 )
list.length
for{ i <- 1 to 10 } { list(i) }
def f(l: List[Int]) = ...
var hm = mutable.HashMap(0, 1, 2)
import scala.collection.JavaConversions._
breakOut
アンチパターンと愉快な仲間たち (1)
Collection の大きさが必要となる時･ﾗﾝﾀﾞﾑｱｸｾｽが必要となる時は IndexedSeq を使う(IndexedSeq 以外でも高速な場合も有)
アンチパターンと愉快な仲間たち (2)
def ng(seq: Seq[Int], acc: Int): Int = seq match { case Nil => acc case head :: tail => ng(tail, acc + head) }
パターンマッチに注意！
順序付き Collectionでさえあれば良い時
条件にあった class/trait を指定する
def f(l: Seq[Int]) = ...
アンチパターンと愉快な仲間たち (3)
要素＼全体
var
val
immutable
.
アンチパターンと愉快な仲間たち (4)
import scala.collection.JavaConverters._
明示的に変換しましょう
アンチパターンと愉快な仲間たち (5)
(List)
List(1, 2, 3) .map(_ + 1)
List(1, 2, 3) .map(_ + 1)(collection.breakOut) : Set[Int]
(Traversable)
def map[B, That](f: A => B)(implicit bf: CanBuildFrom[List[A], B, That]): That
def map[B, That](f: A => B)(implicit bf: CanBuildFrom[Repr, B, That]): That
def breakOut[From, T, To](implicit b: CanBuildFrom[Nothing, T, To]): CanBuildFrom[From, T, To]
breakOut とは … の前にCollection の変換したいときありますよね？
map(...) のシグネチャはどうなっている？
アンチパターンと愉快な仲間たち (5)( cont.)
結局何なん
普段は … 暗黙的に決定される B uilderを使って map等の処理が行われる
breakOut を明示的に渡すと… 変換先の型が推論される 推論された型 のBuilder を使ってmap 等の処理が行われる toSet 等する必要がなくなる
結論 : 型推論 isつよい
Thank you for listening! -References- Scala Documentation (http://docs.scala-lang.org/) ひしだ ま’s 技術 メモページ (http://www.ne.jp/asahi/hishidama/home/tech/scala/) Scala Collections Tips and Tricks (https://pavelfatin.com/scala-collections-tips-and-tricks/)
batched queue
searching: 一つの解を求めるときに使う. 総当り前提ではない(e.g. find)
filtering: 複数の回に絞り込むときに使う. 総当り前提(e.g. filter)diate object
2016/10/