斯卡拉 - 扁平化樹狀結構

我從Java庫中收到了一個樹狀結構。因爲我只對樹的「關鍵」值感興趣，所以我試圖壓扁它。樹是由下列種類的零個或多個：斯卡拉 - 扁平化樹狀結構

class R(val key: String, val nodes: java.util.List[R]) {}

用空節點代表一個分支的端部列表。可以通過以下代碼構建一個示例：

val sample = List[R](
    new R("1", List[R](
    new R("2", List[R]().asJava), 
    new R("3", List[R](new R("4", List[R]().asJava)) 
     .asJava)).asJava)).asJava

我無法編寫正確的方法和有效的方法。這是我到目前爲止有：

def flattenTree(tree: List[R]): List[String] = { 
    tree.foldLeft(List[String]())((acc, x) => 
      x.key :: flattenTree(x.nodes.asScala.toList)) 
}

然而，當我運行此代碼，效率低下，因爲它可能是，我仍然得到它不正確。我的結果結果是：

>>> flattenTree(sample.asScala.toList) 
res0: List[String] = List(1, 3, 4)

這意味着由於某種原因，我失去了節點與鍵「2」。

有人可以推薦一種正確和更有效的扁平化樹的方法嗎？

來源

2015-09-06 Will I Am

您可以定義一個函數扁平化的R對象與flatMap：

// required to be able to use flatMap on java.util.List 
import scala.collection.JavaConversions._ 

def flatten(r: R): Seq[String] = { 
    r.key +: r.nodes.flatMap(flatten) 
}

和一個功能扁平化的序列：

def flattenSeq(l: Seq[R]): Seq[String] = l flatMap flatten

r.nodes.flatMap(flatten)是Buffer，所以前面加上它效率不高。它變成二次複雜。所以，如果順序並不重要的是更有效的方法追加：def flatten(r: R): Seq[String] = r.nodes.flatMap(flatten) :+ r.key

來源

2015-09-06 10:08:01 Kolmar

我不確定，也許我是東西，但是孩子們是不支持flatMap的java.util.List。我必須再次轉換成Java，所以平坦的身體會變成「r.key +：r.nodes.asScala.toSeq.flatMap（flatten3）」？ –

@WillIAm哦，對不起，我忘記了包括導入到我的回答 – Kolmar

Thanks！這個JavaConversions._ vs JavaConverters._非常混亂。:)我有後者。 –

您無法在每次連續呼叫中添加累計密鑰。請嘗試以下操作：

def flattenTree(tree: List[R]): List[String] = { 
    tree.foldLeft(List[String]())((acc, x) => 
      x.key :: flattenTree(x.nodes.asScala.toList) ++ acc) 
}

產生的結果是：List(1, 3, 4, 2)，

，或者，如果適當的順序很重要：

def flattenTree(tree: List[R]): List[String] = { 
    tree.foldLeft(List[String]())((acc, x) => 
      acC++ (x.key :: flattenTree(x.nodes.asScala.toList))) 
}

產生的結果是：List(1, 2, 3, 4)

來源

2015-09-06 08:21:22 Shadowlands

謝謝，讓我渡過了難關。我可以繼續，希望稍後有人會提出一個更好的方法來提出這個建議。 –

轉換每個R到Scalaz Tree，並致電flatten做一個預先或遍歷。

import scala.collection.JavaConversions._ 
import scalaz._ 

def rTree(r: R): Tree[String] = 
    Tree.node(r.key, r.nodes.toStream.map(rTree)) 

sample.flatMap(r => rTree(r).flatten): Seq[String] 
// List(1, 2, 3, 4)

編輯：不幸的是，由於a bug in scalaz爲7.1.1版本，這將導致寬樹木堆棧溢出。

來源

2015-09-06 09:19:42

嗯，我嘗試了你的建議，並增加了我的節點10000個項目，但我最後堆棧溢出（介於1000和10000之間）。上述代碼唯一的變化是將List [String]更改爲Seq [String]以使編譯器感到滿意。我打算採用這種方法，因爲它似乎比Kolmar上面提出的方法要快一些。 http://pastebin.com/BbCEm4H4 –

堆棧溢出似乎是scalaz中的一個錯誤:( –

怎麼樣使用Stream就像scalaz作用：

def flatten(rootElem: R): Stream[String] = { 
    def flatten0(elem: R, xs: Stream[String]): Stream[String] = 
    Stream.cons(elem.key, elem.nodes.foldLeft(xs)((acc, x) => flatten0(x, acc))) 

    flatten0(rootElem, Stream.empty) 
}

來源

2015-09-06 13:34:49

斯卡拉 - 扁平化樹狀結構

回答

相關問題