如何计算 class 引用自身的项目总数

Question

我是 Scala 新手。我需要计算列表中的类别数，我正在尝试构建尾递归函数，但没有成功。

case class Category(name:String, children: List[Category])

val lists = List(
  Category("1",
    List(Category("1.1",
      List(Category("1.2", Nil))
    ))
  )
  ,Category("2", Nil),
  Category("3",
    List(Category("3.1", Nil))
  )
)

Answer 1

考虑以下想法。

让我们定义函数 childCount，收集类别（猫）和 children 的数量（acc）。为了组织 tail-recursive 处理，我们首先从集合中获取 child 并递增 acc。所以我们已经处理了第一个项目，但还有一些项目要处理 - 第一个元素的 children。思路是将这些未处理的children放到children集合的末尾，再次调用childCount

你可以这样实现：

@tailrec
def childCount(cats:Stream[Category], acc:Int):Int = 
  cats match {
    case Stream.Empty => acc
    case x #:: xs => childCount(xs ++ x.children, acc+1)
  }

称之为：

val count = childCount(lists.toStream, 0)

Answer 2

如果您使用列表而不是流并在前面附加元素，Nyavro 的解决方案可以更快（几个数量级）。这是因为 x.children 通常比 xs 短很多，而 Scala 的 List 是一个不可变的单链表，使得前置操作比追加操作快得多。这是一个例子

import scala.annotation.tailrec

case class Category(name:String, children: List[Category])

@tailrec
def childCount(cats:Stream[Category], acc:Int):Int =
  cats match {
    case Stream.Empty => acc
    case x #:: xs => childCount(xs ++ x.children, acc+1)
  }

@tailrec
def childCount2(cats: List[Category], acc:Int): Int =
  cats match {
    case Nil => acc
    case x :: xs => childCount2(x.children ++ xs, acc + 1)
  }

def generate(depth: Int, children: Int): List[Category] = {
  if(depth == 0) Nil
  else (0 until children).map(i => Category("abc", generate(depth - 1, children))).toList
}

val list = generate(8, 3)

var start = System.nanoTime
var count = childCount(list.toStream, 0)
var end = System.nanoTime
println("count: " + count)
println("time: " + ((end - start)/1e6) + "ms")

start = System.nanoTime
count = childCount2(list, 0)
end = System.nanoTime
println("count: " + count)
println("time: " + ((end - start)/1e6) + "ms")

输出：

count: 9840
time: 2226.761485ms
count: 9840
time: 3.90171ms

如何计算 class 引用自身的项目总数

How to count number of total items where a class references itself

scala

tail-recursion