scala中的并行递归

Question

我想从25 lines Sudoku solver in Scala并行递数调用求解器的递归调用。我已经改变了他们的Fold为reduce

def reduce(f: (Int, Int) => Int, accu: Int, l: Int, u: Int): Int = { 
    accu + (l until u).toArray.reduce(f(accu, _) + f(accu, _)) 
} 

其中，如果连续运行工作正常，但是当我把它变成

accu + (l until u).toArray.par.reduce(f(accu, _) + f(accu, _)) 

递归更经常到达底部并产生错误的解决方案。我想，它会执行底层递归并且工作起来，但似乎没有这样做。
我也试过期货

def parForFut2(f: (Int, Int) => Int, accu: Int, l: Int, u: Int): Int = { 
    var sum: Int = accu 
    val vals = l until u 
    vals.foreach(t => scala.actors.Futures.future(sum + f(accu, t))) 
    sum 
} 

这似乎有同样的问题作为 par.reduce

。我将不胜感激任何评论。整个代码在这里：

object SudokuSolver extends App { 
// The board is represented by an array of string 
val source = scala.io.Source.fromFile("./puzzle") 
val lines = (source.getLines).toArray 
var m: Array[Array[Char]] = for (
    str <- lines; 
    line: Array[Char] = str.toArray 
) yield line 
source.close() 

// For printing m 
def print = { 
    Console.println(""); 
    refArrayOps(m) map (carr => Console.println(new String(carr))) 
} 

// The test for validity of n on position x,y 
def invalid(i: Int, x: Int, y: Int, n: Char): Boolean = 
    i < 9 && (m(y)(i) == n || m(i)(x) == n || 
    m(y/3 * 3 + i/3)(x/3 * 3 + i % 3) == n || invalid(i + 1, x, y, n)) 

// Looping over a half-closed range of consecutive Integers [l..u) 
// is factored out Into a higher-order function 
def parReduce(f: (Int, Int) => Int, accu: Int, l: Int, u: Int): Int = { 
    accu + (l until u).toArray.par.reduce(f(accu, _) + f(accu, _)) 
} 

// The search function examines each position on the board in turn, 
// trying the numbers 1..9 in each unfilled position 
// The function is itself a higher-order fold, accumulating the value 
// accu by applying the given function f to it whenever a solution m 
// is found 
def search(x: Int, y: Int, f: (Int) => Int, accu: Int): Int = Pair(x, y) match { 
    case Pair(9, y) => search(0, y + 1, f, accu) // next row 
    case Pair(0, 9) => f(accu) // found a solution - print it and continue 
    case Pair(x, y) => if (m(y)(x) != '0') search(x + 1, y, f, accu) else 
    parForFut1((accu: Int, n: Int) => 
     if (invalid(0, x, y, (n + 48).asInstanceOf[Char])) accu else { 
     m(y)(x) = (n + 48).asInstanceOf[Char]; 
     val newaccu = search(x + 1, y, f, accu); 
     m(y)(x) = '0'; 
     newaccu 
     }, accu, 1, 10) 
} 

// The main part of the program uses the search function to accumulate 
// the total number of solutions 
Console.println("\n" + search(0, 0, i => { print; i + 1 }, 0) + " solution(s)") 
} 

Answer 1

Andreas发表评论后，我将m: Array[Array[Char]]更改为m: List[List[Char]]，这可以防止对它进行任何不必要和不必要的更改。最终循环方法是

def reduc(f: (Int, Int) => Int, 
        accu: Int, l: Int, u: Int, m1: List[List[Char]]):Int = 
    accu + (l until u).toArray.par.reduce(f(accu, _) + f(accu, _)) 

，我不得不通过米作为一个参数到每个使用的功能，所以他们中的每一个有它自己的它的实例。整个代码：

object SudokuSolver extends App{ 
     // The board is represented by an Array of strings (Arrays of Chars), 
     val source = scala.io.Source.fromFile("./puzzle") 

     val lines = source.getLines.toList    
     val m: List[List[Char]] = for (
     str <- lines; 
     line: List[Char] = str.toList 
    ) yield line 
     source.close() 

     // For prInting m 
     def printSud(m: List[List[Char]]) = { 
     Console.println("") 
     m map (println) 
     }            

     Console.println("\nINPUT:")      
     printSud(m) 

     def invalid(i:Int, x:Int, y:Int, n:Char,m1: List[List[Char]]): Boolean = 
     i < 9 && (m1(y)(i) == n || m1(i)(x) == n || 
      m1(y/3 * 3 + i/3)(x/3 * 3 + i % 3) == n || 
      invalid(i + 1, x, y, n, m1)) 

     def reduc(f: (Int, Int) => Int, accu: Int, l: Int, u: Int, 
       m1: List[List[Char]]): Int = 
     accu + (l until u).toArray.par.reduce(f(accu, _) + f(accu, _)) 

     def search(x: Int, y: Int, accu: Int, m1: List[List[Char]]): Int = 
     Pair(x, y) match { 
      case Pair(9, y) => search(0, y + 1, accu, m1) // next row 
      case Pair(0, 9) => { printSud(m1); accu + 1 } // found a solution 
      case Pair(x, y) => 
      if (m1(y)(x) != '0') 
       search(x + 1, y, accu, m1) // place is filled, we skip it. 
      else // box is not filled, we try all n in {1,...,9} 
       reduc((accu: Int, n: Int) => { 
       if (invalid(0, x, y, (n + 48).asInstanceOf[Char], m1)) 
        accu 
       else { // n fits here 
        val line = List(m1(y).patch(x, Seq((n + 48).asInstanceOf[Char]), 1)) 
        val m2 = m1.patch(y, line, 1) 
        val newaccu = search(x + 1, y, accu, m2); 
        val m3 = m1.patch(y, m1(y).patch(x, Seq(0), 1), 1) 
        newaccu 
       } 
      }, accu, 1, 10, m1) 
     }            

     Console.println("\n" + search(0, 0, 0, m) + " solution(s)") 

    } 

Answer 2

据我所知，递归本质上是连续的（即不可并行化）。

我会这样推理：递归意味着（简单地说）'自称'。一个函数调用总是在一个线程中发生，并且恰好在一个线程中发生

如果你正在告诉函数调用它自己，那么你就停留在那个线程中 - 你并没有将工作分开（即使它平行）。

虽然递归和并行性相关，但不在函数调用级别。它们相关的意思是任务可以递归分解成更小的部分，可以并行执行。