5

私は、大きな構造を再帰しながら、「小さな」(短い文字列や単純なケース クラスなどの) オブジェクトを含むセットとマップを取得し、各ポイントで小さな (通常は 1、時には一握りの) オブジェクトを追加するコードを書いています。オブジェクトをセットまたはマップに追加します。可変セットとマップを使用すると、不変セットとマップを大幅に高速化できるように見えますが、その違いを定量的に評価するのに苦労しています。

不変データ構造を使用しているときに、Scala のガベージ コレクションが大幅な速度低下を引き起こすというのは理にかなっていますか? 可変データ構造を使用するとこれを修正できますか?

4

2 に答える 2

6

Scala の不変コレクションは驚くほど効率的です。ほとんどの場合、構造が変更されると、多くの構造が再利用されるためです。

ただし、多くの変更を行う場合は、可変構造の方が適している可能性があります。実際、これは Scala Collection API が内部の多くの場所で行っていることです: 可変データ構造を使用して新しいものを構築し、最後のステップとしてのみ、不変を作成してそれを返します。

于 2012-10-16T06:03:10.890 に答える
-1

Scala 可変データ構造は、メモリを事前に割り当てることにより、不変データ構造よりも効率的です。それらは多くの挿入に適しています (したがって、変更可能である理由)。Map が拡張する HashMap であるデフォルトの可変コレクションで += 関数の実装を見てみましょう。

https://github.com/scala/scala/blob/v2.9.2/src/library/scala/collection/mutable/HashMap.scala#L84

def += (kv: (A, B)): this.type = {
  val e = findEntry(kv._1)
  if (e == null) addEntry(new Entry(kv._1, kv._2))
  else e.value = kv._2
  this
}

HashMap は、addEntry を定義する HashTable を使用して変更可能な Map を実装します。

https://github.com/scala/scala/blob/v2.9.2/src/library/scala/collection/mutable/HashTable.scala#L117

protected def addEntry(e: Entry) {
  val h = index(elemHashCode(e.key))
  e.next = table(h).asInstanceOf[Entry]
  table(h) = e
  tableSize = tableSize + 1
  nnSizeMapAdd(h)
  if (tableSize > threshold)
    resize(2 * table.length)
}

コレクションのサイズは、しきい値に達するたびに 2 倍になります。したがって、一度に n 個のエントリを空の可変データ構造に繰り返し追加する場合、サイズを変更する必要があるのは log(n) 回だけです。不変データ構造の実装については詳しく見ていませんが、挿入のたびにサイズを変更する必要があると思います。したがって、パフォーマンスの格差。

于 2012-10-16T16:53:58.527 に答える