C# Nested foreach loop optimization

Question

I've got a nested foreach loop that I really need to cut the computation time on. Each collection is at about 50 members, so the extrapolation is huge. I've looked at a lot of information about SelectMany, but I'm still not entirely sure how to use it, or if it's the correct solution.

List<string> StringList; //Populated in previous code
Type[] assemblyTypes = RandomAssembly.GetTypes();

foreach (String name in StringList)
{                               
  foreach (Type at in assemblyTypes)
  {                             
    if (name == at.Name)
    {                                       
      //Do stuff.
    }
  }
}

Thanks in advance!

Steve Greatrex · Accepted Answer · 2011-10-11T16:29:51.883

4

Use a lookup (such as a dictionary) to increase the speed of checking for a type name:

List<string> StringList; //Populated in previous code
Dictionary<string,Type> assemblyTypes = RandomAssembly.GetTypes()
    .ToDictionary(t => t.Name, t => t);

foreach (String name in StringList)
{                               
    if (assemblyTypes.ContainsKey(name))
    {                                       
      //Do stuff.
    }
  }
}

You should also check which of the 2 collections (StringList or assemblyTypes) is likely to be larger. You generally want the larger one to be converted to the lookup in order to reduce the number of iterations.

edited Oct 11 '11 at 16:29

answered Oct 11 '11 at 16:23

Steve Greatrex

15,789
5
59
73

1

On a side-note, you might want to adjust this to use t.FullName since a library with common controls in separate namespaces may cause collisions in the dictionary key. My assumption would be that OP would need to account for this in the StringList variable. – Joel Etherton Oct 11 '11 at 17:07
@JoelEtherton good point, but as he states that the list of strings comes from elsewhere (and was using `.Name` in his example) I'll leave the post as-is for now – Steve Greatrex Oct 11 '11 at 18:21
@SteveGreatrex This method seems like the right thing to do, but it's still a bit taxing. StringList has up to 40 members, and it needs to be the parent loop because of how the "do stuff" section needs to be ordered. Reducing the size of StringList reduces the computation time drastically, but that's not a real world scenario. Ideas? – sburke1988 Oct 11 '11 at 19:16
If we're only talking about 40 members in `StringList` then I'd be surprised if it's the iteration over that list that is causing the problem. Two questions: how many of the items in `StringList` *are* in the `assemblyTypes` collection; and what is 'do stuff' doing? Given that it slightly changes the question it might be a good idea to put that info in another question and post the link here – Steve Greatrex Oct 11 '11 at 20:40
@SteveGreatrex http://stackoverflow.com/questions/7732948/high-computation-time All items in `StringList` are in `assemblyTypes`, and `assemblyTypes` only has a few more class definitions in it. – sburke1988 Oct 11 '11 at 21:50

Lucas · Answer 2 · 2011-10-11T16:27:15.613

2

Load Type[] into a Dictionary or HashSet (depending on your version of .NET) and then the inner loop disappears.

List<string> StringList; //Populated in previous code
Type[] assemblyTypes = RandomAssembly.GetTypes();
Dictionary<String,Type> typesHash = new Dictionary<String,Type>();
foreach ( Type type in assemblyTypes ) {
  typesHash.Add( type.Name, type );
}

foreach (String name in StringList) {                               
  Type type = null;
  if ( typesHash.TryGetValue( name, out type ) ) {
    // do something with type
  }
}

edited Oct 11 '11 at 16:27

answered Oct 11 '11 at 16:21

Lucas

14,227
9
74
124

The inner loop didn't disappear, it's just embedded in the hash's TryGetValue method. The search in that portion of the loop has been reduced using a hash though. – Joel Etherton Oct 11 '11 at 16:35

score 0 · Answer 3 · answered Oct 11 '11 at 16:20

0

You might try something like:

assemblyTypes.Where(x => StringList.Contains(x.Name));

Keep in mind this is case sensitive and ignores whitespace, so you will need to add case consideration or trimming if that's an issue.

Edit: (example for loop usage)

foreach (Type item in assemblyTypes.Where(x => StringList.Contains(x.Name)))
{
    // Do stuff
}

answered Oct 11 '11 at 16:20

Joel Etherton

37,325
10
89
104

This will still cause the code to iterate through `StringList` once for every type in the assembly - a dictionary will be much quicker – Steve Greatrex Oct 11 '11 at 16:25
@Steve Greatrex: I didn't choose the type (OP chose List), but even in using a dictionary you'd either have to use x.Keys.Contains (which does the same thing as my example) or provide more code to the predicate by accessing the dictionary item by key value directly. I'm not sure the gains would be worth it, but I'd be interested in OP's benchmarks involving both. – Joel Etherton Oct 11 '11 at 16:33
If you use a `Dictionary` you can use the `ContainsKey` method that uses hashing under the covers to lookup keys. Particularly for larger collections, `ContainsKey` will be **massively** faster than iterating through the `Keys` collection – Steve Greatrex Oct 11 '11 at 16:40
@Steve: When you first made mention of the `List` I thought your intention was to change that object rather than use the dictionary to control the types. This method of access would create a faster check for the key at that level. – Joel Etherton Oct 11 '11 at 17:00

score 0 · Answer 4 · answered Oct 11 '11 at 16:25

0

If your array/list contains lots of items , you can try using Parallel ForEach loop.

answered Oct 11 '11 at 16:25

MichaelS

7,023
10
51
75

score 0 · Answer 5 · answered Oct 11 '11 at 17:18

0

The best optimization might be by querying not for the name but instead for an implemented interface.

Make sure you are optimizing the correct issue/part of your code.

answered Oct 11 '11 at 17:18

Emond

50,210
11
84
115

C# Nested foreach loop optimization

5 Answers5

Linked