Remove foreach - c# code-optimization

Question

How to optimize this code?

ParentDoglist, ChildDoglistis - Ilist. dogListBox - List Box

foreach (Dog ParentDog in ParentDoglist)
{
 foreach (Dog ChildDog in ChildDoglist)
 {
  if(ParentDog.StatusID==ChildDog.StatusID)
  dogListBox.Items.Add(new ListItem(ParentDog.Name, ParentDog.Key));
 }
}

EDIT: ParentDogTypeList, DogTypeList were renamed as ParentDoglist,ChildDoglist, where both are not related with each other

if(ParentDog.Key==ChildDog.Key)

was changed to

if(ParentDog.StatusID==ChildDog.StatusID)

Complete Story:

I need to populate a drop down which would reciprocate a Parent Child relationship. There are certain dogs which may not have any child and that would be called as leafdog. And I also need to show the number of dogs in that particular category

DD would look like

Parent1
  Child11 (10)
  Child12 (12)
Parent2
  Child21 (23)
  Child22 (20)
Leaf1 (20)
Leaf2 (34)

So, the ParentDoglist would bring all the Child and leaf elements along with the count and ChildDogList would have the Parent and leaf ID's hence I would be able to populate the respective Child to their Parent and bind the leaf directly.

The Parent, Child and Leaf Dog would be maintain in one table and differentiated by statusid and count would be in another table.

No parent would have any count, only child and leaf would have count

Table Schema:

Answer 1

You can sort ParentDoglist and ChildDoglist and do linear O(n) finding algorithm insead of this O(n^2).

But you can sort the containers in O((ParentDoglist.Size() + ChildDoglist.Size()) * log2(ParentDoglist.Size() + ChildDoglist.Size())).

Then if you run this code ONCE ONLY, your algorithm is optimal. But if you are searching MORE THAN ONE TIME, the optimal solution is sort the containers and do the comparison in linear time, but if yours container can change bettwen search functions was lanuched and you using "more than once time solution" you must use RB-Tree container to carry this elements, because with normal list after container was changed you can't return to sorted state in O(log(n)) time.

Answer 2

        foreach (var ParentDog in ParentDoglist.Where(p=>ChildDoglist.Any(c=>c.Key== p.Key)).ToList())
            dogListBox.Items.Add(new ListItem(ParentDog.Name, ParentDog.Key));

That's how you would do it with LinQ

Answer 3

Your biggest problem is probably the dogListBox.Items.Add. Adding each items one at a time is quite expensive. ListBox.Items.AddRange is more efficient.

To make the inner loop much smaller you can create a lookup for the keys in the inner loop.

List<ListItem> listItems = new List<ListItem>();
ILookup<string, Dog> childDogsPerKey = ChildDoglist.ToLookup(dog => dog.Key);
foreach (Dog ParentDog in ParentDoglist)
{
    foreach (Dog ChildDog in childDogsPerKey[ParentDog.Key])
    {
        listItems.Add(new ListItem(ParentDog.Name, ParentDog.Key));
    }
}
dogListBox.Items.AddRange(listItems.ToArray());

This code assumes that several child dogs can have the same key. If there can only be one child dog per key you may use .ToDictionary() instead

Answer 4

Since this is coming from the DB, database round trips are likely to be a performance killer. Also the comparison ParentDog.Key==ChildDog.Key can be done in SQL, so you don't pull all that data to your app just to discard it.

Redesign this so you do a single select to grab all the data in one query.

Albin mentioned AddRange, but you can even take this a step further and virtualize your grid so it only pulls the rows displayed to the user when she is looking at that portion of the grid.

EDIT

To generate your list it appears you need to return something like this from the DB:

Parent1, null, null
Parent1, Child1, 110
Parent1, Child12, 12
Parent2, null, null
Parent2, Child21, 23
Parent2, Child22 ,20
Leaf1, null, 20
Leaf2, null, 34

This looks like you need some sort of left join and a count, with a potential union all thrown in.

Answer 5

It's not the foreach that is slow, it's adding and rendering new items.

Add beginupdate/endupdate:

dogListBox.BeginUpdate();
foreach (Dog ParentDog in ParentDoglist) 
{ 
 foreach (Dog ChildDog in ChildDoglist) 
 { 
  if(ParentDog.Key==ChildDog.Key) 
  dogListBox.Items.Add(new ListItem(ParentDog.Name, ParentDog.Key)); 
 } 
} 
dogListBox.EndUpdate();

Answer 6

I still think the most elegant and optimized way is to use Linq for it.

box.Items.AddRange(
   ParentDoglist.Where(p=>ChildDoglist.Any(c=>c.StatusID== p.StatusID))
    .Select(r=>new ListItem(r.StatusID, r.Name)).ToArray());

That's all and it's only one line. If you prefer joins, you can do it with that query.

box.Items.AddRange(
   ParentDoglist.Join(ChildDoglist, p => p.StatusID, c => c.StatusID, (p,c)=>p)
    .Select(r=>new ListItem(r.StatusID, r.Name)).ToArray());

Answer 7

You can replace the nested foreach loop with a simple Linq expression. For this to work you need to be using System.Linq;

foreach (Dog ParentDog in 
            (from dog in ParentDogList
             from ChildDog in dog.StatusId
             where dog.StatusId == ChildDog.StatusId)
             select dog) )
{
    dogListBox.Items.Add(new ListItem(ParentDog.Name, ParentDog.Key));
}