我正在尝试从Scala 中的 25 行数独求解器并行化数独求解器的递归调用。我把他们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)")
}