http://www.reddit.com/r/csharp/comments/30pqzj/performance_competition_find_least_frequent/

perfcomp.cs

using System;
using System.Collections;
using System.Collections.Concurrent;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Threading;
using System.Threading.Tasks;

namespace ConsoleApplication11 {
    class Program {
        static List<int> initial; //generating random array only once and using copies of it later

        static void Main(string[] args) {
            initial = Enumerable.Range(1, 1000).SelectMany(Factors).ToList();
            Console.WriteLine("Initializing JIT");
            TestList<ArraySortImpl>();
            TestList<ToArrayDictionary>();
            TestList<RawDictionary>();
            TestList<Linq>();
            TestList<ParallelDictionary>();
            
            TestArray<ArraySortImpl>();
            TestArray<ToArrayDictionary>();
            TestArray<RawDictionary>();
            TestArray<Linq>();
            TestArray<ParallelDictionary>();
            
            TestCruel<ArraySortImpl>();
            TestCruel<ToArrayDictionary>();
            TestCruel<RawDictionary>();
            TestCruel<Linq>();
            TestCruel<ParallelDictionary>();

            Console.Clear();

            Console.WriteLine("List<int>");
            Console.Write("Sorted: ");
            TestList<ArraySortImpl>();
            Console.Write("Dict:   ");
            TestList<ToArrayDictionary>();
            Console.Write("Dict2:  ");
            TestList<RawDictionary>();
            Console.Write("Linq:   ");
            TestList<Linq>();
            Console.Write("Para:   ");
            TestList<ParallelDictionary>();
            Console.WriteLine();

            Console.WriteLine("int[]");
            Console.Write("Sorted: ");
            TestArray<ArraySortImpl>();
            Console.Write("Dict:   ");
            TestArray<ToArrayDictionary>();
            Console.Write("Dict2:  ");
            TestArray<RawDictionary>();
            Console.Write("Linq:   ");
            TestArray<Linq>();
            Console.Write("Para:   ");
            TestArray<ParallelDictionary>();
            Console.WriteLine();

            Console.WriteLine("Nasty IList<int> impl");
            Console.Write("Sorted: ");
            TestCruel<ArraySortImpl>();
            Console.Write("Dict:   ");
            TestCruel<ToArrayDictionary>();
            Console.Write("Dict2:  ");
            TestCruel<RawDictionary>();
            Console.Write("Linq:   ");
            TestCruel<Linq>();
            Console.Write("Para:   ");
            TestCruel<ParallelDictionary>();
            Console.WriteLine();
            
            Console.ReadKey();
        }

        static IEnumerable<int> Factors(int arg) {
            //really simple prime factorization seive to get a lot of duplicate numbers in our initial array
            if (arg % 2 == 0)
                yield return 2;
            if (arg % 3 == 0)
                yield return 3;
            if (arg % 5 == 0)
                yield return 5;
            if (arg % 7 == 0)
                yield return 7;
            if (arg < 11)
                yield break;

            int max = ((int)Math.Sqrt(arg));
            for (int i = 10; i < max; i += 10) {
                int a = i + 1,
                    b = i + 3,
                    c = i + 7,
                    d = i + 9;
                if (arg % a == 0)
                    yield return a;
                if (arg % b == 0)
                    yield return b;
                if (arg % c == 0)
                    yield return c;
                if (arg % d == 0)
                    yield return d;
            }
        }

        static void TestList<T>() where T: ICodeRush, new() {
            var t = new T();
            var list = new List<int>(initial);

            var timer = new Stopwatch();
            timer.Start();

            t.FindLeastFrequentNumber(list);

            timer.Stop();

            Console.WriteLine("Elapsed: " + timer.Elapsed);
        }

        static void TestArray<T>() where T: ICodeRush, new() {
            var t = new T();
            var arr = initial.ToArray();

            var timer = new Stopwatch();
            timer.Start();

            t.FindLeastFrequentNumber(arr);

            timer.Stop();

            Console.WriteLine("Elapsed: " + timer.Elapsed);
        }

        static void TestCruel<T>() where T: ICodeRush, new() {
            var t = new T();
            var arr = new WayBad(new List<int>(initial));

            var timer = new Stopwatch();
            timer.Start();

            t.FindLeastFrequentNumber(arr);

            timer.Stop();

            Console.WriteLine("Elapsed: " + timer.Elapsed);
        }

    }

    class WayBad : IList<int> {
        readonly List<int> _inner;
        public WayBad(List<int> inner) { _inner = inner; }

        public IEnumerator<int> GetEnumerator() {
            foreach (var i in _inner) {
                Thread.Sleep(1);
                yield return i;
            }
        }

        IEnumerator IEnumerable.GetEnumerator() { return GetEnumerator(); }
        public void Add(int item) { _inner.Add(item); }
        public void Clear() { _inner.Clear(); }
        public bool Contains(int item) { return _inner.Contains(item); }

        public void CopyTo(int[] array, int arrayIndex) {
            for (int index = 0; index < _inner.Count; index++) {
                Thread.Sleep(1);
            }
            _inner.CopyTo(array, arrayIndex);
        }

        public bool Remove(int item) { return _inner.Remove(item); }

        public int Count {
            get {
                Thread.Sleep(1);
                return _inner.Count;
            }
        }

        public bool IsReadOnly { get { return ((ICollection<int>)_inner).IsReadOnly; } }
        public int IndexOf(int item) { return _inner.IndexOf(item); }
        public void Insert(int index, int item) { _inner.Insert(index, item); }
        public void RemoveAt(int index) { _inner.RemoveAt(index); }

        public int this[int index] {
            get {
                Thread.Sleep(1);
                return _inner[index];
            }
            set { _inner[index] = value; }
        }
    }

    public interface ICodeRush {
        int? FindLeastFrequentNumber(IList<int> list);
    }

    public class ArraySortImpl : ICodeRush {
        public int? FindLeastFrequentNumber(IList<int> list) {
            if (list == null || list.Count < 1) return null;
            var arr = list as int[] ?? list.ToArray();
            Array.Sort(arr);
            var sofar = arr[0];
            var prev = arr[0];
            var i = prev;
            var count = 1;
            var mincount = int.MaxValue;
            for (var index = 1; index < arr.Length; index++) {
                i = arr[index];
                if (prev == i) {
                    count++;
                    continue;
                }
                if (count < mincount) {
                    mincount = count;
                    sofar = prev;
                }
                prev = i;
                count = 1;
            }
            return count < mincount ? i : sofar;
        }
    }
    public class ToArrayDictionary : ICodeRush {
        public int? FindLeastFrequentNumber(IList<int> list) {
            if (list == null || list.Count < 1)
                return null;
            var arr = list as int[] ?? list.ToArray();
            var d = new Dictionary<int, int>();
            foreach (var i in arr) {
                int count;
                d.TryGetValue(i, out count);
                d[i] = count + 1;
            }
            int mincount = int.MaxValue;
            int minelem = 0;
            foreach (var i in d) {
                if (i.Value < mincount) {
                    mincount = i.Value;
                    minelem = i.Key;
                }
            }
            return minelem;
        }
    }
    public class RawDictionary : ICodeRush {
        public int? FindLeastFrequentNumber(IList<int> list) {
            if (list == null || list.Count < 1)
                return null;
            var d = new Dictionary<int, int>();
            var max = list.Count;
            for (int index = 0; index < max; index++) {
                var i = list[index];

                int count;
                d.TryGetValue(i, out count);
                d[i] = count + 1;
            }
            int mincount = int.MaxValue;
            int minelem = 0;
            foreach (var i in d) {
                if (i.Value < mincount) {
                    mincount = i.Value;
                    minelem = i.Key;
                }
            }
            return minelem;
        }
    }
    public class Linq : ICodeRush {
        public int? FindLeastFrequentNumber(IList<int> list) {
            if (list == null || list.Count < 1)
                return null;
            return list.GroupBy(k => k).OrderBy(g => g.Count()).First().Key;
        }
    }
    public class ParallelDictionary : ICodeRush {
        public int? FindLeastFrequentNumber(IList<int> list) {
            if (list == null || list.Count < 1)
                return null;
            var d = new ConcurrentDictionary<int, int>();
            Parallel.ForEach(list, new ParallelOptions { MaxDegreeOfParallelism = Environment.ProcessorCount * 2}, i => d.AddOrUpdate(i, iAdd => 1, (iUpdate, iOld) => iOld + 1));
            int mincount = int.MaxValue;
            int minelem = 0;
            foreach (var i in d) {
                if (i.Value < mincount) {
                    mincount = i.Value;
                    minelem = i.Key;
                }
            }
            return minelem;
        }
    }
}