17. Collections
scalaはcollectionsの豊富なライブラリを持っている。
既にarray, list, set, mapについて見て来た。
collectionsの継承階層を見る。
色々なcollectionsの使い方を見る。
speed, space, requirements on input dataのトレードオフ等。
17.1 Overview of the library
scalaのcollectionsライブラリは多くのclass, traitを巻き込んでいる。
全体像をScaladocから描き出すのは簡単ではない。
全体像を理解するために必要なtraitのみを下記に示す。
+- Seq // 順番ありの並び(sequence), array, list
Iterable <-+- Set // 重複無しの要素の集まり。重複は==で決める。
+- Map // keyとvalueの組の集まり。
Iterable
Iterable[A]のIterator[A]を生成するメソッドを有する。
def elements: Iterator[A]
elementsは唯一の抽象メソッド。
具象メソッドも多数定義している。
全てelementsが返すIteratorを使用して実装されている。
Iterator
Iterableと同じ多数のメソッドを持っている。
継承階層は異なる。
AnyRef <--- Iterator
Iterableは繰り返しが可能な型表現する。
** Iteratorを生成出来る型。
複数回走査されるかもしれない。
Iteratorは繰り返しに使われるメカニズムそのもの。
一回しか走査出来ない。
再度走査した場合はもういちどIteratorを生成する必要ある。
next, hasNext
多くの具象メソッドがnext, hasNextを使ってIteratorに実装されている。
next, hasNextは抽象メソッドでmix-inする側で定義する。
17.2 Sequences
trait Seqを継承している、順序付きのデータ列のクラス。
1番目、2番目、103番目などの順番が存在する。
Lists
一番重要なsequence type。
先頭への追加削除は早い。
後ろの要素へのアクセスはリストを走査するので遅い。
この実装は多くのアルゴリズムを実装するのに適している。
パターンマッチングなど。
Arrays
任意の要素に効率良くアクセス、更新できる。
0始まりのインデックス。
大きさは固定。
要素は変更可能(mutalble)
javaの配列と互換性がある。
ただし()で要素にアクセスするので注意。
List buffers
import scala.collection.mutable.ListBuffer
mutable
先頭に加えて末尾にも効率良く要素を追加できる。
+= append (末尾に追加)
+: prepend (先頭に追加)
目的のリストを生成したらtoListでListを取得出来る。
?? これが主な使い方? ListからListBuffersへの変換は?
末尾再帰以外の場合のstack overflowを避けるためにも使える。
再帰の代わりにforやwhileとListBufferを組み合わせて使う。Section 22.2
Array buffers
import scala.collection.mutable.ArrayBuffer
長さを変更可能Array
Arrayで出来ることもほとんど実施可能。少しだけ遅い。
先頭と末尾から追加(+=, +:)削除(-=)可能。
平均固定時間で実行できるが、メモリ確保のために線形時間が掛かる場合もある。
?? 末尾から削除のメソッドが分からない。?
Queues
mutable, immutable両方のクラスがある。
importや階層を明示的に指定して使い分ける。
import scala.collection.immutable.Queue
scala> val has1 = empty.enqueue(1)
scala> val has123 = has1.enqueue(List(2, 3))
scala> val (element, has23) = has123.dequeue
import scala.collection.mutable.Queue
scala> val queue = new Queue[String]
scala> queue += "a"
scala> queue ++= List("b", "c")
scala> queue.dequeue
Stacks
mutable, immutable両方のクラスがある。
importや階層を明示的に指定して使い分ける。
import scala.collection.immutable.Stack
import scala.collection.mutable.Stack
push, pop, top(peekの意味)でアクセスする。
Strings (via RichString)
string自体はcollectionではない。
stringにない操作を行った場合RichStringにimplicit conversionされる。
Predefにimplicit conversionが定義されている。
RichStringはSeq[Char]
17.3 Sets and maps
mutableとimmutable両方のtraitがある。
MapやSetという名前のtraitは3種類ある。
defaultではimmutableのtraitが使われる。
immutableを推奨する意図があるから。
** 色々できるが黙って使うと推奨になると言うのが良い。
object Predef {
type Set[T] = scala.collection.immutable.Set[T]
type Map[K, V] = scala.collection.immutable.Map[K, V]
val Set = scala.collection.immutable.Set
val Map = scala.collection.immutable.Map
// ...
}
上記のPredefでの定義でdefaultの動作を決めている。
type～はfull nameのalias
val～はsingleton objectへの参照を保存。
mutable, immutable両方使いたいとき。
import scala.collection.mutable
val mutaSet = mutable.Set(1, 2, 3)
val immutaSet = Set(1, 2, 3)
Using sets
重複なしの要素を含むcollection
重複は==メソッドで判定する。
** Mapのkey部分のみと似ている。
immutable
+, - で要素の追加削除
++, -- で要素Listの追加削除
mutable
+=, -= で要素の追加削除
++=, --= で要素Listの追加削除
clear で全要素削除
共通
Set(1, 2, 3)で生成
Set.empty[T]で空のSetを生成
size, contains
Using maps
keyとvalueの両方の型指定が必要
var m = mutable.Map.empty[String, Int]
keyとvalueの組の辞書、連想配列。
配列はkeyが0始まりで連続の整数のMapと似ている。
値の設定、参照はArrayと同様。
m("hoge") = 1, val i = m("hoge")
key -> value
(key, value): Tuple2[K, V] のsyntactic sugar。
immutable
+, - で要素の追加削除
++, -- で要素Listの追加削除
mutable
+=, -= で要素の追加削除
++=, --= で要素Listの追加削除
m(k) = v
共通
Map(k1 -> v1, k2 -> v2, ...)
Map.empty[K, V]
v = m(k)
m.keySet でキーのSet, Set(k1, k2, ...)
m.keys, m.values でキー、値のIterator
size, contains, isEmpty
Default sets and maps
mutable
defaultではHashSet, HashMapなどが使われる。
効率良いO(1)のアクセスが可能。
immtable
5より小さい場合は効率化のため各サイズに合わせてた専用のクラスが使われる。
たとえば、scala.collection.immutable.Set3 等。
5以上の場合はmutableと同様にHashSetなどが使われる。
Sorted sets and maps
immutableのSetもしくはMapのkeyに対して順番に並べられたSortedSet,Mapがある。
mutableはなし
実装はred-black treeをつかったTreeSet, Mapがある。
red-black treeはself-balancing binary search tree
順序はOrdered traitをmix-inするかimplicit conversion出来るtypeを使う。
順序通り走査ができるIteratorを使える。
Synchronized sets and maps
thread-safeなMapを使いたい場合あはSynchronizedMap traitをmix-inする。
new HashMap[String, String] with SynchronizedMap[String, String] {
override def default(key: String) = "Why do you want to know?"
}
コンパイラはHashMapにSynchronizedMapをmix-inした人工サブクラスを生成。
defaultメソッドのoverrideも出来る。
keyが存在しない時に行う動作を定義できる。
newでそのインスタンスを生成する。
java.util.concurrentが使える場合もある。
unsynchronized collectionsをScala actorsと一緒に使う方法もある。Chapter 30
17.4 Selecting mutable versus immutable collections
mutableとimmutableどちらが良いかはケースバイケース。
迷ったらimmutableにするのを推奨。後で必要になったらmutableに変更する。
mutableで作ってあるコードが分かり難かったらimmutableにした方が良いかも。
特にちゃんとコピーを取っているか心配だったり誰が変更するのかきになるとき。
mutableとimmutableだとimmutableの方が小さくて早い。
mutableのHashMapは空で80byte, 各要素16byteのオーバーヘッドあり
immutableだと空は一つのオブジェクト共有するのでポインタ領域のみ。
さらに1～4要素は個別タイプがあるので16～40byteしか使わない。
少ない要素数ならimmutableを使った方が効率が良い。
mutableからimmutableへの変更
immutableは+=などの=を使ったメソッドが定義されていない。
a += b がない場合はsyntactic sugarで a = a + b と解釈される。
a はvar, mutableである必要がある。
+=だけではなくて、=を使ったすべてのメソッドに適用される。
collectionに限らず全ての型に対してこのsyntactic sugarを使える。
17.5 Initializing collections
コレクションの初期化方法についての考察。
factory methodに初期要素を渡す。
companion objectのapply methodを使う。
一番一般的な方法。
要素の型については通常はコンパイラの型推論に従えば問題ない。
明示的な型指定をした方が良い場合もある。
初期要素よりも上位の型を指定したい場合等。
特に後から要素が変更になるmutableの場合。
他のコレクションの要素で初期化したい場合。
空のコレクションを作って++でListを渡して作成する。
TreeSet[String]() ++ List("c", "b", "a")
Converting to array or list
toArrayやtoListを実行すれば良い。
順序は変換前のcollectionのIteratorの順序になる。
初期化に使ったList等の順に戻る訳ではない。
TreeSet[String]() ++ List("c", "b", "a").toList => List("a", "b", "c")
通常は全要素のコピーになるので大量だと時間が掛かる。
少ない要素数であればあまり気にする必要はない。
?? 少ない要素の場合が多いと言いたい?
Converting between mutable and immutable sets and maps
mutable<->immutableで変換したい場合も空のコレクションと++メソッドが使える。
変換後のからのコレクションに++で変換前のコレクションを追加する。
17.6 Tuples
Tuple少ない固定数の要素の組を一つにまとめて扱うためのもの。
複数の型を混ぜて格納出来る。
List[Any]やArray[Any]も色々な型を格納している様に見えるが、そうではない。
Anyと言う単一の型を格納しているだけ。Anyに適用出来ることしか出来ない。
val x :: y :: z :: nil = List[Any](1, 2, "abc")
val a = x + y // 出来ない
val b = z.toList // 出来ない
同等のことを実施するためにはdown castが必要。
Tuple複数の型を格納出来る。
それぞれの要素にはその型に適用できることが出来る。
val (x, y, z) = (1, 2, "abc")
val a = x + y // 出来る
val b = z.toList // 出来る
down castしなくても型情報が保持されているので問題ない。
意味的にまとまりのない複数の値を組み合わせて扱いたい場合に便利。
複数の値を返すメソッドを作りたい場合に便利。
型(class)を定義しても同じことは出来る。
型を定義するまでもないときはtupleが有効。
意味のあるまとまりの場合はclassにすべき。
たとえば年、月、日の組み合わせならDateクラスを定義すべき。
簡単なのでtupleを乱用しない様注意が必要!!
各要素へのアクセスは._N。Nは1始まり。
(1, 2)._2
パターンマッチングで各要素を取り出すこともできる。
val (x, y) = (1, 2)
()がないと別の意味に解釈されるので注意!!
multiple definitionと解釈される。Chapter 18
17.7 Conclusion
collection libraryと重要なclass, traitの概要。
Scaladocから詳細な情報を読み取れる様になったはず。
0 件のコメント:
コメントを投稿