scala - 在scala中并行移动两条路径

Question

我有两棵树（路径），由一个节点定义

trait Node {
  def getParent : Node
  def op(n:Node)
}

我想旅行两个节点，直到父节点并行为空，例如：

伪：

def simultanousUp(/*var*/ a:Node,/*var*/ b:Node) = 
     while(a != null) {
          a.op(b); 
          a = a.getParent;
          b = if(b!=null) b.getParent else null /*or throw somthing*/;
      }

问题：在 scala 中是否有更优雅和/或高性能的方式来做到这一点？

为了避免误解：这不是关于并发执行的问题！

Answer 1

父级不能为空。

首先，让我们正确：

trait Node {
  def parent : Option[Node]
  def op(n:Node) // what does op mean ? what is the return type of op ? 
                 //cannot be Unit
}

然后

@scala.annotation.tailrec 
//it makes sure it's tailrec, so it can be optimized
def simultanousUp(a:Node, b:Node): (Node,Node) = {
      a.op(b)
      (a.parent, b.parent) match {
          case (Some(pa), Some(pb)) => simultanousUp(pa,pb)
          case _ => (a,b)
      }

}

Answer 2

@annotation.tailrec final def simultaneousUp(a: Node, b: Node) {
  if (a != null && b != null) {
    a op b
    simultaneousUp(a.getParent, b.getParent)
  }
  // Throw exception or whatever on mismatched lengths?
}

Answer 3

如果 op 是一个简单的操作，你不能有效地并行运行它，因为遍历会消耗大量时间。

如果 op 是更复杂（即耗时）的操作，您可以并行执行。但是，您需要先将其转换为 ParVector 或类似的东西。

---

我认为没有更高效的方式来遍历它。然而，Stream 有一个更优雅（但可能不是那么高效）的解决方案：

def pathTo(start: Node): Stream[Node] = start.getParent match{
    case null => Stream.empty
    case nextPoint => Stream.cons(start, pathTo(nextPoint))
}