IntersectOptimization.cs

using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;


namespace ConsoleApplication {
   class Program {


      static void Main() {
        Profile<object>(1000, 1000, 800,   10000);
        Profile<object>(1000, 1000, 200,   10000);
        Profile<object>(1000, 100,  50,    10000);
        Profile<object>(100,  1000, 50,    10000);
      }

      static void Profile<T>(int nbElemHashsetA, int nbElemB, int intersectionSize, int nbLoop) where T : class, new() {
         Debug.Assert(intersectionSize <= nbElemHashsetA);
         Debug.Assert(intersectionSize <= nbElemB);
         var seqIntersection = new T[intersectionSize];
         for (var i = 0; i < intersectionSize; i++) { seqIntersection[i] = new T(); }
         
         var hashsetA = new HashSet<T>(seqIntersection);
         for (var i = intersectionSize; i < nbElemHashsetA; i++) { hashsetA.Add(new T()); }

         var seqB = new T[nbElemB];
         Array.Copy(seqIntersection, seqB,intersectionSize);
         for (var i = intersectionSize; i < nbElemB; i++) { seqB[i] = new T(); }
         seqB.Shuffle();


         var stopwatch1 = new Stopwatch();
         stopwatch1.Start();
         for (var i = 0; i < nbLoop; i++) {
            var seqIntersection1 = seqB.Intersect(hashsetA);
            var intersectionSize1 = seqIntersection1.Count(); // <-- provoke iteration
         }
         stopwatch1.Stop();

         var stopwatch2 = new Stopwatch();
         stopwatch2.Start();
         for (var i = 0; i < nbLoop; i++) {
            var seqIntersection2 = seqB.MyIntersect(hashsetA);
            var intersectionSize2 = seqIntersection2.Count(); // <-- provoke iteration
         }
         stopwatch2.Stop();

         Console.WriteLine("nbElemHashsetA=" + nbElemHashsetA + "  nbElemB=" + nbElemB + "  intersectionSize=" + intersectionSize + "  nbLoop=" + nbLoop);
         Console.WriteLine("  Default Intersect: " + new TimeSpan(stopwatch1.ElapsedTicks).ToString());
         Console.WriteLine("  Hashset Intersect: " + new TimeSpan(stopwatch2.ElapsedTicks).ToString());
         Console.WriteLine("  Gain : " + (int)(((float)stopwatch1.ElapsedTicks / stopwatch2.ElapsedTicks) * 100) + "%");
      }
   }


   static class MyExtensionMethods {
      internal static IEnumerable<T> MyIntersect<T>(this IEnumerable<T> first, IEnumerable<T> second) {
         Debug.Assert(first != null);
         Debug.Assert(second != null);
         var firstHashset = first as HashSet<T>;
         var secondHashset = second as HashSet<T>;
         if (firstHashset != null && secondHashset != null) {
            return (firstHashset.Count > secondHashset.Count)
                      ? firstHashset.Intersect(second)
                      : secondHashset.Intersect(first);
         }
         if (firstHashset != null) { return firstHashset.Intersect(second); }
         if (secondHashset != null) { return secondHashset.Intersect(first); }
         return first.Intersect(second);
      }

      static IEnumerable<T> Intersect<T>(this HashSet<T> firstHashset, IEnumerable<T> second) {
         Debug.Assert(firstHashset != null);
         Debug.Assert(second != null);
         foreach (var tmp in second) {
            if (firstHashset.Contains(tmp)) { yield return tmp; }
         }
      }


      internal static void Shuffle<T>(this T[] array) where T : class, new() {
         Debug.Assert(array != null);
         var length = array.Length;
         Debug.Assert(length > 0);
         var random = new Random((int)DateTime.Now.Ticks);
         for (int i = 0; i < length; i++) {
            var indexA = random.Next(0, length - 1);
            var indexB = random.Next(0, length - 1);
            if (indexA == indexB) { continue; }
            var tmp = array[indexA];
            array[indexA] = array[indexB];
            array[indexB] = tmp;
         }
      } 
   }
}