1

私はScalaが初めてです！ただし、オイラー問題 4parに対する次の実用的な解決策があります。使用できるかどうかを確認するためだけに使用したいと思います。

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 秒かかり、デュアルコア システムでは 1 つのプロセッサしか使用しないことに気付きました。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警告が返され、プロセッサの 1 つしか使用されず、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

編集: オイラー問題 4 の答えを 2 つの 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).viewコレクションSeqViewの遅延バージョンを表す return 。、並列コレクションを(min to max).view.par返します。ParSeqつまり、par遅延シーケンスを呼び出すと、強制的に評価されます。したがって、この場合、遅延と並列処理のどちらかを選択する必要があります。SeqViewからに移行するときにどのような変換が実行されるかを言うのは困難ですがParSeq、この不必要な複雑さが原因OutOfMemoryErrorです。

Update2

はい、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 ) のように並列コレクションを使用するよりもわずかに高速ですが、2 番目のジェネレーターでを削除すると、そのソリューションのパフォーマンスはほぼ同じになります。

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
}

アクターの良いところは、命令型コードを使用しながら並列処理を実行できることです。したがって、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 に答える