1

算法就是这样。

    def fib(x: Int): BigInt = {
        x match {
            case 1 => BigInt(1)
            case 2 => BigInt(1)
            case x => fib(x-1) + fib(x-2)
        }
    }

我尝试使算法与 Scala 中的 Actor 并行。但是与没有 Actor 的代码相比，我的代码非常慢！

有没有让它工作的好方法？

4

2 回答 2

2

对于不大的n，串行代码总是会更快（在尾递归的情况下要快得多）。这是因为调用一个新的函数会比启动一个新的actor更快。另外，线程和上下文切换之间会存在争用。

在下面的代码中，我为每个n > 2. 可以有很多优化的方法，但我只是简单地使用递归T(n) = T(n-1) + T(n-2)到串行一个。

import akka.actor.Actor
import akka.actor.Props
import akka.actor.ActorSystem
import akka.event.Logging
import akka.actor.ActorRef
import akka.routing.RoundRobinRouter

object Fib extends App {

trait Fib
case class N(val n: Int) extends Fib

case class Ans(n: Int)
class FibN(listen: ActorRef) extends Actor {

var numOfResults = 0;
var ans = 0;
val log = Logging(context.system, this)

def receive = {
  case N(x) => {
    //println(self.path+"-Message N(x) "+x)
    val others = context.actorOf(Props(new FibN(self)).withRouter(RoundRobinRouter(2)), name = "Fibn:" + x)
    if(x==1 || x==2)
      listen ! new Ans(1)
    else if(x>2){
      others ! new N(x-1)
      others ! new N(x-2)
    }


  }

  case Ans(x) => {
    //println(self.path+" Ans(x) "+x+" numOfResults "+numOfResults+" from "+sender.path)
    numOfResults += 1
    ans = ans + x;
    if (numOfResults == 2){
      //println(self.path+"sending back to sender "+listen.path+" numOfResults "+numOfResults)
      listen ! Ans(ans)
    }


  }
  case _ => println(self.path+"Not valid")

}

}


class Listener extends Actor{
val log = Logging(context.system, this)
var st:Long = 0;
def receive = {
  case Ans(x) => {
    println(self.path+"\n\nAns is "+x+" time taken: "+(System.currentTimeMillis() - st))
    context.system.shutdown
  }
  case N(x) => {
    println(self.path+" Message Received "+x)
    val actor = context.actorOf(Props(new FibN(self)),"FibN")
    st = System.currentTimeMillis()
    actor ! new N(x)
  }
  case _ => println(self.path+" Invalid request")
 }
}

val system = ActorSystem("Fibanoccia")
val listener = system.actorOf(Props[Listener],"Listener")
listener ! new N(25)
}

正如预期的那样，这要慢得多。除非n非常大，否则由于上述原因，actor 总是会变慢。对于较大的“n”，可以分解。

于 2013-06-14T10:41:16.347 回答
0

我不知道 Scala 但你想试试这个吗？

def fib(a:BigInt, b:BigInt, n: Int): BigInt = {
    n match {
        case 1 => BigInt(a) + BigInt(b)
        case x => fib(b, a + b, n - 1)
    }
}

我不知道语法，但这个概念可能会有所帮助。使用 0 和 1 作为前两个参数。这是一个 O(n) 算法。

为什么不使用具有 O(log(n)) 出色时间复杂度的快速功率优化矩阵乘法？

于 2013-06-14T10:46:41.283 回答