3

単純なnode.id、node.parentIdの関連付けが与えられた場合、treeNodeのいくつかのコレクションの左右のノード値を計算する関数があります。それは非常にシンプルで十分に機能します...しかし、まあ、もっと慣用的なアプローチがあるかどうか疑問に思っています。具体的には、外部で追跡された値を使用せずに左/右の値を追跡しながら、おいしい再帰を維持する方法があります。

/* 
 * A tree node
 */
case class TreeNode(val id:String, val parentId: String){
    var left: Int = 0
    var right: Int = 0
}

/* 
 * a method to compute the left/right node values 
 */
def walktree(node: TreeNode) = {
    /* 
     * increment state for the inner function 
     */
    var c = 0

    /*
     * A method to set the increment state
     */
    def increment = { c+=1; c } // poo

    /* 
     * the tasty inner method
     * treeNodes is a List[TreeNode]
     */
    def walk(node: TreeNode): Unit = {
      node.left = increment

      /* 
       * recurse on all direct descendants 
       */
      treeNodes filter( _.parentId == node.id) foreach (walk(_))

      node.right = increment
    }

    walk(node)
}

walktree(someRootNode)

編集-ノードのリストはデータベースから取得されます。ノードを適切なツリーにプルするには、時間がかかりすぎます。私はフラットリストをメモリにプルしています。私が持っているのは、親と子に関連するノードIDを介した関連付けだけです。

左/右ノード値を追加すると、単一のSQLクエリですべての子（および子の子）のスナップショップを取得できます。

親子の関連付けが変更された場合にデータの整合性を維持するには、計算を非常に迅速に実行する必要があります（これは非常に頻繁に行われます）。

素晴らしいScalaコレクションを使用することに加えて、ツリーノードでの事前/事後フィルタリングに並列処理を使用することで速度を向上させました。左/右ノード値を追跡するより慣用的な方法を見つけたかったのです。@dhgからの回答を見た後、それはさらに良くなりました。フィルタの代わりにgroupByを使用すると、アルゴリズムが4次ではなく線形になります（ほとんどの場合？）。

val treeNodeMap = treeNodes.groupBy(_.parentId).withDefaultValue(Nil)

def walktree(node: TreeNode) = {
    def walk(node: TreeNode, counter: Int): Int = {
        node.left = counter 
        node.right = 
          treeNodeMap(node.id) 
          .foldLeft(counter+1) {
            (result, curnode) => walk(curnode, result) + 1
        }
        node.right
    }
    walk(node,1)
}
4

2 に答える 2

6

あなたのコードは、順番にトラバーサル番号を計算しているようです。

コードをより良くしたいのfoldは、現在の値を下に運び、更新された値を上に渡すことだと思います。を呼び出すたびに呼び出さないようにするために、 treeNodes.groupBy(_.parentId)beforeを実行することも価値があることに注意してください。walktreetreeNodes.filter(...)walk

val treeNodes = List(TreeNode("1","0"),TreeNode("2","1"),TreeNode("3","1"))

val treeNodeMap = treeNodes.groupBy(_.parentId).withDefaultValue(Nil)

def walktree2(node: TreeNode) = {
  def walk(node: TreeNode, c: Int): Int = {
    node.left = c
    val newC = 
      treeNodeMap(node.id)         // get the children without filtering
        .foldLeft(c+1)((c, child) => walk(child, c) + 1)
    node.right = newC
    newC
  }

  walk(node, 1)
}

そして、同じ結果が生成されます。

scala> walktree2(TreeNode("0","-1"))
scala> treeNodes.map(n => "(%s,%s)".format(n.left,n.right))
res32: List[String] = List((2,7), (3,4), (5,6))

つまり、次のようにコードを完全に書き直します。

case class TreeNode(        // class is now immutable; `walktree` returns a new tree
  id: String,
  value: Int,               // value to be set during `walktree` 
  left: Option[TreeNode],   // recursively-defined structure
  right: Option[TreeNode])  //   makes traversal much simpler

def walktree(node: TreeNode) = {
  def walk(nodeOption: Option[TreeNode], c: Int): (Option[TreeNode], Int) = {
    nodeOption match {
      case None => (None, c)  // if this child doesn't exist, do nothing
      case Some(node) =>      // if this child exists, recursively walk
        val (newLeft, cLeft) = walk(node.left, c)        // walk the left side
        val newC = cLeft + 1                             // update the value
        val (newRight, cRight) = walk(node.right, newC)  // walk the right side
        (Some(TreeNode(node.id, newC, newLeft, newRight)), cRight)
    }
  }

  walk(Some(node), 0)._1
}

次に、次のように使用できます。

walktree(
  TreeNode("1", -1,
    Some(TreeNode("2", -1,
      Some(TreeNode("3", -1, None, None)),
      Some(TreeNode("4", -1, None, None)))),
    Some(TreeNode("5", -1, None, None))))

生産するには:

Some(TreeNode(1,4,
  Some(TreeNode(2,2,
    Some(TreeNode(3,1,None,None)),
    Some(TreeNode(4,3,None,None)))),
  Some(TreeNode(5,5,None,None))))
于 2012-04-11T16:22:02.990 に答える
1

私があなたのアルゴリズムを正しく取得した場合：

def walktree(node: TreeNode, c: Int): Int = {
    node.left = c

    val c2 = treeNodes.filter(_.parentId == node.id).foldLeft(c + 1) { 
        (cur, n) => walktree(n, cur)
    }

    node.right = c2 + 1
    c2 + 2
}

walktree(new TreeNode("", ""), 0)

オフバイワンエラーが発生する可能性があります。

いくつかのランダムな考え（ http://codereview.stackexchange.comに適しています）：

  • コンパイルする投稿を試してみてください...それは次のシーケンスであると推測する必要がありますTreeNode：

  • valcaseクラスに対して暗黙的です：

    case class TreeNode(val id: String, val parentId: String) {

  • 明示的=および関数の場合Unitは避けてください。Unit

    def walktree(node: TreeNode) = {
def walk(node: TreeNode): Unit = {

  • 副作用のあるメソッドには、次のものが必要()です。

    def increment = {c += 1; c}

  • これは非常に遅いので、子のリストを実際のノードに保存することを検討してください。

    treeNodes filter (_.parentId == node.id) foreach (walk(_))

  • より簡潔な構文は次のようになりますtreeNodes foreach walk：

    treeNodes foreach (walk(_))
于 2012-04-11T16:14:21.620 に答える