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

Scala Seq

ScalaのSeqは、要素を並べて管理するコレクション。
JavaではList・Map・Setが代表的なコレクションだが、ScalaではSeq・Map・Set。

概要

Seqは、インスタンス（要素）を並べて管理するコレクション。
最初の要素、次の要素…という様に順番に処理していくのに向いている。

Seqは、さらにIndexedSeq・LinearSeq（およびBuffer）に分類される。
IndexedSeqは添字（インデックス）を使って、途中の要素を取り出しやすいSeq。Javaの配列やRandomAccess（ArrayList）に相当する。
LinearSeqは順番に処理する方を重視しているSeq。JavaのList（LinkedList）に相当する。
Bufferは可変のSeq（要素の追加がしやすい）。

インスタンス生成

Seqのコンパニオンオブジェクトには、以下のような初期化メソッドがある。
（例えばRangeの様に、必ずしも全てのメソッドが使える訳でもないが、大抵のオブジェクトで共通）

fill

同じ値で埋めたSeqを作る場合、どのクラスを使うのが一番速いのか試してみた。（WindowsXP＋Scala2.8.1＋JRE1.6.0_22）

// 要素数が10個
benchmark(10, 100*10000){ クラス.fill(10)('A') }

// 要素数が10万個
benchmark(10, 100){ クラス.fill(100000)('A') }

Streamの圧勝。Listは遅い。

Streamは（fillの場合は要素数と）要素の計算方法のみを保持するので、インスタンス生成は要素数に依存せず、速い。
Arrayは要素数が少ないとVectorより効率が良いが、要素数が多いとVectorの方が若干良いようだ。

ついでに、特定の文字で埋めた文字列（例えば999…999（ALL9）とか）を作るにはどれが速いのか試してみた。

// '9'がn個ならんだString
benchmark(10, 10*10000){ 計算式 }

汎用性のある方法（何の文字でもOK）では、小細工せずにStringのpadToメソッドを使うのが一番速かった＾＾；
インスタンス生成のみなら一番速かったStreamは、最下位。

ALL9の場合は「Longに変換してString化する」という方法も考えられるのでやってみた。（任意の文字（ALLスペースとか）への応用は効かないが）
ちなみにmath.pow()はDoubleで計算されるので、15桁まででないと正確に計算できない。
9桁までならLongでなくIntで計算できるが、Array.iterate.last方式がmath.pow()より速くなるかどうか、といった程度。

さらについでに、LongのALL9を作る速度も試してみた。
（Longで表せる範囲の10進数のALL9の最大は18桁）

自分でn乗を計算する関数を作ったのが一番最速だった(苦笑)

def f(n:Int, m:Long):Long = if (n == 0) m else f(n-1, m*10L)

ライブラリーを使った中ではmath.pow()を使う方法が最速だが、Array.iterate.lastも遜色ない。

range

順番に並んだ数値で初期化する。[2011-02-20]

scala> Range(0, 10)
res0: scala.collection.immutable.Range with Range.ByOne = Range(0, 1, 2, 3, 4, 5, 6, 7, 8, 9)

scala> Range(1, 10+1)
res1: scala.collection.immutable.Range with Range.ByOne = Range(1, 2, 3, 4, 5, 6, 7, 8, 9, 10)

scala> Range(10, 20+1, 2)
res2: scala.collection.immutable.Range = Range(10, 12, 14, 16, 18, 20)

scala> Array.range(1, 10+1)
res3: Array[Int] = Array(1, 2, 3, 4, 5, 6, 7, 8, 9, 10)

インスタンス生成だけならやはりStreamは速いが、さすがに専用クラスであるRangeはさらに速い。

Range以外の個別のクラスで範囲の数値が欲しい場合は、やはりrangeメソッドを使うのが一番高速。
次いで速いのは“Range.to他クラス”（Range.toVectorは無い）だが、Ａｒｒａｙに関しては++メソッドより逆に遅いのが不思議。

rangeで作ったインスタンスに対する演算の例として、sumメソッドを呼び出してみた。

演算のみだったらArrayやListがRangeよりも速い。（インスタンス生成と合わせるとRangeの方が速いが）

要素数が少ないと、Streamが意外と速い。Arrayと同じくらいだ。

VectorがStreamより遅いのも意外だったけど、VecotrはIndexedSeqだから、添字によって特定要素にアクセスするのは速くても、順次処理は遅くなるのか？

rangeで作ったインスタンスに対する演算の例として、mapメソッドを呼び出してみた。

Streamの速度が桁違い。ということは、計算式を保持した新しいStreamを作っているだけで、各要素への実際の演算（評価）は行っていないのだろう。

sumだと最下位だったVectorは、Listより速い。要素数が10万だと、Arrayよりも速くなっている。
mapの場合は新しいコレクションインスタンスを作る必要があるから、その分の影響が大きいのだろう。

rangeで作ったインスタンスに対する演算の例として、foreachメソッドを呼び出してみた。
（メソッドの外にある変数tへの加算）

ここでも、要素数が10万だとVectorはArrayよりも速い。
Streamは順当に(?)最下位。

しかしsumと同じ事をやってる割には、要素数が少ないときはsumの方が速く、要素数が多くなったらこちらの方が速いなぁ。

head・tail等

（rangeで作ったインスタンスに対して）headとかtailとかのよく使いそうなメソッドを試してみた。[2011-02-20]

benchmark(10, 回数){ r.head }.report

Range.lastが速いのにRange.headが遅いのは腑に落ちないけど。

再帰関数の例でよく見かけるhead・tailの組み合わせは、ListやStreamだと高速に出来るようになっているんだなぁ。 （→Listのhead・tailの実装）
逆に添字（インデックス）を指定した取得（apply）やlastは、見事にListとStreamが一番遅い。