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

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 3

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 4

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();