2

quicksortF()私は、Scala の Future を使用してパーティションの再帰的な並べ替えを同時に実行できるようにするクイックソート (メソッド) を作成しました。また、通常のクイックソート (メソッドquicksort()) も実装しました。残念ながら、並べ替えるリストが約 1000 要素 (900 が機能する) を超えると、Future バージョンはデッドロック (永久にブロックされるようです) に終わります。ソースを以下に示します。

私は俳優と先物に比較的慣れていません。ここで何がうまくいかないのですか？

ありがとう！

import util.Random
import actors.Futures._

/**
 * Quicksort with and without using the Future pattern.
 * @author Markus Gumbel
 */
object FutureQuickSortProblem {

  def main(args: Array[String]) {
    val n = 1000 // works for n = 900 but not for 1000 anymore.

    // Create a random list of size n:
    val list = (1 to n).map(c => Random.nextInt(n * 10)).toList
    println(list)
    // Sort it with regular quicksort:
    val sortedList = quicksort(list)
    println(sortedList)
    // ... and with quicksort using Future (which hangs):
    val sortedListF = quicksortF(list)
    println(sortedListF)
  }

  // This one works.
  def quicksort(list: List[Int]): List[Int] = {
    if (list.length <= 1) list
    else {
      val pivot = list.head
      val leftList = list.filter(_ < pivot)
      val middleList = list.filter(pivot == _)
      val rightList = list.filter(_ > pivot)

      val sortedLeftList = quicksort(leftList)
      val sortedRightList = quicksort(rightList)
      sortedLeftList ::: middleList ::: sortedRightList
    }
  }

  // Almost the same as quicksort() except that Future is used.
  // However, this one hangs.
  def quicksortF(list: List[Int]): List[Int] = {

    if (list.length <= 1) list
    else {
      val pivot = list.head
      val leftList = list.filter(_ < pivot)
      val middleList = list.filter(pivot == _)
      val rightList = list.filter(_ > pivot)

      // Same as quicksort() but here we are using a Future
      // to sort the left and right partitions independently:
      val sortedLeftListFuture = future {
        quicksortF(leftList)
      }
      val sortedRightListFuture = future {
        quicksortF(rightList)
      }
      sortedLeftListFuture() ::: middleList ::: sortedRightListFuture()
    }
  }
}

class FutureQuickSortProblem // If not defined, Intellij won't find the main method.?!
4

2 に答える 2

3

免責事項: (2.10 より前の) 標準ライブラリのアクターやフューチャーを個人的に真剣に使用したことはありません。また、API について気に入らない (または少なくとも理解できない) 点がいくつかあります。たとえば、Scalaz、Akka、または Play 2.0 の実装と比較してください。

しかし、このような場合の通常のアプローチは、先物をすぐに要求して結果を結合するのではなく、モナド的に結合することです。たとえば、次のように記述できます (新しい戻り値の型に注意してください)。

import scala.actors.Futures._

def quicksortF(list: List[Int]): Responder[List[Int]] = {
  if (list.length <= 1) future(list)
  else {
    val pivot = list.head
    val leftList = list.filter(_ < pivot)
    val middleList = list.filter(pivot == _)
    val rightList = list.filter(_ > pivot)

    for {
      left <- quicksortF(leftList)
      right <- quicksortF(rightList)
    } yield left ::: middleList ::: right
  }
}

バニラの実装のように、これは必ずしも非常に効率的ではなく、スタックをかなり簡単に吹き飛ばしますが、スレッドが不足することはありません。

補足として、なぜaではなくflatMapa をFuture返すのですか? 私にはわかりませんし、他の人も知りません。このような理由から、非推奨になった 2.10 より前の標準ライブラリのアクターベースの同時実行処理を完全にスキップすることをお勧めします。ResponderFuture

于 2012-12-16T18:08:54.120 に答える
1

私が理解しているように、(再帰呼び出しの結果を連結するときのように) Future で apply を呼び出すと、結果が取得されるまでブロックされます。

于 2012-12-16T15:47:31.457 に答える