Scala Actor素筛

Question

我是一名新的 java 程序员，最近被告知要检查 scala 的并发实现。我认为一个简单的（尽管不是说明并发性的最佳例子）示例可能是让参与者解决埃拉托斯特尼筛法。到目前为止，我已经拼凑了一些东西，但我不确定我要走的方向是否接近正确。这是我当前的代码：

import scala.actors.Actor
import scala.actors.Actor._
import Array._

class PrimeActor(val id: Int) extends Actor {

     //Runs one Prime of the Sieve of Eratosthenes
     def sieve(p: Int, list: Array[Int]) {
       var i = 1
       var place = 0
       while(list contains (i * p)) {
       place = list.indexOf(i * p)
       if (list(place) != 0) 
          list.update(place, 0)
       i += 1
       }
     }

   //Checks to see if there is a higher prime in the list
   //If so, creates a new actor to handle it and sends
   //it the list and the prime
   def findandCreateNextPrime(p: Int, list: Array[Int]){
      var i = 1
      var place = list.indexOf(p)
      while(list(place + i) == 0 && (p + i) <= list.last) {
         i += 1
      }
      val newP = list(place+i)

      if (list contains (p + i)) {
         if ((p + i) equals list.last) {
            print(list.last)
         } else {
            print(", ")
            val pA = new PrimeActor(newP)
            pA.start()
            pA ! (list(newP), list)
         } 
     } else {
     println("DONE")
    } 
  }

   //Actor behavior
   def act() {
      loop {
         react{
            case (recievedP: Int, recievedList: Array[Int]) =>
               print(recievedP)
               sieve(recievedP, recievedList)
               findandCreateNextPrime(recievedP, recievedList)
               exit()
         }
      }
   }
}

任何帮助或指导意见将不胜感激。谢谢！

Answer 1

在 Scala 中，您可以以函数式风格编写代码。我建议你使用它。首先忘记Array，它是一个可变集合，而 scala 中的可变集合是邪恶的。最好使用不可变集合作为List. 关于 的说法也是如此var。val尽可能 尝试使用。
我猜想，在 Scala 中实现埃拉托斯特尼筛法的最简单方法如下：

import scala.annotations.tailrec

def sieve(until: Int): Seq[Int] = {
  @tailrec
  def loop(i: Int, primes: Seq[Int]): Seq[Int] = {
    // we reached the desired end
    if (i > until) primes
    else {
      // we already found a factor of this i
      if (primes exists(i % _ == 0)) loop(i + 2, primes)
      // we found a new prime
      else loop(i + 2, primes :+ i)
    }
  }
  // there is no prime smaller than 2
  if (until < 2) Seq.empty[Int]
  // starting with 3 has the advantage, we only need to check i + 2
  else loop(3, Seq.empty[Int] :+ 2)
}

如果您刚刚开始使用 Scala，这可能有点令人困惑，但我会解释一下。
我们想要一个由所有素数组成的序列，直到达到一个特定的数字。我们定义一个递归函数，它将检查每个第二个数字是否是素数。因为它是尾递归的，所以编译器会将其优化为 for 理解，所以我们不需要担心StackOverflows。如果我们的计数器超过最大值 ( until)，我们将返回我们检测到的素数。这是我们的递归锚。否则，我们检查是否找到了素数，这是我们当前 的一个因子i。如果有，我们就跳到下一个候选，否则我们添加i到素数并继续下一个候选。
注意：注释不是必需的，但如果存在，编译器会警告您，如果函数不是尾递归的。

使用我建议的代码会导致我们遇到问题，您不能再使用并发性。《Scala 编程》中的一章对 scala 并发性做了很好的介绍。他们通过并发解决了理发师睡觉的问题。这是他们的解决方案的链接。