S-JIS[2011-03-20/2011-04-02] 変更履歴

Scala List

ScalaのListはJavaのListとはかなり異なる。
JavaではListは代表的なコレクションのひとつだが、ScalaではSeqが代表であり、ListはSeqの一種。

概要

ScalaのListはJavaのListとは異なり、単方向（片方向）のリスト（かなり原始的でその分シンプルなリスト）である。
継承関係は、Seq←LinearSeq←List。

JavaのListはインターフェースであり、具象クラスでよく使われるのはArrayListやLinkedList。
JavaのListでデータを追加するメソッドはadd()であり、データはリストの末尾に追加される。
ArrayListは内部で配列を使ってデータを保持しており、配列サイズを超えるデータが追加される場合には拡張される。
LinkedListは双方向リストであり、末尾データへの“ポインター（参照）”を保持しているので、末尾へ簡単にアクセスできる。

ScalaのList（不変List）の構造は単純なリスト（単方向リスト）であり、データと“次のデータへのポインター”しか保持していない。
“次のデータへのポインター”しか保持していないので、末尾データへアクセスするにはリスト内の全データを辿る必要があり、効率が悪い。
逆に先頭データへはすぐアクセスできるので、データを追加する場合はリストの先頭へ追加するのが効率が良い。
（データ数を取得するにも全データを辿る必要がある。JavaのArrayListやLinkedListはデータ数を別途保持している）

また、再帰呼び出しと非常に相性が良い。
（色々なコレクションに対して再帰呼び出しを行うと、たいていListが一番速い）

Listのクラス

List関連のクラス。

インスタンス生成

Listのインスタンスを作る（初期化する）方法。

Listのメソッド

List関連のメソッド。
（→Seq・Iterable・Traversableのメソッド）

head・tailの実装

Listは先頭要素と次のデータ（残りのList）を保持しているので、それを取り出す操作（head・tail）はすごく速い。

sealed abstract class List[+A] extends LinearSeq[A] 〜 {
  def isEmpty: Boolean
  def head: A
  def tail: List[A]
〜
}

final case class ::[B](private var hd: B, private[scala] var tl: List[B]) extends List[B] {
  override def head : B = hd
  override def tail : List[B] = tl
  override def isEmpty: Boolean = false
〜
}

したがって、関数型プログラミングの例でよく出てくる再帰関数にhead・tailを使用するのは、Listではとても相性が良い。

@scala.annotation.tailrec
def sum(s: Int, list: List[Int]): Int = {
  if (list.isEmpty) {
    s
  } else {
    sum(s + list.head, list.tail)
  }
}

→他のSeq具象クラスのhead・tailの実行時間
→sumの例

追加順

Listはデータを先頭に追加するのが速いが、来た順にデータを追加していくと、出来たListは逆順になってしまう。そこでreverseを使えば来た順になる。

var list = List.empty[Int]
for(i <- 1 to N){ list = i :: list }
list.reverse

あるいは、ListBufferやMutableListで末尾に追加していってtoListでListを取得することも出来る。[/2011-03-21]

val buffer = scala.collection.mutable.ListBuffer[Int]()
for(i <- 1 to N){ buffer += i }
buffer.toList

val mlist = new scala.collection.mutable.MutableList[Int]
for(i <- 1 to N){ mlist += i }
mlist.toList

どうやら、来た順に並べたいならListBufferを使う方が多少効率が良いようだ。
逆順（あるいは順序にこだわらない）でいいならListの先頭に追加していく方が速い。

ListBufferは先頭に追加するのも末尾に追加するのも同じ速度（速度の違いは誤差の範囲）。