1

我对使用 scala 和 akka 进行编程比较陌生，我尝试使用 akka 演员为 n-queens 问题编写解决方案。不幸的是，我的想法效果不佳：与顺序方法相比，计算所有解决方案需要更长的时间，并且程序永远不会终止。但是，一些正确的解决方案会打印到控制台。这是我的代码：

  case class Work(list: List[Point])
  case class Reply(list: List[Point])

  class QueenWorker(val master: ActorRef) extends Actor {
        override def preStart() = {
      println("new worker")
    }
    def receive = {
      case Work(list) =>
        val len = list.length
        if (len < size) {
          val actors = for (
            i <- 0 until size if (!list.exists(_.y == i))
          ) yield (context.actorOf(Props(new QueenWorker(master))), i)
          actors.foreach { case (actor, pos) => actor ! Work(list :+ (new Point(len, pos))) }

   } else {
          if (check(list)) { //check() checks whether the solution is valid
            master ! Reply(list)
            println("solution found!")
          }
          //else sender ! Reply(List[List[Point]]())
        }
         //context.stop(self) //when do I have to use it?
         //println("worker stopped - len "+len)
    }
  }

  class QueenMaster extends Actor {
    override def preStart() = {
      println("preStart")
      context.actorOf(Props(new QueenWorker(self))) ! Work(List[Point]())
    }

      def receive = {//print solution to console
      case Reply(list) =>
        for (x <- 0 until size) {
          for (y <- 0 until size) {
            if (list.exists(p => p.x == x && p.y == y)) print("x ") else print("o ")
          }
          println()
        }
        println()
    }
  }

 def runParallel {
    val system = ActorSystem("QueenSystem")
    val queenMaster = system.actorOf(Props[QueenMaster])
  }

我的意图是为每个新的回溯迭代创建一个新的演员。如果一个参与者找到了一个有效的解决方案，它将被发送给将其打印到控制台的主控。

  • 程序永远不会终止。但是，如果我删除 //context.stop(self) 周围的评论，根本找不到解决方案。我该如何解决这个问题？
  • 我的整个方法似乎是错误的。有什么更好的呢？
  • 是否有可能找到使用期货而不是演员的并行解决方案？

提前致谢！

4

1 回答 1

0

经过一些调整后，我设法运行了您的程序并获得了size=8. 出于调试目的，将这两行添加到runParallel：

readLine()
system.shutdown()

当程序完成时——按回车键——这将导致shutdown方法被调用并且你的程序将退出。

我在 8 核 i7 2.2Ghz 机器上运行 - 所以你的结果可能会有所不同。

关于性能，这几乎是一个低效的解决方案，原因如下：在回溯过程的每一步 - 即对于每个尝试过的部分解决方案 - 您正在创建和执行一个简单的循环，为下一个提议的解决方案创建更多的参与者.

现在，在 Akka 中创建一个演员非常快，但我敢说，在你的情况下，创建一个演员的开销比它正在做的实际工作更大（甚至可能是一个数量级）——我还没有测试过这个，但很有可能。

此处分析的部分解决方案的数量与板的大小呈指数关系。那就是您正在创建指数级数量的参与者 - 这是很多开销，您肯定会失去通过并行计算解决方案获得的任何优势。

我们怎样才能使它变得更好？好吧，首先，我们可以少创建几个演员。

让我们创建一个固定的QueenWorker演员池（与您计算机中的核心数量相同），并将它们放在SmallesMailboxRouter后面。

当您的工作人员检查已处理消息中的当前解决方案Work而不是创建新参与者时，他们会将新提出的解决方案发送到路由器，路由器将以Work统一的方式将这些新消息发送到其路由。

一个工人actor现在将处理更多的部分解决方案，而不仅仅是一个，就像它之前所做的那样。这比以前要好得多的实际工作/akka_housekeeping 比率。

我们还能做得更好吗？我认为我们可以，如果你对你的问题建模有点不同。在皇后问题中，一般来说，在回溯中，您正在探索部分解决方案树。在算法的每个步骤中，当您从现有解决方案生成更多部分解决方案时，您正在分支您的树。您的方法的问题在于，当您在算法中分支时，您也在并发流中分支 - 我在这里指的是您正在发送一个新的工作消息以由另一个参与者处理的事实。这很好，但是如果您添加数字，您会发现这是很多开销，不会为您带来任何时间优势。

那是因为你的Work任务的粒度非常小。你在发送消息之间做的工作很少——这会影响你的表现。Work您可以让您的工作人员在生成新消息之前探索更大的部分解决方案。

例如，如果您有一个 8 核 CPU，并且问题已经存在，size=8那么您最好创建 8 个工作人员并将任务分配给工作人员 K，以计算在第一行的 K 列中具有皇后的解决方案。现在每个工人只执行一项Work任务，约占总工作量的 1/8——这将产生更好的结果。

关于期货的解决方案 - 你当然可以这样做，但我认为程序时间将与具有固定演员池的演员解决方案大致相同。但我鼓励你尝试，因为我可能是错的。

于 2013-04-05T23:14:39.003 回答