Foreach very slow C#

Question

I have a foreach, in this foreach I go through a list and within this foreach I have a condition to check if in another list that have 200 thousand row there is certain information that is a string.

I would like make it more quickly.

  foreach(var dto in List){
    // the problem is here
    if(anotherList.Any(d => d.id == dto.id && d.line.equals(dto.line))) 
          continue;
    }

I hope make it faster.

Answer 1

Any has complexity of O(n) where n is number of elements in the collection (anotherList) so you code has overall complexity of O(m*n) where m is number of elements in List. If id is unique then you can create lookup dictionary which should have constant lookup time in general case and do something like:

var dict = anotherList
  .ToDictionary(d => d.Id);

foreach(var dto in List)
{
    if (dict.TryGetValue(dto.Id, out var val) && val.line.equals(dto.line))
    {
        continue;
    }
}

Which should reduce complexity to O(m+n).

If you have several strings per Id you can consider following options:

1. Use Lookup<TKey,TElement> in case when there are not much strings per Id:

Represents a collection of keys each mapped to one or more values.

var lookup = anotherList.ToLookup(d => d.Id) and then search collection of matched elements

2. Build dictionary from Id to HashSet<strings> and check the hashset too :

var dictOfSets = anotherList
    .GroupBy(d => d.Id)
    .ToDictionary(gr => gr.Key, gr => gr.Select(d => d.Line).ToHashSet());

foreach(var dto in List)
{
    if (dictOfSets.TryGetValue(dto.Id, out var val) && val.Contains(dto.Line))
    {
        continue;
    }
}

3. Try leveraging value tuples with it's generated GetHashcode and Equals to build corresponding hashtable (basic idea is the same - you need "constant" lookup):

var hashSet = anotherList
    .Select(d => (d.Id, d.Line))
    .ToHashSet();

foreach(var dto in List)
{
    if (hashSet.Contains((dto.Id, dto.Line)))
    {
        continue;
    }
}

Read more:

• Time complexity
• Know Thy Complexities!
• Dictionary<TKey,TValue>

  The Dictionary<TKey,TValue> generic class provides a mapping from a set of keys to a set of values. Each addition to the dictionary consists of a value and its associated key. Retrieving a value by using its key is very fast, close to O(1), because the Dictionary<TKey,TValue> class is implemented as a hash table.

• Collections doc.