What is the Most Efficient way to compare large List of integers to smaller List of integers?

algorithm, c#, performance

Solution

Three options now - the first two are more general, in that they don't rely on `MillionIntegerList` being sorted (which wasn't originally specified). The third is preferable in the case where the large list is already sorted.

Option 1

Yes, there's definitely a better way of doing it, using LINQ:

var common = MillionIntegerList.Intersect(TwoThousandIntegerList).ToList();

That will internally use a `HashSet<int>` built via the `TwoThousandIntegerList`, then look up each element of `MillionIntegerList` within it - which will be much more efficient than going through the whole of `TwoThousandIntegerList` each time.

If you only want the non-blacklisted ones, you need:

var valid = MillionIntegerList.Except(TwoThousandIntegerList).ToList();

Note that if you only need to iterate over the results once, you should remove the `ToList` call - I've included it to materialize the results so they can be examined multiple times cheaply. If you're just iterating, the return value of `Intersect` or `Except` will just stream the results, making it much cheaper in terms of memory usage.

Option 2

If you don't want to rely on the implementation details of LINQ to Objects but you still want a hash-based approach:

var hashSet = new HashSet<int>(TwoThousandIntegerList);
hashSet.IntersectWith(MillionIntegerList);
// Now use hashSet

Option 3

The approach of using the fact that the large list is sorted would definitely be useful.

Assuming you don't mind sorting the blacklisted list first as well, you could write a streaming (and general purpose) implementation like this (untested):

// Note: to use this, you'd need to make sure that *both* sequences are sorted.
// You could either sort TwoThousandIntegerList in place, or use LINQ's OrderBy
// method.

public IEnumerable<T> SortedIntersect<T>(this IEnumerable<T> first,
    IEnumerable<T> second) where T : IComparable<T>
{
    using (var firstIterator = first.GetEnumerator())
    {
        if (!firstIterator.MoveNext())
        {
            yield break;
        }

        using (var secondIterator = second.GetEnumerator())
        {
            if (!secondIterator.MoveNext())
            {
                yield break;
            }
            T firstValue = firstIterator.Current;
            T secondValue = secondIterator.Current;

            while (true)
            {
                int comparison = firstValue.CompareTo(secondValue);
                if (comparison == 0) // firstValue == secondValue
                {
                    yield return firstValue;
                }
                else if (comparison < 0) // firstValue < secondValue
                {
                    if (!firstIterator.MoveNext())
                    {
                        yield break;
                    }
                    firstValue = firstIterator.Current;
                }
                else // firstValue > secondValue
                {
                    if (!secondIterator.MoveNext())
                    {
                        yield break;
                    }
                    secondValue = secondIterator.Current;
                }  
            }                
        }
    }
}

(You could take an `IComparer<T>` if you wanted instead of relying on T being comparable.)

Problem

Original source