0

我尝试使用 Scala Futures 编写并行合并排序。但是，当我在 Eclipse 的解释器中对大小为 100 000 的列表运行我的算法时，一切都变得非常缓慢，最终我收到一条错误消息，告诉我内存不足。当我从命令行在解释器中运行它时，它已经挂在大小为 10 000 的列表中（但现在我没有收到错误消息）。

为什么会发生这种情况，有解决办法吗？

import scala.actors.Future
import scala.actors.Futures._

object MergeSort{
    def sort[T <% Ordered[T]](toBeSorted :List[T]) :List[T] = toBeSorted match{
      case Nil => Nil
      case List(x) => List(x)
      case someList =>
        val (left, right) = someList splitAt someList.length/2
        val sortedLeft = future { sort(left) }
        val sortedRight = sort(right)
        merge(sortedLeft(), sortedRight, Nil)
    }

    def merge[T <% Ordered[T]](a :List[T], b :List[T], Ack: List[T]) :List[T] = (a, b) match {
      case (Nil, ys) => Ack.reverse ++ ys
      case (xs, Nil) => Ack.reverse ++ xs
      case (x::xs, y::ys) if x < y => merge(xs, y::ys, x::Ack)
      case (x::xs, y::ys) => merge(x::xs, ys, y::Ack)
    }
}
4

2 回答 2

2

您应该尝试使用 Akka 未来并根据您的需要调整 ExecutionContext：

看起来 std-lib 没有为您提供像这样的用例的良好默认值。

于 2013-03-23T17:06:17.413 回答
0

正如 Rex 所指出的，（任何）Future API 的开销是相当大的，不应被忽略。

不要在上下文切换开销上浪费宝贵的 CPU 和内存。您应该将列表拆分成合理大小的块，并在同一个线程中执行排序。

例如，如果您的机器上有 4 个内核和 4GB 内存。您可以将其拆分为 500MB 的块并同时运行多达 4 个合并排序。这将使您的吞吐量和并行度最大化。

您可以使用 SIP-14 的 ExecutionContext 来限制使用的线程数。

private val GLOBAL_THREAD_LIMIT = Runtime.getRuntime.availableProcessors()
private lazy implicit val executionContext =
   ExecutionContext.fromExecutorService(
       Executors.newFixedThreadPool(GLOBAL_THREAD_LIMIT)
)

顺便说一句，我在 SIP-14 中实现了并行外部合并排序。我已经在我的博客上解释了实现细节：http: //blog.yunglinho.com/blog/2013/03/19/parallel-external-merge-sort/

于 2013-03-25T04:49:04.187 回答