このメソッドをもっともっとScalaliciousにするには

Question

私は単純な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を使った関連付けです。

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

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

すばらしいScalaコレクションを使用することに加えて、ツリーノードのいくつかの前後のフィルタ処理に並列処理を使用することでスピードも向上しました。私は、左/右のノード値を追跡するもっと慣用的な方法を見つけたいと思っていました。 @dhgからの答えを見た後、それはさらに良くなった。フィルタの代わりにgroupByを使用すると、アルゴリズム（大部分は？）が2次ではなく線形に変わります！

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

Answer 1

あなたのコードは、インオーダートラバーサル番号を計算することが表示されます。

あなたのコードをより良くしたいと思うのは、現在の値を下に持ち、更新された値を上に渡すfoldです。 walkに電話するたびにtreeNodes.filter(...)に電話するのを防ぐため、walktreeの前にtreeNodes.groupBy(_.parentId)を実行する価値があることに注意してください。

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

製造するため

：？ `treeNodes`が定義されている

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

Answer 2

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

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) 

オフ対1のエラーが発生する可能性があります。 （より良いhttp://codereview.stackexchange.comに適し）

いくつかのランダムな思考：

valcaseのクラスの暗黙のです：私たちはそれを推測する必要が...コンパイル

• トライ投稿がTreeNodeのシーケンスであります：

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

• 明示的に避ける=Unit機能のためのD 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(_))