スカラ：使用してマージソート先物タイミングアウト

Question

次のシーケンシャルマージソート非常に迅速に結果を返します： -

def mergeSort(xs: List[Int]): List[Int] = { 
    def merge(xs: List[Int], ys: List[Int]): List[Int] = (xs, ys) match { 
     case (Nil, _) => ys 
     case (_, Nil) => xs 
     case (x :: xs1, y :: ys1) => if (x <= y) x :: merge(xs1, ys) else y :: merge(xs, ys1) 
    } 
    val mid = xs.length/2 
    if (mid <= 0) xs 
    else { 
     val (xs1, ys1) = xs.splitAt(mid) 



     merge(mergeSort(xs1), mergeSort(ys1)) 
    } 
    } 

    val newList = (1 to 10000).toList.reverse 

    mergeSort(newList) 

しかし、私は先物を使用して、それを並列化しようとすると、それがタイムアウト： -

def mergeSort(xs: List[Int]): List[Int] = { 
    def merge(xs: List[Int], ys: List[Int]): List[Int] = (xs, ys) match { 
     case (Nil, _) => ys 
     case (_, Nil) => xs 
     case (x :: xs1, y :: ys1) => if (x <= y) x :: merge(xs1, ys) else y :: merge(xs, ys1) 
    } 
    val mid = xs.length/2 
    if (mid <= 0) xs 
    else { 
     val (xs1, ys1) = xs.splitAt(mid) 
     val sortedList1 = Future{mergeSort(xs1)} 
     val sortedList2 = Future{mergeSort(ys1)} 

     merge(Await.result(sortedList1,5 seconds), Await.result(sortedList2,5 seconds)) 
    } 
    } 

    val newList = (1 to 10000).toList.reverse 

    mergeSort(newList) 

タイムアウト例外が発生します。これはおそらく、このコードがlog2 10000スレッドを生成し、実行コンテキストのスレッドプールに多数のスレッドが含まれないため、多くの遅延が追加されるためです。

1.）どのようにしてマージソートの固有の並列性を利用し、このコードを並列化できますか？

2.）Futuresはどのようなユースケースが有用か、避けなければならないのはいつですか？

編集1：私は今のところ得ているのフィードバックをもとにリファクタリングコード： - 通常

def mergeSort(xs: List[Int]): Future[List[Int]] = { 

    @tailrec 
    def merge(xs: List[Int], ys: List[Int], acc: List[Int]): List[Int] = (xs, ys) match { 
     case (Nil, _) => acc.reverse ::: ys 
     case (_, Nil) => acc.reverse ::: xs 
     case (x :: xs1, y :: ys1) => if (x <= y) merge(xs1, ys, x :: acc) else merge(xs, ys1, y :: acc) 
    } 

    val mid = xs.length/2 
    if (mid <= 0) Future { 
     xs 
    } 
    else { 
     val (xs1, ys1) = xs.splitAt(mid) 
     val sortedList1 = mergeSort(xs1) 
     val sortedList2 = mergeSort(ys1) 
     for (s1 <- sortedList1; s2 <- sortedList2) yield merge(s1, s2, List()) 
    } 
    } 

Answer 1

先物を使用して、あなたは、a）はできるだけ待つ先物内で動作することを好むはずですb）使用している実行コンテキストに注意を払う。 A）の例として

は、ここにあなたがこれを変更することができます方法は次のとおりです。

def mergeSort(xs: List[Int]): Future[List[Int]] = { 
    def merge(xs: List[Int], ys: List[Int]): List[Int] = (xs, ys) match { 
    case (Nil, _) => ys 
    case (_, Nil) => xs 
    case (x :: xs1, y :: ys1) => if (x <= y) x :: merge(xs1, ys) else y :: merge(xs, ys1) 
    } 
    val mid = xs.length/2 
    if (mid <= 0) Future(xs) 
    else { 
    val (xs1, ys1) = xs.splitAt(mid) 
    val sortedList1 = mergeSort(xs1) 
    val sortedList2 = mergeSort(ys1) 
    for (s1 <- sortedList1; s2 <- sortedList2) yield merge(s1, s2) 
    } 
} 
val newList = (1 to 10000).toList.reverse 

Await.result(mergeSort(newList), 5 seconds) 

しかしオーバーヘッドのトンがまだここにあります。通常、オーバーヘッドが支配的になるのを避けるために、かなり大きなサイズの作業を並列化するだけです。この場合、再帰がある一定のサイズよりも小さいリストに達すると、シングルスレッドバージョンに戻ってしまうことになります。