2

ですから、私が取り組んでいるグラフプロジェクトのためにScalaで並列コレクションを使用してきました。グラフクラスの基本を定義しました。現在scala.collection.mutable.HashMap、キーがどこにIntあり、値がListBuffer[Int]（隣接リスト）である場所を使用しています。 。（編集：これはその後に変更されましたArrayBuffer[Int]

私は数ヶ月前にC++で同様のことをしましたstd::vector<int, std::vector<int> >。

私が今やろうとしているのは、グラフ内の頂点のすべてのペア間でメトリックを実行することです。そのため、C++では次のようにしました。

// myVec = std::vector<int> of vertices
for (std::vector<int>::iterator iter = myVec.begin(); iter != myVec.end(); ++iter) {
    for (std::vector<int>::iterator iter2 = myVec.begin(); 
        iter2 != myVec.end(); ++iter2) {
        /* Run algorithm between *iter and *iter2 */
    }
}

私はこれを行うことで、Scalaで同じことを並列化しました（または試みました）。

// vertexList is a List[Int] (NOW CHANGED TO Array[Int] - see below)
vertexList.par.foreach(u =>
  vertexList.foreach(v =>
    /* Run algorithm between u and v */
  )
)

C ++バージョンは明らかにシングルスレッドですが、Scalaバージョンは.par並列コレクションを使用しており、8コア（同じマシン）でマルチスレッドになっています。ただし、C ++バージョンは約3日間で305,570ペアを処理しましたが、Scalaバージョンはこれまでのところ17時間で23,573ペアしか処理していません。

私が正しく計算したと仮定すると、シングルスレッドのC++バージョンはScalaバージョンよりも約3倍高速です。Scalaは本当にC++よりもはるかに遅いのでしょうか、それとも私はScalaを完全に誤用しているのでしょうか（私は最近始めたばかりです-私はScalaでプログラミングを始めたばかりです）。

ありがとう！-kstruct

編集whileループを使用するには、次のようなことをしますか。

// Where vertexList is an Array[Int]
vertexList.par.foreach(u =>
  while (i <- 0 until vertexList.length) {
    /* Run algorithm between u and vertexList(i) */
  }
}

全体にwhileループを使用するという意味の場合、whileに相当するものはあり.par.foreachますか？

EDIT2ちょっと待ってください、そのコードは正しくありません-私の悪いです。whileループを使用してこれを並列化するにはどうすればよいですか？var i反復を追跡するものがある場合、すべてのスレッドがそれを共有しているのではないでしょiうか？

4

3 に答える 3

4

HashMapあなたのコメントから、各アルゴリズムの実行の最後に共有ミュータブルを更新していることがわかります。また、散歩をランダム化する場合、共有Randomは論点でもあります。

2つの変更をお勧めします。

  1. 共有コレクションを変更する代わりに、.mapとを使用して不変のコレクションを返します。.flatMap
  2. ThreadLocalRandom（AkkaまたはJava 7のいずれかから）を使用して、乱数ジェネレーターでの競合を減らします
  3. さらに考えられる競合ポイントについては、アルゴリズムの残りの部分を確認してください。
  4. 内側のループを並列に実行してみることもできます。しかし、あなたのアルゴリズムを知らなければ、それが助けになるのか、それとも傷つくのかを知るのは難しいです。幸い、並列コレクションと順次コレクションのすべての組み合わせを実行するのは非常に簡単です。以下のコードでpVertexList切り替えてください。vertexList

このようなもの：

val pVertexList = vertexList.par
val allResult = for {
  u <- pVertexList
  v <- pVertexList
} yield {
  /* Run algorithm between u and v */
  ((u -> v) -> result)
}

値allResultはになりますParVector[((Int, Int), Int)]。あなたは.toMapそれをに変換するためにそれを要求するかもしれませんMap。

于 2012-03-16T22:06:27.227 に答える
2

なぜ可変なのですか？Scala 2.9.xには、優れた並列可変マップはないと思います。特に、このようなデータ構造が次のScala2.10に追加されたためです。

一方、...あなたはList[Int]？それを使用しないでください、を使用してくださいVector[Int]。また、可変マップとバッファーから不変リストへの変換を行って、他の場所で時間を無駄にしていないことを確認しますか？Scalaのデータ構造はC++のものとは異なるため、コードの他の場所で複雑さの問題が発生する可能性があります。

最後に、デイブが競合について尋ねるとき、何かに興味があるかもしれないと思います。競合がある場合は、並列処理によって処理が遅くなる可能性があります。並列化しない場合、実行速度はどれくらい速く/遅くなりますか？並列にしないと高速になる場合は、競合の問題が発生している可能性があります。

于 2012-03-17T02:18:38.210 に答える
0

完全にはわかりませんが、foreachループ内のforeachループは、多くのオブジェクトが作成されるため、かなり遅いと思います。参照：http ：//scala-programming-language.1934581.n4.nabble.com/for-loop-vs-while-loop-performance-td1935856.html

whileループを使用して書き直してみてください。

また、リストはヘッドアクセスに対してのみ効率的であり、配列はおそらくより高速です。

于 2012-03-16T19:22:45.770 に答える