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、シリアルコードは常に高速になります (末尾再帰の場合ははるかに高速です)。これは、新しい関数を呼び出す方が、新しいアクターを開始するよりも高速になるためです。さらに、スレッドとコンテキスト スイッチの間で競合が発生します。

以下のコードでは、 ごとに新しいアクターを開始します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、アクターは前述の理由により常に遅くなります。より大きな「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)
    }
}

構文はわかりませんが、この概念が役立つ場合があります。最初の 2 つの引数として 0 と 1 を使用します。これは O(n) アルゴリズムです。

そして、O(log(n)) という優れた時間計算量を持つ高速電力最適化行列乗算を使用してみませんか?

于 2013-06-14T10:46:41.283 に答える