1

我对 Scala 很陌生！但是，我想使用以下针对欧拉问题 4 的工作解决方案，只是par为了看看我是否可以做到：

import scala.math

object Problem4 {
    def isPalindrome(x: Int): Boolean = {
        val string = x.toString
        string.reverseIterator.sameElements(string.iterator)
    }

    def getPairs(minimum: Int, maximum: Int) = {
        for (i <- minimum to maximum view;
             j <- minimum to maximum view)
             yield (i, j)
    }

    def getAnswer(numberOfDigits: Int): Int = {
        val maximum = math.pow(10, numberOfDigits).toInt
        val minimum = math.pow(10, numberOfDigits - 1).toInt
        val products = for {
                           pair <- getPairs(minimum, maximum)
                           product = pair match { case (i, j) => i * j } 
                           if isPalindrome(product)
                       } yield product
        products.par.max
    }

    def main(args: Array[String]) {
        val answer = getAnswer(4)
        println("Problem 4 answer: %s".format(answer))
    }
} // object Problem4

Project Euler 4要求输入 3 位数字，我注意到在我的 PC 上找到 4 位数字的答案需要 63 秒，并且在我的双核系统上只使用一个处理器。尽管这适用par于for表达式的末尾。

我如何并行化这个使用par？理想情况下，我想找到 4 位数字的答案需要 30-40 秒。谢谢！

编辑：我很确定getPairs返回一个View：

    scala>     def getPairs(minimum: Int, maximum: Int) = {
         |         for (i <- minimum to maximum view;
         |              j <- minimum to maximum view)
         |              yield (i, j)
         |     }
    getPairs: (minimum: Int, maximum: Int)scala.collection.SeqView[(Int, Int),Seq[_]]

此外，添加par到getPairs调用会返回一个警告，仍然只使用我的一个处理器，并导致java.lang.OutOfMemoryError: Java heap space异常：

[info] Loading project definition from M:\programming\testdriveneuler\src\problem4\project
[info] Set current project to euler (in build file:/M:/programming/testdriveneuler/src/problem4/)
[info] Compiling 1 Scala source to M:\programming\testdriveneuler\src\problem4\target\scala-2.9.2\classes...
[warn] M:\programming\testdriveneuler\src\problem4\src\main\scala\Problem4.scala:39: `withFilter' method does not yet exist on scala.collection.parallel.ParSeq[((Int, Int), Int)], using `filter' method instead
[warn]                            pair <- getPairs(minimum, maximum).par
[warn]                                 ^
[warn] one warning found

编辑：我对计算 2 个 4 位数字乘积的欧拉问题 4 的答案非常感兴趣。供参考，答案是99000099。

4

3 回答 3

3

如此复杂。它可以用2个功能来完成

def isPalindrome(x: Int) = x.toString sameElements x.toString.reverse

def products(min: Int, max: Int) = for { 
  x <- min to max par; 
  y <- min to max par; 
  if isPalindrome(x * y) 
} yield (x, y, x * y)

scala> products(100, 999).maxBy(_._3)
res0: (Int, Int, Int) = (913,993,906609)

更新

(min to max).viewReturns SeqView，它表示集合的惰性版本。(min to max).view.par返回ParSeq，并行收集。换句话说，调用par惰性序列将强制它进行评估。因此，在这种情况下，您应该在惰性和并行性之间进行选择。很难说当您从SeqViewto移动时执行了哪些转换，ParSeq但这种不必要的复杂性正在导致OutOfMemoryError。

更新2

是的，for它只是集合上高阶操作的语法糖。循环的脱糖版本for将类似于：

(min to max par) flatMap { x =>
  (min to max par)
    .filter(y => isPalindrome(x * y))
    .map(y => x * y)
}
于 2012-05-10T14:17:12.313 回答
1

在调用 getPairs 时添加 .par；

pair <- getPairs(min, max).par

我怀疑（但不能在我的手机上确定）getPairs 方法没有返回视图；因此您的 for 循环执行您的计算。

验证这一点的一种简单方法是省略最后一行（即 products.par.max - for 循环的评估）并查看您的程序是否仍在执行计算。

于 2012-05-10T13:57:55.193 回答
1

你可以像这样并行化它：

  def isPalindrome (n: Int) = n.toString == n.toString.reverse
  val R = 100 until 1000
  val xs = for (i <- R; j <- R) yield i * j
  val pals = xs.par filter isPalindrome
  println (pals max)

（省略.par非并行的）。但是我发现我的双核机器上的并行版本慢了 3-4 倍。有时并行化的开销是不值得的。

编辑：对于咯咯笑，这是一个使用 Akka 的版本（基于Pi 计算教程）。它的性能比使用 4e6 的答案（在我的机器8.0s vs 9.1s上）中使用并行集合稍快，尽管如果您删除.par第二个生成器上的解决方案，该解决方案的性能几乎相同。

import akka.actor._
import akka.routing.RoundRobinRouter

sealed trait Euler4Message
case object Calculate extends Euler4Message
case class Work(range1: Seq[Int], range2: Seq[Int]) extends Euler4Message
case class Result(value: Int) extends Euler4Message
case class FinalResult(value: Int, duration: Long)

class Worker extends Actor {

  def calculate(r1: Seq[Int], r2: Seq[Int]): Int = {
    def isPalindrome(x: Int) = {
      val s = x.toString
      s.reverseIterator.sameElements(s.iterator)
    }
    val pals = for (i <- r1; j <- r2; if isPalindrome(i * j)) yield i * j
    pals.max
  } 

  def receive = { case Work(r1, r2) => sender ! Result(calculate(r1, r2)) }   
}

class Master(nrOfDigits: Int, nrOfWorkers: Int, chunkSize: Int) extends Actor {

  var nrOfResults: Int = 0
  var maxResult = 0
  var sentAll = false
  var nrMessages = 0

  val start: Long = System.currentTimeMillis
  val min = math.pow(10, nrOfDigits - 1).toInt
  val max = math.pow(10, nrOfDigits).toInt 
  val range = min until max
  val workerRouter = 
    context.actorOf(Props[Worker].withRouter(RoundRobinRouter(nrOfWorkers)))

  def receive = {
    case Calculate =>
      for (i <- range.grouped(chunkSize)) { 
        // grouped produces an Iterator, so is 'lazy'
        workerRouter ! Work(i, range)
        nrMessages += 1
      }
      sentAll = true

    case Result(value) =>
      if (value > maxResult) maxResult = value
      nrOfResults += 1
      if (sentAll && nrOfResults == nrMessages) {
         println("Result = "+ maxResult 
                +"\nTime in ms: "+ (System.currentTimeMillis - start))
         context.system.shutdown()
      }
  }
}

object Euler4 extends App {
  val master =  ActorSystem().actorOf(Props(new Master(4, 4, 50)))
  master ! Calculate
}

演员的好处是您可以使用命令式代码并且仍然获得并行性。因此，将上面 worker actor 中的方法换成calculate下面的方法，整个事情大约在1.0 秒内完成（提高了 8 倍）。

我发现它在更大的块大小（尝试 1000）时工作得最快，并确保您的工作人员至少与处理器一样多。

  def calculate(r1: Seq[Int], r2: Seq[Int]): Int = {
    def isPalindrome(x: Int) = {
      val s = x.toString
      s.reverseIterator.sameElements(s.iterator)
    }
    var max = 0
    // count down so that we don't have to check if palindrome so often
    var i = r1.last
    while (i >= r1.head) {
      // for some reason counting down here increases the run-time :/
      var j = r2.head
      while (j <= r2.last) {
        val r = i * j
        if (r > max && isPalindrome(r)) max = r
        j += 1
      }
      i -= 1
    }
    max
  }
于 2012-05-10T14:31:05.163 回答