Tree of objects

Question

I have this list of 2000+ categories that need to be organized in a tree before being sent to the controller and the View so the javascript plugin can render them correctly.

I am already doing this but the performance is terrible. It is taking like 30 seconds to assemble the tree.

I can't see what is dropping performance here. Can you guys help me to improve this code?

var allCategories = dal.Listar();
List<Model.Entity.CategoriaCursoEADVO> nestedCategories = new List<Model.Entity.CategoriaCursoEADVO>();

foreach (Model.Entity.CategoriaCursoEAD item in allCategories)
{
    if (item.IdCategoriaPai == null)
    {
        CategoriaCursoEADVO child = new CategoriaCursoEADVO();

        child.id = item.Id;
        child.text = item.Descricao;
        nestedCategories.Add(child);
        FillChild(allCategories, child, item.Id);
    }
}

And here is the FillChild method:

public int FillChild(IEnumerable<CategoriaCursoEAD> categorias, CategoriaCursoEADVO parent, int IID)
{
    var childCategories = categorias.Where(w => w.IdCategoriaPai.Equals(IID));
    parent.children = new List<CategoriaCursoEADVO>();

    if (childCategories.Count() > 0)
    {
        foreach (CategoriaCursoEAD cat in childCategories)
        {
            CategoriaCursoEADVO child = new CategoriaCursoEADVO();

            child.id = cat.Id;
            child.text = cat.Descricao;
            parent.children.Add(child);
            FillChild(categorias, child, cat.Id);
        }
        return 0;
    }
    else
    {
        return 0;
    }
}

I think the problem is with the new instances and tried using Parallel loops with no satisfatory level of improvement.

Answer 1

This is a pretty good time to use a HashTable (Dictionary). Something like the below code should help.

    // Convert the flat list into a hash table with the ID
    // of the element as the key
    var dict = allCategories.ToDictionary (i => i.Id);

    // Group categories by the parent id
    var parentGrouping = allCategories.Where(c => c.IdCategoriaPai != null).GroupBy(c => c.ParentId);

    // Since we group the items by parent id, we can find
    // the parent by id in the dictionary and add the children
    // that have that particular id.
    foreach(var groupItem in parentGrouping)
        if(groupItem.Key != null)
            dict[(int)groupItem.Key].children.AddRange(groupItem);

    // Get the root elements.
    var hierarchicalCategories = allCategories.Where(item => item.IdCategoriaPai == null);

    // Do what you need to do here.

This code will create a tree of categories. hierarchicalCategories will contain direct references to the root elements (categories that do not have a parent), assuming that your data is structured that way.