0

ScalaFuturesを使用して並列マージソートを作成しようとしました。ただし、Eclipseのインタープリター内でサイズ100 000のリストでアルゴリズムを実行すると、すべてが非常に遅くなり、最終的にはメモリが不足していることを示すエラーメッセージが表示されます。コマンドラインからインタープリターで実行すると、サイズ10000のリストで既にハングしています（ただし、エラーメッセージは表示されません）。

なぜこれが発生し、修正がありますか？

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 future を使用して、必要に応じて 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 に答える