あるタイプから別のタイプへのスカラコレクションの変換の複雑さは何ですか？

Question

私は、次のもののようなScalaのコレクションの変換動作の複雑さを知っていただきたいと思います：

List.fill(n)(1).toArray 
Array.fill(n)(1).toList 
ArrayBuffer(Array.fill(n)(1):_*) 

私はそれは残念ながら、O（n）のとなりますので、それらのexemplesのために、我々はすべての要素をループする必要があるとし私はこれらの変換の下でサブルーチンを知らないので、複雑さが最適化されるかもしれません。

他の種類のスカラ変換に複雑さを追加するのをためらってください。

Answer 1

私はソースコードを簡単に見て、あなたが思ったようにすべてO（n）であるように見えます。あなたが直線的にコレクションの上に単純に繰り返し処理を、それを見ることができるように

override /*TraversableLike*/ def copyToArray[B >: A](xs: Array[B], start: Int, len: Int) { 
    var i = start 
    val end = (start + len) min xs.length 
    val it = iterator 
    while (i < end && it.hasNext) { 
    xs(i) = it.next() 
    i += 1 
    } 
} 

source

：ここ

は、例えば（toArrayによって使用される）サブルーチンcopyToArrayです。