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:

Discreditable

Is DogTypeList a list of all dog types and ParentDogTypeList a subset of dog types? – Amasa

Are these lists coming from a database? – Eventuality

@Sam Saffron yeah both the lists are from DB. – Discreditable

@Preet Sangha I have more than 3 inner foreach of same kind so i thought of reducing the foreach – Discreditable

@Sri, then can you edit the question include your db schema for the tables here. a direct query will likely be fastest – Eventuality

Check: If a Dog has more than 1 Child you want it in the Listbox multiple times? Your code seems to do an Outer Join. – Cameliacamella

@Henk Holterman Edited my question to explain the complete scenario – Discreditable

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.

Ptolemy

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

Elementary

Agree that AddRange will probably help out a lot. – Eventuality

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

Ethelind

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.

Eventuality

Edited my question to explain the complete sceanrio – Discreditable

yes exactly but how do i populate the List box without any loop? – Discreditable

@Sri, a single query and a single loop, I can't help out anymore without a table schema and SQL flavor you are using (assuming SQL Server) – Eventuality

Updated with Schema I use Mysql – Discreditable

I used two queries one which would fetch the count for leaf and child. other one is used to get the categories which would help to find which child falls under which parent! – Discreditable

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

Hakan

Answer 6

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

Confusion

Answer 7

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

Ethelind

Doesn't that still have an implicit nested loop? – Succeed

This is still O(n^2) ;-( only with lazy foreach in ChildDoglist container without any optimisation. – Ptolemy