17

同様の操作（つまり、多くのマップを1つのマップにマージします。この質問を参照）について、Scalaのimmutable.Mapとmutable.Mapのパフォーマンス特性を比較したいと思いました。可変マップと不変マップの両方で同様の実装のように見えるものがあります（以下を参照）。

テストとして、1,000,000個の単一アイテムのMap [Int、Int]を含むリストを生成し、このリストをテスト対象の関数に渡しました。十分なメモリがあれば、結果は驚くべきものではありませんでした。mutable.Mapの場合は約1200ミリ秒、immutable.Mapの場合は約1800ミリ秒、mutable.Mapを使用した命令型実装の場合は約750ミリ秒です。それについてもコメントしてください。

少し驚いたのは、おそらく私が少し太っていたためです。IntelliJ8.1のデフォルトの実行構成では、両方の可変実装がOutOfMemoryErrorにヒットしましたが、不変コレクションはヒットしませんでした。不変テストは最後まで実行されましたが、非常にゆっくりと実行されました。約28秒かかります。最大JVMメモリを増やしたところ（約200MB、しきい値がどこにあるかわからない）、上記の結果が得られました。

とにかく、これが私が本当に知りたいことです：

なぜ可変の実装はメモリを使い果たしますが、不変の実装はそうではありませんか？ 不変バージョンでは、可変実装が実行する前にガベージコレクターを実行してメモリを解放できると思いますが、これらのガベージコレクションはすべて、不変の低メモリ実行の遅さを説明していますが、より詳細な説明が必要ですそれより。

以下の実装。（注：これらが可能な限り最良の実装であるとは言いません。遠慮なく改善を提案してください。）

  def mergeMaps[A,B](func: (B,B) => B)(listOfMaps: List[Map[A,B]]): Map[A,B] =
    (Map[A,B]() /: (for (m <- listOfMaps; kv <-m) yield kv)) { (acc, kv) =>
      acc + (if (acc.contains(kv._1)) kv._1 -> func(acc(kv._1), kv._2) else kv)
    }

  def mergeMutableMaps[A,B](func: (B,B) => B)(listOfMaps: List[mutable.Map[A,B]]): mutable.Map[A,B] =
    (mutable.Map[A,B]() /: (for (m <- listOfMaps; kv <- m) yield kv)) { (acc, kv) =>
      acc + (if (acc.contains(kv._1)) kv._1 -> func(acc(kv._1), kv._2) else kv)
    }

  def mergeMutableImperative[A,B](func: (B,B) => B)(listOfMaps: List[mutable.Map[A,B]]): mutable.Map[A,B] = {
    val toReturn = mutable.Map[A,B]()
    for (m <- listOfMaps; kv <- m) {
      if (toReturn contains kv._1) {
        toReturn(kv._1) = func(toReturn(kv._1), kv._2)
      } else {
        toReturn(kv._1) = kv._2
      }
    }
    toReturn
  }
4

1 に答える 1

25

まあ、それは本当にあなたが使っている地図の実際のタイプに依存します。おそらくHashMap。現在、そのような可変構造は、使用する予定のメモリを事前に割り当てることでパフォーマンスを向上させます。あなたは100万のマップに参加しているので、最終的なマップはやや大きくなるはずです。これらのキー/値がどのように追加されるかを見てみましょう。

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

行のを参照して2 *くださいresize？ミュータブルHashMapはスペースが不足するたびに2倍になることで大きくなりますが、不変のキーはメモリ使用量がかなり控えめです（ただし、既存のキーは通常、更新時に2倍のスペースを占有します）。

ここで、他のパフォーマンスの問題については、最初の2つのバージョンでキーと値のリストを作成しています。つまり、マップを結合する前に、それぞれTuple2（キーと値のペア）がメモリに2回存在しているということです。さらに、のオーバーヘッドListは小さいですが、オーバーヘッドの100万倍以上の要素について話しています。

それを回避するプロジェクションを使用することをお勧めします。残念ながら、プロジェクションはに基づいてStreamいますが、Scala2.7.xでの目的にはあまり信頼できません。それでも、代わりにこれを試してください：

for (m <- listOfMaps.projection; kv <- m) yield kv

AStreamは、必要になるまで値を計算しません。Streamガベージコレクターは、アルゴリズムの場合のように、のヘッドへの参照を保持しない限り、未使用の要素も収集する必要があります。

編集

補完として、for / yieldの理解は、1つ以上のコレクションを取得し、新しいコレクションを返します。多くの場合、返されるコレクションは元のコレクションと同じタイプです。したがって、たとえば、次のコードでは、for-comprehensionが新しいリストを作成し、それが内に格納されl2ます。val l2 =新しいリストを作成するのはそれではなく、理解のためです。

val l = List(1,2,3)
val l2 = for (e <- l) yield e*2

mutable次に、最初の2つのアルゴリズム（キーワードを除く）で使用されているコードを見てみましょう。

(Map[A,B]() /: (for (m <- listOfMaps; kv <-m) yield kv))

ここfoldLeftでは同義語で書かれた演算子は/:、for-comprehensionによって返されたオブジェクトに対して呼び出されます。演算子の最後にあるa:は、オブジェクトとパラメーターの順序を逆にすることに注意してください。

foldLeftそれでは、これがどのオブジェクトであり、どのオブジェクトが呼び出されているかを考えてみましょう。この理解のための最初のジェネレータはですm <- listOfMaps。これlistOfMapsはタイプList[X]のコレクションであり、Xはここでは実際には関係ありません。の理解の結果Listは常に別のものListです。他のジェネレーターは関係ありません。

したがって、これを取得し、これのコンポーネントであるListそれぞれの内部のすべてのキー/値を取得し、それらすべてを使用して新しいものを作成します。それがあなたが持っているすべてのものを複製している理由です。MapListList

（実際、各ジェネレーターが新しいコレクションを作成するため、それよりもさらに悪いです。2番目のジェネレーターによって作成されたコレクションは、各要素のサイズでlistOfMapsあり、使用後すぐに破棄されます）

次の質問（実際には最初の質問ですが、答えを逆にする方が簡単でした）は、の使用がどのようにprojection役立つかです。

を呼び出すprojectionと、（Scala 2.7.xの）Listタイプの新しいオブジェクトが返されます。Stream最初は、これは事態を悪化させるだけだと思う​​かもしれません。これは、のコピーがList1つではなく、3つになるためです。ただし、aStreamは事前に計算されていません。それは怠惰に計算されます。

つまり、結果のオブジェクトであるStream、は、のコピーではListなく、必要に応じて計算するために使用できる関数Streamです。計算されると、結果は保持されるため、再度計算する必要はありません。

また、、mapおよびflatMapすべてfilterがStream新しいを返します。これは、それらを作成しStreamたものの単一のコピーをList作成せずに、それらをすべて一緒にチェーンできることを意味します。内包表記yieldはこれらの機能そのものを使用するため、Stream内部を使用することでデータの不要なコピーを防ぐことができます。

さて、あなたがこのようなものを書いたとしましょう：

val kvs = for (m <- listOfMaps.projection; kv <-m) yield kv
(Map[A,B]() /: kvs) { ... }

この場合、何も得られません。に割り当てた後Stream、kvsデータはまだコピーされていません。ただし、2行目が実行されると、kvsはその各要素を計算するため、データの完全なコピーを保持します。

ここで、元の形式について考えてみましょう。

(Map[A,B]() /: (for (m <- listOfMaps.projection; kv <-m) yield kv))

この場合、Streamは計算と同時に使用されます。foldLeftaのStream定義方法を簡単に見てみましょう。

override final def foldLeft[B](z: B)(f: (B, A) => B): B = { 
  if (isEmpty) z 
  else tail.foldLeft(f(z, head))(f) 
}

Streamが空の場合は、アキュムレータを返すだけです。それ以外の場合は、新しいアキュムレータ（f(z, head)）を計算し、それと関数をのに渡しtailますStream。

ただし、実行されるとf(z, head)、への参照は残りませんhead。または、言い換えると、プログラム内のどこもがを指していません。つまりhead、Streamガベージコレクターはそれを収集できるため、メモリが解放されます。

最終的な結果として、for-comprehensionによって生成された各要素は、アキュムレータの計算に使用している間、ほんの短時間だけ存在します。そして、これはあなたがあなたのデータ全体のコピーを保持することを節約する方法です。

最後に、なぜ3番目のアルゴリズムがその恩恵を受けないのかという問題があります。3番目のアルゴリズムはを使用しないためyield、データのコピーは作成されません。この場合、を使用projectionすると間接レイヤーのみが追加されます。

于 2009-08-20T21:31:12.167 に答える