Intersect two colections with .Net 2.0

  • Thread starter Thread starter Arne Garvander
  • Start date Start date
A

Arne Garvander

How can I compute the intersection of two sets of data, if the two sets are
in memory? I am using .Net 2.0.
I need to find the numbers that are found in both collections. Is that
called an intersect?
Maybe this would be an argument for getting Visual Studio 2008 and .Net 3.5.
 
Personally, I would try to avoid O(nm) performance by building a
dictionary from one list, and comparing to the other - that should
give (roughly) O(n+m) [much better].

Something like below.

Marc

using System;
using System.Collections.Generic;
static class Program
{
static void Main()
{
List<int> lhs = new List<int> { 1, 2, 3, 4, 5, 6 },
rhs = new List<int> { 2, 4, 5, 6, 7 };

foreach (int value in Intersect(lhs, rhs))
{
Console.WriteLine(value);
}

}
static IEnumerable<T> Intersect<T>(IList<T> lhs, IList<T> rhs)
{
if(lhs == null) throw new ArgumentNullException("lhs");
if(rhs == null) throw new ArgumentNullException("rhs");

// build the dictionary from the shorter list
if (lhs.Count > rhs.Count)
{
IList<T> tmp = rhs;
rhs = lhs;
lhs = tmp;
}
Dictionary<T, bool> lookup = new Dictionary<T, bool>();
foreach (T item in lhs)
{
if (!lookup.ContainsKey(item)) lookup.Add(item, true);
}
foreach (T item in rhs)
{
if (lookup.ContainsKey(item))
{
lookup.Remove(item); // prevent duplicates
yield return item;

}
}
}
}
 
Back
Top