Scala Actor Prime Sieve

Question

我是一个新手java程序员，最近被告知要检查scala的并发实现。我想了一个简单的(尽管不是最好的)并发性的例子是让参与者来解决Eratosthenes的筛子。到目前为止，我已经拼凑了一些东西，但我真的不确定我要走的方向是否接近正确。下面是我当前的代码：

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中实现Eratosthenes筛子的最简单方法是：

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- complier，所以我们不需要担心StackOverflows。如果我们的计数器超过最大值(until)，我们就会返回质数，我们检测到的。这是我们的递归锚点。否则，我们检查是否找到质数，这是当前i的一个因子。如果有，我们就跳到下一个候选，否则我们将i加到我们的质数上，然后继续下一个候选。

注意:注释不是必须的，但是如果它存在，编译器会警告你，如果函数不是尾递归的。

使用我建议的代码会导致这个问题，你不能再使用并发了。关于scala中并发的一个很好的介绍，是来自Programming Scala的一章。他们通过一致性解决了睡眠理发师的问题。以下是他们的解决方案的link。

Answer 2

参与者是关于并发性的:不同的任务同时完成，必要时相互通信。

关于演员有两件非常重要的事情：

1. 你只能通过消息与演员交谈。如果你的参与者没有发送返回的消息，或者从消息以外的其他地方获取信息，那么你这样做是错误的。
2. 你不会向参与者发送可变数据结构。如果你这样做了，你就做错了。

因此，您在示例中违反了这两个规则，而且参与者之间实际上没有交互。由于这些原因，演员在这里可能是错误的选择。在这种情况下，在并行集合中寻找答案可能会更好，但它们在这里也不会对您有所帮助。

Eratosthenes的筛子本质上是一个串行算法，无论是并行还是并发，都不是一个好的选择。