ScalaでVectorを使用する利点

投稿日: 2022-10-19 2022-10-19
タグ: Scala Collections

1. 概要

この短いチュートリアルでは、Scalaの Vector データ構造について学び、ListやArrayなどの他の選択肢との違いを確認します。

プログラムに不変のシーケンスデータ構造を選択する必要がある場合は、インデックス付きシーケンスまたは線形シーケンスのいずれかを選択できます。ここでは、ほとんどのアルゴリズムで適切に機能する汎用コレクションを見つけようとしています。

2. Vector とは何ですか？

Vectorは、Scalaの不変のデータ構造です。これは、他の既存のデータ構造へのランダムアクセスの非効率性に対処するためにScalaバージョン2.8で導入されました。 VectorはAbstractSeqとIndexedSeqを拡張します。したがって、一定時間の要素アクセスと長さの計算をサポートします。 Vectorは現在、不変のIndexedSeqのデフォルトの実装です。

3. VectorScalaでの実装

Vectorは、base-32整数trieとして実装されます。ルートレベルには0から32（2 ^ 5）のノードがあり、ルートレベルの各ノードに接続する別の32ノードが存在する可能性があります。したがって、2番目のレベルは最大32 * 32（2 ^ 10）個の要素に対応できます。 3番目のレベルには、32 * 32 * 32（2 ^ 15）要素などが含まれます。

したがって、5レベルの Vector は、最大2^30個の要素を保持できます。したがって、このような大規模なサイズのコレクションから要素にアクセスするには、5レベルのノードをトラバースするだけで、「実質的に一定時間」（eC）の操作になります。

ベクトル要素は32のバッチとしてメモリ内に一緒に存在するため、非常に高い局所性を提供します。

4. 性能特性

線形シーケンスコレクションは、headアクセスおよび反復アルゴリズムのインデックス付きシーケンスよりもわずかに改善されます。他のすべての場合、特に膨大なコレクションでは、インデックス付きシーケンスのパフォーマンスがはるかに速くなります。コレクションの一般的な操作は、4つのカテゴリにグループ化できます。これらを見てみましょう。

4.1. プリペンドとアペンド

Vectorは、構造共有を使用した永続的なデータ構造です。この手法により、追加/追加操作は、可変データ構造とほぼ同じ速度になります。追加または追加して新しい要素を追加すると、構造共有を使用して構造が変更され、結果が新しいVectorとして返されます。

いくつかの実験を実行して、実際の時間差を見てみましょう。

def appendPrependSeq(seq:Seq[Int], f: (Seq[Int], Int) => Seq[Int], it:Int): (Seq[Int], Double) ={
  val begin = System.currentTimeMillis
  var modifiedSeq = seq
  for (j <- 0 until it) {
    modifiedSeq = f(modifiedSeq, j)
  }
  val elapsedTime = System.currentTimeMillis - begin
  return (modifiedSeq, elapsedTime)
}

val vec:Vector[Int] = Vector()
val lst:List[Int] = List()

val numElements = 10000
val appendTimeRatio = appendPrependSeq(lst, (a,b) => a:+b, numElements)._2/appendPrependSeq(vec, (a,b) => a:+b, numElements)._2
val prependTimeRatio = appendPrependSeq(vec, (a,b) => b+:a, numElements)._2/appendPrependSeq(lst, (a,b) => b+:a, numElements)._2

println("Append test with %s elements, Vector is ~ %s times faster than List".format(numElements, appendTimeRatio))
println("Prepend test with %s elements, List is ~ %s times faster than Vector".format(numElements, prependTimeRatio))

テスト結果は、追加操作が同等であることを明確に示していますが、追加は大幅に高速です- Vectorを使用：

Append test with 10000 elements, Vector is ~ 67.7 times faster than List
Prepend test with 10000 elements, List is ~ 3.0 times faster than Vector

4.2. ランダムアクセスとランダムアップデート

これは、Vectorが他の不変のコレクションと比較して非常に優れている点です。 trie データ構造を使用した実装のおかげで、任意の位置の要素にアクセスするには、ツリー内のいくつかのレベルとブランチをトラバースする必要があります。

いくつかの実験を実行して、実際のパフォーマンス上の利点を実際に確認してみましょう。

def randomAccessSeq(seq:Seq[Int], it:Int): (Double) ={
  val begin = System.currentTimeMillis
  for (j <- 0 until it) {
    val idx = Random.nextInt(it)
    val elem = seq(idx)
  }
  val elapsedTime = System.currentTimeMillis - begin
  return (elapsedTime)
}

val numElements = 10000
val vec:Vector[Int] = (1 to numElements).toVector
val lst:List[Int] = (1 to numElements).toList

val randomAccessTimeRatio = randomAccessSeq(lst, numElements)/randomAccessSeq(vec, numElements)
println("Random access test with %s elements, Vector is ~ %s times faster than List".format(numElements, randomAccessTimeRatio))

10,000個の要素だけでテストを実行すると、実行時間に大きな違いが見られます。

Random access test with 10000 elements, Vector is ~ 36.0 times faster than List

4.3. ヘッド/テールアクセス

もう1つの一般的な操作は、ヘッド/テール要素へのアクセスです。推測できるように、インデックス付きツリーデータ構造から最初と最後の要素にアクセスすることは、どちらも高速操作です。

このようなシナリオでVectorがどのように機能するかを確認するために、別の例を見てみましょう。

def headTailAccessSeq(seq:Seq[Int], f: (Seq[Int]) => Int): (Int, Double) ={
  val begin = System.currentTimeMillis
  val headOrTail = f(seq)
  val elapsedTime = System.currentTimeMillis - begin
  return (headOrTail, elapsedTime)
}

val numElements = 1000000
val vec:Vector[Int] = (1 to numElements).toVector
val lst:List[Int] = (1 to numElements).toList

println(" Vector of %s elements took %s for head access".format(numElements, headTailAccessSeq(vec, (seq) => seq.head)._2 ))
println(" List of %s elements took %s for head access".format(numElements, headTailAccessSeq(lst, (seq) => seq.head)._2 ))

println(" Vector of %s elements took %s for tail access".format(numElements, headTailAccessSeq(vec, (seq) => seq.last)._2 ))
println(" List of %s elements took %s for tail access".format(numElements, headTailAccessSeq(lst, (seq) => seq.last)._2 ))

得られた出力は、ヘッドアクセスのパフォーマンスが同等であり、テールアクセスの場合のパフォーマンスが優れていることを示しています。

Vector of 1000000 elements took 0.0 for head access
List of 1000000 elements took 0.0 for head access
Vector of 1000000 elements took 0.0 for tail access
List of 1000000 elements took 15.0 for tail access

4.4. 反復

一部のアルゴリズムでは、コレクション全体のすべての要素を反復処理する必要があります。 Vector 内のすべての要素をトラバースすることは、リンクリストよりも少し複雑ですが、パフォーマンスに大きな違いはありません。

もう一度、反復アルゴリズムでVectorとListのパフォーマンスを比較してみましょう。

def calculateSumSeq(seq:Seq[Int]): (Int, Double) ={
  val begin = System.currentTimeMillis
  var total = 0
  for (elem <- seq) {
    total = total + elem
  }
  val elapsedTime = System.currentTimeMillis - begin
  return (total, elapsedTime)
}

val numElements = 10000000
val vec:Vector[Int] = (1 to numElements).toVector
val lst:List[Int] = (1 to numElements).toList

println(" Vector iteration of %s elements took %s milliseconds".format(numElements, calculateSumSeq(vec)._2))
println(" List iteration of %s elements took %s milliseconds".format(numElements, calculateSumSeq(lst)._2))

ListとVectorの両方で同様の反復パフォーマンスを示す出力が得られます。

Vector iteration of 10000000 elements took 63.0 milliseconds
List iteration of 10000000 elements took 53.0 milliseconds

5. 結論

このチュートリアルでは、Scalaの Vector データ構造、その実装の詳細、およびさまざまな状況でのパフォーマンス特性について学習しました。 Vector は、ランダムアクセス、特に膨大なコレクションではるかに優れたパフォーマンスを発揮します。 Scalaの他の不変のコレクションと比較して、他のすべての一般的な操作に対して非常に優れたパフォーマンスを提供します。

いつものように、完全なソースコードはGitHubのにあります。

getdocs

13036