List + .toVectorまたはVectorでのテール再帰？

Question

val dimensionality = 10 
    val zeros = DenseVector.zeros[Double](dimensionality) 

    @tailrec private def specials(list: List[DenseVector[Int]], i: Int): List[DenseVector[Int]] = { 
    if(i >= dimensionality) list 
    else { 
     val vec = zeros.copy 
     vec(i to i) := 1 
     specials(vec :: list, i + 1) 
    } 
    } 

    val specialList = specials(Nil, 0).toVector 
    specialList.map(...doing my thing...) 

は、私は上記のアキュムレータとしてリストを使用して、私の末尾再帰関数を記述し、その後

specials(Nil, 0).toVector 

書いたり、私が最初の場所でのベクトルと私のトレイル再帰を書くべきでしょうか？計算上より効率的なものは何ですか？

ところで：specialListは、1つのエントリを除いてすべてのエントリが0であるDenseVectorsを含むリストです。長いものと同じ数のDenseVectorsがあります。

Answer 1

私はあなたがここで何をしようとしてSURないよしかし、あなたがそうのようにコードを書き換えることができます：あなたが行列を扱っていると

type Mat = List[Vector[Int]] 

@tailrec 
private def specials(mat: Mat, i: Int): Mat = i match { 
    case `dimensionality` => mat 
    case _ => 
    val v = zeros.copy.updated(i,1) 
    specials(v :: mat, i + 1) 
} 

、ベクターは、おそらくより良い選択です。

Answer 2

はのは、両方のバリアントの性能特性を比較してみましょう：

• List：先頭追加は、一定の時間がかかり、Vectorへの変換は線形時間がかかります。
• Vector：prependingは "実質的に"一定時間（eC）を要し、その後の変換は必要ありません。

あなたはListとVectorの実装を比較する場合は、Listに先頭に追加するVectorに先頭に追加よりも簡単かつ安価操作であることがわかります。 Listによって行われているように、先頭に別の要素を追加するのではなく、Vectorは潜在的に内部的にすべてのブランチ/サブツリーを置き換える必要があります。平均しても、これは依然として一定時間内に起こります（サブツリーのサイズが異なるため「実質的に一定」）が、Listよりも高価です。プラス面では、toVectorへの呼び出しを避けることができます。

結局のところ、重要なポイントは、作成したいコレクションのサイズです（つまり、実行する再帰的な前置ステップの量）。明らかに勝者がなく、2つの変種のうちの1つが<= nステップの方が速いのに対して、> nステップの方が高速です。私の純粋なおもちゃのベンチマークでは、List/toVecorは、8k要素未満ではより速くと思われましたが、あなたのシナリオを適切に表す適切なベンチマークのセットを実行する必要があります。