Scala并行Mergesort - 内存不足 [英] Scala Parallel Mergesort - Out of Memory

问题描述

我试图用Scala Futures编写一个并行Mergesort。但是，当我运行我的算法在一个大小为10万的列表中的Eclipse的解释器，一切都变得非常迟钝，最终我得到一个错误信息告诉我我的内存不足。当我从命令行在解释器中运行它挂起已经在大小10 000的列表（但现在我没有得到错误消息）。

I've tried to write a parallel Mergesort using Scala Futures. However, when I run my algorithm on a list of size 100 000 inside Eclipse's interpreter everything gets very sluggish and eventually I get an error message telling me I'm out of memory. When I run it in the interpreter from the command line it hangs already at lists of size 10 000 (but now I get no error messages).

为什么会发生这种情况，是否有修复？

Why does this happen and is there a fix?

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)
    }
}

推荐答案

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

You should try using the Akka future and tweaking the ExecutionContext according to your needs:

• http://doc.akka.io/docs/akka/ 2.0.1 / scala / futures.html

• http://doc.akka.io/docs/akka/2.0.1/scala/futures.html

看起来std-lib没有给出良好的默认值对于这种情况。

It looks like the std-lib doesn't give you good defaults for use-case like that.

这篇关于Scala并行Mergesort - 内存不足的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！