我該如何使這種方法更Scalalicious

Question

我有一個函數，計算一些簡單的node.id，node.parentId關聯的treeNodes集合的左右節點值。它非常簡單並且運作良好......但是，我想知道是否有更習慣的方法。特別是有沒有一種方法來跟蹤左/右值，而不使用一些外部跟蹤值，但仍然保持美味的遞歸。

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

編輯 - 節點列表取自數據庫。將節點拉入適當的樹會花費太多時間。我正在將一個單子列表放入記憶中，而我所擁有的是一個通過節點標識符與父母和孩子相關的關聯。

添加左/右節點值允許我通過單個SQL查詢獲得所有兒童（和兒童兒童）的快照。

如果父母 - 子女關聯發生變化（他們經常這樣做），計算需要非常快速地執行以保持數據完整性。

除了使用令人​​敬畏的Scala集合外，我還通過對樹節點上的某些前/後過濾使用並行處理來提高速度。我想找到更加習慣的方式來跟蹤左/右節點值。從@dhg看到答案後，情況變得更好了。使用groupBy而不是過濾器可以使算法（主要是？）線性而不是四邊形！

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，它將當前值向下並向上傳遞更新後的值。請注意，在walktree之前執行treeNodes.groupBy(_.parentId)以防止每次撥打walk時致電treeNodes.filter(...)也可能值得。

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

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) 

關閉接一個錯誤都可能發生。

一些隨機的想法（更適合http://codereview.stackexchange.com）：

• ，編譯......我們不得不猜測，嘗試張貼是TreeNode序列：

• val是隱含的case類：

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

• 避免顯式=一個d 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(_))