S-JIS[2011-02-17/2011-03-20] 変更履歴
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の様に、必ずしも全てのメソッドが使える訳でもないが、大抵のオブジェクトで共通)
メソッド | 備考 | 例 | |
---|---|---|---|
コーディング | 結果 | ||
empty | 空のSeqを返す。 | List.empty[Int] |
List[Int]() |
apply | 初期値(要素)を指定する。 | List("A","B","C") |
List(A, B, C) |
concat | 他のコレクションからSeqを生成する。 | List.concat(Array("A","B"), Seq("C","D")) |
List(A, B, C, D) |
fill | 同じ値で埋める。 | List.fill(5)("A") |
List(A, A, A, A, A) |
tabulate | 添字から要素を計算する。 | List.tabulate(5)(i => i*i) |
List(0, 1, 4, 9, 16) |
iterate | 前の要素の値を元に要素を計算する。 初期値sに対し、s, f(s), f(f(s))…となる。 |
List.iterate(2, 8)(n => n*2) |
List(2, 4, 8, 16, 32, 64, 128, 256) |
range | 範囲(開始・終了)を指定する。 (Rangeにはrangeメソッドは無くて、 apply()メソッドを使用する) |
List.range(10, 15+1) |
List(10, 11, 12, 13, 14, 15) |
Range(10, 15+1) |
Range(10, 11, 12, 13, 14, 15) |
||
List.range(1, 10+1, 2) |
List(1, 3, 5, 7, 9) |
同じ値で埋めたSeqを作る場合、どのクラスを使うのが一番速いのか試してみた。(WindowsXP+Scala2.8.1+JRE1.6.0_22)
// 要素数が10個 benchmark(10, 100*10000){ クラス.fill(10)('A') }
// 要素数が10万個 benchmark(10, 100){ クラス.fill(100000)('A') }
クラス | 実行時間[ミリ秒] | |
---|---|---|
要素数10×100万回 | 要素数10万×100回 | |
Stream | 157, 157, 141, 109, 125, 125, 125, 125, 110, 109 |
0, 0, 0, 0, 0, 0, 0, 0, 0, 0 |
Array | 609, 578, 594, 593, 578, 578, 578, 593, 578, 578 |
532, 532, 531, 531, 531, 532, 531, 531, 532, 515 |
Vector | 985, 938, 953, 938, 937, 937, 937, 938, 938, 937 |
484, 485, 500, 500, 484, 485, 500, 469, 484, 485 |
List | 1234, 1204, 1219, 1188, 1188, 1188, 1203, 1203, 1203,
1203 |
1672, 1672, 1641, 1625, 1610, 1609, 1594, 1625, 1594,
1625 |
Streamの圧勝。Listは遅い。
Streamは(fillの場合は要素数と)要素の計算方法のみを保持するので、インスタンス生成は要素数に依存せず、速い。
Arrayは要素数が少ないとVectorより効率が良いが、要素数が多いとVectorの方が若干良いようだ。
ついでに、特定の文字で埋めた文字列(例えば999…999(ALL9)とか)を作るにはどれが速いのか試してみた。
// '9'がn個ならんだString benchmark(10, 10*10000){ 計算式 }
コード | 10万回の実行時間[ミリ秒] | ||
---|---|---|---|
9個 | 15個 | 32個 | |
(f(n, 1L) -1).toString |
47, 31, 31, 31, 31, 31, 47, 47, 47, 47 |
78, 78, 93, 78, 78, 79, 78, 63, 79, 78 |
|
{var m=1L; Range(0, 15).foreach(_
=> m*=10); m-1}.toString |
62, 62, 63, 62, 62, 63, 63, 46, 63, 63 |
109, 109, 109, 109, 125, 109, 94, 94, 93, 93 |
|
"".padTo(n, '9') |
110, 78, 94, 78, 78, 78, 78, 94, 78, 78 |
109, 109, 110, 110, 109, 94, 109, 109, 109, 109 |
188, 188, 188, 188, 188, 172, 172, 172, 171, 187 |
(scala.math.pow(10, n) -1).toLong.toString |
109, 94, 109, 109, 109, 109, 109, 110, 110, 109 |
141, 125, 140, 141, 141, 141, 140, 141, 141, 141 |
|
(Array. iterate(10, n)(_*10).last
-1).toString |
125, 109, 125, 109, 125, 109, 125, 109, 109, 125 |
||
(Array. iterate(10L, n)(_*10).last
-1).toString |
157, 141, 125, 141, 141, 141, 125, 141, 125, 141 |
219, 203, 204, 203, 218, 203, 203, 219, 219, 219 |
|
(Vector.iterate(10L, n)(_*10).last -1).toString |
250, 188, 187, 171, 187, 172, 188, 187, 204, 187 |
281, 266, 265, 266, 266, 265, 265, 266, 266, 250 |
|
Array. fill(n)('9').mkString("") |
296, 250, 250, 265, 250, 250, 266, 250, 266, 266 |
406, 391, 390, 375, 391, 391, 391, 391, 391, 390 |
844, 843, 812, 938, 859, 812, 812, 813, 797, 812 |
(List. iterate(10L, n)(_*10).last -1).toString |
281, 281, 281, 282, 281, 281, 265, 281, 282, 281 |
438, 437, 438, 438, 422, 438, 437, 437, 438, 438 |
|
Vector.fill(n)('9').mkString("") |
344, 313, 312, 313, 313, 328, 328, 328, 312, 313 |
500, 484, 484, 485, 469, 469, 484, 484, 469, 469 |
922, 890, 891, 891, 890, 890, 875, 891, 875, 875 |
List. fill(n)('9').mkString("") |
438, 422, 422, 421, 422, 422, 437, 422, 422, 422 |
656, 641, 625, 625, 625, 625, 625, 625, 625, 625 |
1281, 1234, 1234, 1234, 1235, 1250, 1234, 1234, 1218,
1250 |
Stream.fill(n)('9').mkString("") |
547, 531, 516, 515, 516, 516, 515, 516, 531, 532 |
781, 750, 766, 750, 750, 781, 750, 766, 750, 750 |
1563, 1515, 1531, 1516, 1516, 1531, 1532, 1516, 1546,
1516 |
(Stream.iterate(10L, n)(_*10).last -1).toString |
656, 516, 515, 515, 531, 516, 531, 531, 516, 531 |
906, 890, 891, 875, 922, 906, 891, 890, 890, 891 |
汎用性のある方法(何の文字でも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桁)
コード | 10万回の実行時間[ミリ秒] | |
---|---|---|
15桁 | 18桁 | |
f(n, 1L) -1 |
15, 16, 16, 15, 15, 15, 16, 16, 16, 15 |
32, 31, 16, 16, 16, 31, 16, 16, 16, 16 |
var m=1L; Range(0, n).foreach(_
=> m*=10); m-1 |
47, 47, 47, 47, 47, 47, 47, 47, 47, 47 |
62, 62, 47, 62, 47, 62, 62, 47, 47, 47 |
(scala.math.pow(10, n) -1).toLong |
141, 125, 141, 141, 140, 141, 140, 141, 141, 140 |
|
Array. iterate(10L, n)(_*10).last
-1 |
172, 156, 156, 157, 156, 140, 156, 141, 140, 156 |
218, 187, 172, 187, 172, 188, 203, 187, 172, 172 |
Vector.iterate(10L, n)(_*10).last -1 |
219, 219, 203, 219, 219, 219, 203, 219, 218, 219 |
250, 250, 265, 297, 235, 219, 250, 218, 234, 234 |
"".padTo(n, '9').toLong |
234, 219, 235, 218, 235, 235, 234, 219, 266, 266 |
281, 265, 250, 265, 266, 265, 266, 266, 266, 266 |
Array .fill(n)(10L).foldLeft(1L)(_
* _) -1 |
281, 281, 281, 266, 282, 281, 265, 265, 281, 281 |
344, 328, 328, 359, 359, 313, 328, 329, 328, 328 |
Array .fill(n)(10L).product
-1 |
328, 328, 313, 296, 297, 328, 297, 313, 297, 313 |
391, 375, 360, 344, 359, 360, 375, 375, 344, 344 |
Vector.fill(n)(10L).foldLeft(1L)(_ * _) -1 |
375, 360, 343, 360, 359, 344, 359, 360, 344, 359 |
422, 422, 391, 407, 391, 391, 390, 391, 391, 391 |
List. iterate(10L, n)(_*10).last -1 |
375, 375, 359, 375, 359, 375, 360, 375, 359, 375 |
328, 328, 329, 328, 328, 312, 328, 328, 328, 329 |
Vector.fill(n)(10L).product -1 |
390, 375, 360, 375, 375, 375, 375, 375, 375, 375 |
437, 422, 422, 421, 438, 438, 438, 453, 515, 437 |
List .fill(n)(10L).foldLeft(1L)(_ * _) -1 |
468, 438, 438, 437, 437, 454, 453, 454, 453, 438 |
563, 562, 547, 547, 562, 563, 547, 547, 547, 547 |
List .fill(n)(10L).product -1 |
484, 453, 469, 454, 469, 437, 469, 468, 453, 453 |
563, 532, 547, 547, 531, 547, 531, 547, 531, 532 |
Stream.fill(n)(10L).foldLeft(1L)(_ * _) -1 |
547, 531, 515, 516, 516, 500, 500, 500, 500, 500 |
625, 609, 609, 593, 609, 594, 594, 641, 609, 609 |
Stream.fill(n)(10L).product -1 |
531, 516, 515, 516, 516, 515, 516, 641, 516, 515 |
625, 594, 593, 609, 625, 625, 609, 609, 610, 610 |
Stream.iterate(10L, n)(_*10).last -1 |
860, 844, 828, 829, 828, 828, 828, 844, 844, 844 |
1031, 985, 1000, 984, 984, 984, 985, 984, 985, 985 |
自分でn乗を計算する関数を作ったのが一番最速だった(苦笑)
def f(n:Int, m:Long):Long = if (n == 0) m else f(n-1, m*10L)
ライブラリーを使った中ではmath.pow()を使う方法が最速だが、Array.iterate.lastも遜色ない。
順番に並んだ数値で初期化する。[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)
コード | 実行時間[ミリ秒] | |
---|---|---|
要素数10×100万回 | 要素数10万×100回 | |
Range(1,n+1) |
47, 47, 47, 46, 47, 47, 47, 47, 47, 47 |
0, 0, 0, 0, 0, 0, 0, 0, 0, 0 |
Stream.range(1,n+1) |
125, 125, 110, 110, 110, 109, 125, 125, 109, 109 |
0, 0, 0, 0, 0, 0, 0, 0, 0, 0 |
Range(1,n+1).toStream |
438, 406, 406, 422, 422, 422, 422, 422, 422, 422 |
0, 0, 0, 0, 0, 0, 0, 0, 0, 0 |
Stream.empty[Int]++Range(1,n+1) |
578, 531, 531, 516, 531, 531, 515, 532, 531, 531 |
0, 0, 0, 0, 0, 0, 0, 0, 0, 0 |
Array. range(1,n+1) |
703, 688, 657, 797, 672, 719, 672, 657, 672, 672 |
765, 781, 719, 719, 735, 688, 734, 734, 704, 719 |
Vector.range(1,n+1) |
1047, 984, 985, 968, 969, 984, 953, 969, 953, 968 |
781, 750, 734, 750, 734, 750, 734, 750, 750, 750 |
List. range(1,n+1) |
1438, 1312, 1329, 1328, 1312, 1297, 1313, 1313, 1328,
1313 |
1469, 1453, 1422, 1437, 1438, 1625, 1422, 1422, 1438,
1453 |
Array.empty[Int]++Range(1,n+1) |
1797, 1719, 1719, 1719, 1735, 1734, 1735, 1719, 1703,
1718 |
906, 922, 985, 859, 844, 844, 844, 844, 859, 843 |
Range(1,n+1).toList |
1969, 2078, 1875, 1812, 1828, 1844, 1860, 1813, 1813,
1813 |
1813, 1812, 1828, 1812, 1797, 1813, 1812, 1797, 1812,
1828 |
List.empty[Int]++Range(1,n+1) |
2125, 2078, 2078, 2281, 2078, 2094, 2094, 2094, 2078,
2093 |
1922, 1906, 1922, 1891, 1922, 1922, 1922, 1937, 1906,
1922 |
Vector.empty[Int]++Range(1,n+1) |
2359, 2297, 2296, 2297, 2297, 2281, 2281, 2281, 2282,
2281 |
953, 953, 953, 953, 968, 953, 953, 938, 938, 938 |
Range(1,n+1).toArray |
2469, 2438, 2422, 2469, 2469, 2469, 2453, 2469, 2469,
2453 |
1828, 1797, 1766, 1797, 1797, 1781, 1797, 1765, 1781,
1781 |
インスタンス生成だけならやはりStreamは速いが、さすがに専用クラスであるRangeはさらに速い。
Range以外の個別のクラスで範囲の数値が欲しい場合は、やはりrangeメソッドを使うのが一番高速。
次いで速いのは“Range.
to他クラス”(Range.toVectorは無い)だが、Arrayに関しては++メソッドより逆に遅いのが不思議。
rangeで作ったインスタンスに対する演算の例として、sumメソッドを呼び出してみた。
コード | 実行時間[ミリ秒] | ||
---|---|---|---|
要素数10×100万回 | 要素数10万×100回 | ||
val a = Array. range(1, n+1) |
a.sum |
94, 78, 78, 94, 93, 94, 94, 79, 94, 94 |
812, 766, 766, 750, 750, 781, 782, 750, 812, 813 |
val l = List. range(1, n+1) |
l.sum |
141, 109, 109, 110, 110, 110, 110, 94, 110, 110 |
907, 891, 906, 907, 906, 891, 922, 891, 906, 891 |
val r = Range(1, n+1) |
r.sum |
125, 109, 110, 109, 109, 109, 109, 109, 109, 110 |
1000, 984, 985, 984, 969, 985, 984, 1000, 1000, 922 |
val s = Stream.range(1, n+1) |
s.sum |
94, 94, 94, 94, 94, 94, 94, 94, 125, 94 |
1140, 1000, 1000, 1016, 1016, 1032, 1016, 1016, 1016,
1000 |
val v = Vector.range(1, n+1) |
v.sum |
157, 125, 125, 125, 125, 125, 125, 140, 125, 141 |
1172, 1172, 1172, 1172, 1172, 1172, 1172, 1172, 1156,
1187 |
演算のみだったらArrayやListがRangeよりも速い。(インスタンス生成と合わせるとRangeの方が速いが)
要素数が少ないと、Streamが意外と速い。Arrayと同じくらいだ。
VectorがStreamより遅いのも意外だったけど、VecotrはIndexedSeqだから、添字によって特定要素にアクセスするのは速くても、順次処理は遅くなるのか?
rangeで作ったインスタンスに対する演算の例として、mapメソッドを呼び出してみた。
コード | 実行時間[ミリ秒] | ||
---|---|---|---|
要素数10×100万回 | 要素数10万×100回 | ||
s.map(n => ('A'+n%26).toChar) |
47, 16, 32, 15, 31, 31, 16, 15, 31, 16 |
0, 0, 0, 0, 0, 0, 0, 0, 0, 0 |
|
r.map(n => ('A'+n%26).toChar) |
Vectorになる | 235, 203, 204, 203, 203, 219, 203, 203, 203, 204 |
1391, 1312, 1359, 1359, 1360, 1343, 1313, 1313, 1328,
1328 |
a.map(n => ('A'+n%26).toChar) |
219, 219, 219, 203, 219, 203, 203, 203, 219, 219 |
1891, 1844, 1859, 1875, 1859, 1860, 1859, 1891, 1844,
1875 |
|
v.map(n => ('A'+n%26).toChar) |
265, 265, 266, 250, 266, 250, 266, 250, 250, 250 |
1406, 1391, 1407, 1406, 1390, 1406, 1391, 1407, 1391,
1406 |
|
l.map(n => ('A'+n%26).toChar) |
359, 359, 344, 343, 344, 344, 359, 344, 328, 343 |
2609, 2719, 2578, 2593, 2579, 2578, 2797, 2578, 2594,
2610 |
Streamの速度が桁違い。ということは、計算式を保持した新しいStreamを作っているだけで、各要素への実際の演算(評価)は行っていないのだろう。
sumだと最下位だったVectorは、Listより速い。要素数が10万だと、Arrayよりも速くなっている。
mapの場合は新しいコレクションインスタンスを作る必要があるから、その分の影響が大きいのだろう。
rangeで作ったインスタンスに対する演算の例として、foreachメソッドを呼び出してみた。
(メソッドの外にある変数tへの加算)
コード | 実行時間[ミリ秒] | |
---|---|---|
要素数10×100万回 | 要素数10万×100回 | |
r.foreach{ t += _ } |
313, 328, 312, 328, 328, 328, 312, 328, 328, 328 |
172, 172, 188, 172, 171, 172, 172, 172, 172, 171 |
a.foreach{ t += _ } |
750, 734, 735, 719, 718, 734, 719, 719, 735, 735 |
610, 578, 609, 594, 594, 593, 594, 594, 609, 594 |
l.foreach{ t += _ } |
828, 829, 813, 828, 828, 828, 828, 828, 844, 828 |
625, 641, 640, 625, 625, 625, 641, 641, 641, 641 |
v.foreach{ t += _ } |
906, 907, 968, 953, 891, 890, 890, 891, 891, 891 |
531, 531, 531, 516, 547, 547, 579, 547, 531, 532 |
s.foreach{ t += _ } |
953, 938, 938, 969, 953, 938, 938, 937, 953, 938 |
734, 719, 719, 719, 703, 703, 718, 703, 719, 719 |
ここでも、要素数が10万だとVectorはArrayよりも速い。
Streamは順当に(?)最下位。
しかしsumと同じ事をやってる割には、要素数が少ないときはsumの方が速く、要素数が多くなったらこちらの方が速いなぁ。
(rangeで作ったインスタンスに対して)headとかtailとかのよく使いそうなメソッドを試してみた。[2011-02-20]
benchmark(10, 回数){ r.head }.report
実行時間[ミリ秒] | ||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|
上段:要素数10×100万回 下段:要素数10万×100回 |
||||||||||||
head | tail | last | size | apply(5) | apply(50000) | fill | range | foreach | map | sum | ||
Range | 377 0 |
297 0 |
43 0 |
123 0 |
112 0 |
0 |
47 0 |
324 172 |
205 1338 |
109 986 |
||
Array | 129 0 |
1039 965 |
160 0 |
70 0 |
25 0 |
0 |
584 531 |
682 729 |
729 598 |
213 1865 |
90 777 |
|
List | 51 0 |
31 0 |
553 383 |
473 379 |
453 0 |
209 |
1201 1625 |
1319 1442 |
828 635 |
348 2608 |
110 901 |
|
Vector | 438 0 |
1102 4 |
443 0 |
25 0 |
90 0 |
0 |
940 488 |
973 746 |
903 537 |
258 1401 |
129 1172 |
|
Stream | 57 0 |
36 0 |
635 510 |
537 467 |
493 0 |
227 |
127 0 |
115 0 |
944 715 |
24 0 |
94 1014 |
Range.lastが速いのにRange.headが遅いのは腑に落ちないけど。
再帰関数の例でよく見かけるhead・tailの組み合わせは、ListやStreamだと高速に出来るようになっているんだなぁ。
(→Listのhead・tailの実装)
逆に添字(インデックス)を指定した取得(apply)やlastは、見事にListとStreamが一番遅い。