2

次のようなノードで定義された2つのツリー（パス）があります

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

親がnullになるまで2つのノードを並行して移動したい：

擬似：

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 でこれを行うためのよりエレガントでパフォーマンスの高い方法はありますか?

誤解を避けるために: 同時実行に関する問題ではありません!

4

3 に答える 3

3 
@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?
}
于 2013-01-29T19:00:51.857 に答える
3

親を null にすることはできません。

まず、正しくしましょう :

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)
      }

}
于 2013-01-29T18:44:01.177 に答える
-1

op が単純な操作である場合、トラバースにかなりの時間がかかるため、効率的に並列実行することはできません。

op がより複雑な (つまり、時間のかかる) 操作である場合は、並行して行うことができます。ただし、最初に ParVector などに変換する必要があります。

それをトラバースするよりパフォーマンスの高い方法はないと思います。ただし、Stream によるより洗練された (ただし、おそらくパフォーマンスは高くない) ソリューションがあります。

def pathTo(start: Node): Stream[Node] = start.getParent match{
    case null => Stream.empty
    case nextPoint => Stream.cons(start, pathTo(nextPoint))
}
于 2013-01-29T18:42:38.107 に答える