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 编程大约有 300 页）？

谢谢！-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循环，那么是否有相当于.par.foreachfor while的？

EDIT2等一下，那个代码甚至都不对——我的错。我将如何使用 while 循环并行化它？如果我有一些var i跟踪迭代，那么不是所有线程都在共享它i吗？

4

3 回答 3

4

从您的评论中，我看到您HashMap在每个算法运行结束时更新了一个共享的可变对象。如果你随机化你的步行，共享Random也是一个争论点。

我推荐两个改变：

  1. 使用.mapand.flatMap返回一个不可变的集合，而不是修改一个共享的集合。
  2. 使用 a 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将是 a ParVector[((Int, Int), Int)]。您可以调用.toMap它将其转换为Map.

于 2012-03-16T22:06:27.227 回答
2

为什么是可变的？我不认为 Scala 2.9.x 上有一个好的并行可变映射——特别是因为即将推出的 Scala 2.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 回答