Comment compter le nombre total d'articles pour lesquels une classe fait référence

Question

Je suis nouveau à scala. J'ai besoin de compter le nombre de catégories dans la liste, et j'essaye de construire une fonction récursive de queue, sans aucun succès.

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

solution de Nyavro peut être beaucoup plus rapide (de plusieurs ordres de grandeur) si vous utilisez des listes au lieu des cours d'eau et ajouter également des éléments à l'avant. Cela est dû au fait que x.children est généralement beaucoup plus court que xs et que la liste de Scala est une liste unidirectionnelle immuable qui rend les opérations d'avance beaucoup plus rapides que les opérations d'ajout. Voici un exemple

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

sortie:

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

Answer 2

Envisagez l'idée suivante.

Permet de définir la fonction childCount, en prenant la collecte des catégories (chats) et le nombre d'enfants comptent jusqu'à présent (acc). Pour organiser le traitement récursif de la queue, nous prenons le premier enfant de la collection et augmentons l'acc. Nous avons donc traité le premier élément, mais nous avons obtenu plus d'éléments à traiter - les enfants du premier élément. L'idée est de mettre ces enfants non traités à la fin de la collecte des enfants et d'appeler à nouveau childCount.

Vous pouvez la mettre en œuvre ainsi:

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

l'appellent:

val count = childCount(lists.toStream, 0)