S-JIS[2011-02-13/2016-06-18] 変更履歴

Scalaコレクション

Scalaコレクション(要素の並び・集合・グループ)のメモ。


概要

Scalaのコレクションは不変(イミュータブル・immutable)なものと可変(ミュータブル・mutable)なものがあり、基本的には不変な方を使用するのがScalaの方針。
大抵の不変なクラスはデフォルトで使える(Predef別名(type)が定義されている)のに対し、可変な方は自分でインポートしないと使えないようになっている。
(全然関係ないが、ミュータントと言えば化け物・変異・変わってしまったもの)

Javaでは代表的なコレクションはList・Map・Setだと思うが、ScalaではSeq・Map・Setとなっているようだ。
(ScalaのListはSeqから派生している)

Scalaのコレクションにはコレクションを操作する為のメソッドがいっぱいある。
Javaのコレクション操作メソッドとはかなり異なっており、たぶん関数型言語らしい構造・特徴なのだと思う。

コレクションについては以下のサイトが非常に参考になります。
(参考になるというより、Scala 2.8 コレクションAPIは必見)

Scala 2.8 コレクション API eed3si9nさんが「The Scala 2.8 Collections API」を翻訳したもの。
Scala 2.8 コレクションAPI るとさんが「The Scala 2.8 Collections API」を翻訳したもの。
Scala コレクションのアーキテクチャ eed3si9nさんが「The Architecture of Scala Collections」を翻訳したもの。

Scala2.9では、マルチスレッドで並列で実行できる並列コレクションが新設された。[2011-09-18]


コレクションの種類

eed3si9nさんの可変コレクションおよび不変コレクションの下の方に出ている派生関係の図が非常に分かり易い。
また、実際にどのクラスを使うべきかについては、るとさんの性能特性の表が非常に参考になる。

イミュータブル(不変)なコレクションはscala.collection.immutableパッケージにある。
ミュータブル(可変)なコレクションはscala.collection.mutableパッケージにある。

トレイト 不変 可変 Java相当 備考
Traversable       探索可能トレイト。全てのコレクションの親トレイト。
このトレイトではforeachのみが抽象メソッドで
それ以外はTraversableLikeで定義されている。
Iterable       繰り返し可能トレイト。
IterableはTraversableの(唯一の)直系であり、
Iterableの直下にSeq・Map・Setが居る。
Gen〜       Scala2.9では並列コレクションが増えた。[2011-09-18]
その為、「通常のコレクション」と「並列コレクション」の共通部分として、Genで始まるトレイトが出来たようだ。
Par〜       Scala2.9の並列コレクションはParで始まるトレイトになっている。[2011-09-18]
Seq         順番に並んでいるコレクション。
IndexedSeq   WrappedArray
ArraySeq
配列 配列(Array)
String StringBuilder StringStringBuilder 文字列
Range     for式の「1 to 10」とか「0 until 10」とかでよく使うやつ。
Intで開始値・終了値(範囲)だけ保持する。
NumericRange     Rangeの汎用版。LongやBigInt・BigDecimal等で使う。
'A' to 'Z'」でNumericRange[Char]、
1L to 10」でNumericRange[Long]が作れる。[/2011-03-23]
Vector     Scala2.8で導入されたコレクション。
木構造(1ノードが32要素)で要素を保持する。[/2016-06-18]
LinearSeq List LinkedList
DoubleLinkedList
MutableList
List
LinkedList
リスト
Stream     無限に続く値群を意味するコレクション。
Queue Queue
SynchronizedQueue
PriorityQueue
SynchronizedPriorityQueue
Queue キュー
Stack Stack
SynchronizedStack
ArrayStack
Stack スタック
Buffer   ArrayBuffer   配列に変換しやすいBuffer。要素の追加が出来る。
  ListBuffer   Listに変換しやすいBuffer
  SynchronizedBuffer    
Map       Map キーを元に値を取得するコレクション。
  HashMap HashMap HashMap  
ListMap ListMap    
  LinkedHashMap LinkedHashMap  
  WeakHashMap WeakHashMap 弱参照ハッシュマップ。
  OpenHashMap    
  MultiMap    
  ConcurrentMap    
  SynchronizedMap    
SortedMap TreeMap   SortedMap・TreeMap  
    TrieMap 2.10   [2013-06-08]
Set       Set 値が存在しているかどうかを保持するコレクション(集合)。
  HashSet HashSet HashSet  
BitSet BitSet BitSet  
ListSet      
  LinkedHashSet    
SortedSet TreeSet   SortedSet・TreeSet  

コレクションの生成

コレクションのインスタンスを生成するには、コレクションクラスのコンパニオンオブジェクト(のapply()メソッド)を使用する。

val l = List("a", "b", "c")
val m = Map("a" -> 123, "b" -> 456, "c" -> 789)
val s = Set("a", "b", "c")

可変コレクションを使うにはクラスをインポートする必要がある。
不変クラスと可変クラスで名前がかぶるクラス(トレイト・オブジェクト)もあるので、別名を付けると良い。

import scala.collection.mutable.{ ListBuffer, Map=>MMap, Set=>MSet }
val l = ListBuffer("a", "b", "c")
val m = MMap("a" -> 123, "b" -> 456, "c" -> 789)
val s = MSet("a", "b", "c")

空(要素数が0)のコレクションは、コンパニオンオブジェクト(のapplyメソッド)の引数を0個にする他に、
コンパニオンオブジェクトのemptyメソッドでも取得できる。[2011-02-17]

  val list = List[Int]()
  val list = List.empty[Int]
  val list:List[Int] = List()
  val list:List[Int] = List.empty
×val list = List(1,2,3).empty

Seqの場合、同じ値で初期化するfillや値を範囲(開始値・終了値)で指定するrange等、他にも初期化メソッドがある。[2011-02-17]

Seqの初期化メソッド


MapやSetの不変オブジェクトの場合、初期化時点で要素数が分かる(後から変わることが無い)為、要素数に応じて効率の良いクラスが使用される。
例えばScala2.8のMapの場合、以下のようになっている。

要素数 実際の具象クラス
1 scala.collection.immutable.Map$Map1
2 scala.collection.immutable.Map$Map2
3 scala.collection.immutable.Map$Map3
4 scala.collection.immutable.Map$Map4
5 scala.collection.immutable.HashMap$HashTrieMap

要素数1〜4のMapでは、getメソッドの実体はif文の羅列でキーを判定している。
これは、要素数が少ないなら、下手に内部構造(配列とかリストとか)を持って検索するより高速だからだろう。
(参考→Javaの場合、要素数が少ないならMap#containsKey()よりList#contains()の方が速い

しかも、Map1でキーを追加するとMap2が返るし、Map2からキーを削除すればMap1が返るようにちゃんと連動している。


Scala目次へ戻る / 技術メモへ戻る
メールの送信先:ひしだま