斯卡拉：合併排序利用期貨超時

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線程，這會增加很多延遲，因爲執行上下文Threadpool可能沒有那麼多線程。

1.）我如何利用合併排序中的固有並行性和並行化代碼？

2.）對於什麼用例是期貨有用，什麼時候應該避免？

編輯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）注意你正在使用的執行上下文。

作爲的一個例子），這裏是你如何可以改變這一點：

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) 

但是仍然有一噸的開銷在這裏。通常情況下，您只會並行處理大小相當的工作塊以避免被開銷佔據主導地位，在這種情況下，當遞歸達到低於某個常量大小的列表時，這可能意味着回退到單線程版本。