Creating a list with nested lists

Question

I have made algorithms to create a list with nested lists in order to then show them in a tree view. From what users told me, my view method is fine, but the way I create the final list is probably not doing so well since it takes 9 seconds for my page to load on a test web deploy environment.

This is what my viewmodel looks like:

public class CategoryModel
{
 public long idCategory { get; set; }
 public string name { get; set; }
 public string path{ get; set; }
 public int idParentCategory { get; set; }
 public int order { get; set; }
 public int depth { get; set; }
 // List of child categories that can go deeper.
 // In a way childCategories are branches
 public List<CategoryModel> childCategories { get; set; }
 public int selected { get; set; }
}

So first, I create a list with all categories:

 public List<CategoryModel> GetSuperUserCategories()
 {
 // I use this model for having a final model to pass to the view
 List<CategoryModel> catModel = new List<CategoryModel>();
 // Here I retrieve the categories in Entity Framework form, but I add it to CategoryModel
 // later on so it can be used as a ViewModel, hence avoiding Entities to be
 // in my view
 List<Web_Categories> categories = menuRepo.GetAllCategories();
 if (categories == null || categories.Count == 0)
 return null;
 else
 { // Add all categories to the list here
 foreach(var cat in categories)
 {
 //You can see model properties here
 catModel.Add(new CategoryModel
 {
 idCategory = cat.IDCategorie,
 name = cat.Nom,
 path = cat.CheminPhysique,
 idParentCategory = cat.IDCategorieMere,
 depth = 0,
 order = cat.Ordre,
 childCategories = new List<CategoryModel>()
 });
 }
 return catModel;
 }
}

Then I have a method to determine the nested lists, which categories has child categories and inside these children categories I do the same:

public List<CategoryModel> getDocumentsChildren(List<CategoryModel> categories)
{
 int depth=0;
 try
 {
 long i;
 //Loop on categories
 foreach (var cat in categories)
 {
 i = cat.idCategory;
 if (cat.idParentCategory == 0) {
 cat.depth = 0; //Determine depth for display
 continue;
 }
 //We loop twice to find nested categories
 //Is idParentCategory of our current loop equal to our first loop idCategory?
 foreach (var nextCat in categories)
 {
 if (nextCat.idParentCategory == cat.idCategory && nextCat.idCategory != cat.idCategory)
 {
 nextCat.depth = cat.depth + 1;
 cat.childCategories.Add(nextCat);
 }
 } 
 }
 //Once the children elements have been determined, We can remove top
 //nodes so that they don't show and are only nested 
 foreach (var cat in categories.ToList())
 {
 if (cat.idParentCategory != 1)
 categories.Remove(cat);
 }
 return categories;
 }catch (Exception e)
 {
 Console.WriteLine("Une erreur s'est produite : " + e.ToString());
 return null;
 }
}

Finally I sort all the lists with recursive calls:

public List<CategoryModel> SortCategoryModel(List<CategoryModel> model)
{
 foreach(var m in model)
 {
 if (m.childCategories != null)
 {
 m.childCategories = m.childCategories.OrderBy(c=>c.name).ToList();
 //recurse on childCategories
 m.childCategories = SortCategoryModel(m.childCategories);
 }
 }
 return model;
}

Note that I have a total of 119 categories. I use these methods for all the treeview generations, also for creating a dynamic menu which takes about 15 seconds to load in test deploy environment. I believe the SortCategoryModel method to be the issue but I'm not sure how to improve it?

I also search childDocuments, but I removed it here because it does not change much

After measuring the time it takes to make these three methods combined, I find 5.4357 milliseconds. It seems weird my page turns to 15 seconds loading. I'll mention my virtual machine is always around 90% RAM usage. Could this be an issue?

Answer 1

You have written about 10 times as much code as needed to create your collection of CategoryModel You can greatly simplify this by using linq queries, and gain some performance as well.

I would first suggest you sort on the database, rather than calling a method that returns a in-memory collection of Web_Categories and running multiple loops and recursive methods. Then you can use .Lookup() to group your items

// Sort and group the categories
var groups = _context.Web_Categories
 .OrderBy(x => x.idParentCategory).ThenBy(x => x.name)
 .ToLookup(x => x.idParentCategory, x => new CategoryModel
 {
 idCategory = x.idCategory,
 name = x.name,
 ....
 });

Then use a single loop to assign the child categories

// Assign children
foreach (var item in groups.SelectMany(x => x))
{
 item.childCategories = groups[item.idCategory].ToList();
}

and finally return the top level parents

List<CategoryVM> result = groups[null].ToList();

Its not clear why your view model has properties such as int idParentCategory and int order and int depth, and based on you (now closed) previous question they are not necessary. In addition, I suggest your idParentCategory property in the data model/database table be nullable, so that a value of null (rather than a value of 0) denotes a top level category.

• Flexabust Bergson: Thanks for your answer. idParentCategory refers to the parent category of a category. It is organized this way in my table Web_Categories, this is how you know which elements are child elements. In the code you proposed, how do we know it's a child element (assign children part)? As for depth, I used it for creating my menu and adding css to elements that need a bigger margin, should've removed it here since indeed it is not relevant. Order I have left because it is in the table but I found no use for it (it's more of a specification, I have to talk to my boss about this).
• Flexabust Bergson: Also, isn't in the same 'assign children' part : item.Categories should be item.childCategories? I understand more now for the ambiguity of idParentCategory, I do it because I create the model, and then to know children I use it, but I guess with a method more like yours, I won't necessarily need it. It all depends if I determine children directly on DB access or after creating the model. If I determine the children using the model, then I need this property to know which elements are child.
• Stephen Muecke: Yes, I understand what the idParentCategory is for. What I'm saying is that it should be a nullable field. If the Web_Categories is a top level category, its value should be null (not 0)
• Stephen Muecke: And you do not need the depth property, that can simply be done using css (I will show how to do that later)
• Stephen Muecke: Yes, it should be item.childCategories (will edit in a moment)

Answer 2

What is sure it's that you have a bottleneck so my approach to find out would be to measure every method execution by using a stopwatch...

Also, after a second sight, I see too many for each loops, you might rethink a bit your algorithm to minimize so many loops and also try linq to, for instance, order the results or use where clauses.