DictionaryVsBinarySearch.cs

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

public static class Tests
{
    private static readonly IDictionary<string, IList<long>> results = new Dictionary<string, IList<long>>();

    public static void Test(Action action, string name)
    {
        var sw = new Stopwatch();
        sw.Start();
        action();
        sw.Stop();
        IList<long> tries;
        if (!results.TryGetValue(name, out tries))
        {
            results[name] = tries = new List<long>();
        }
        tries.Add(sw.ElapsedMilliseconds);
        Console.WriteLine(name + ": " + sw.ElapsedMilliseconds);
    }

    public static void Main()
    {
        var rand = new Random();
        var array = Enumerable.Range(1, 100000)
            .Select(x => new DateTime(rand.Next(1900, 2014), rand.Next(1, 12), rand.Next(1, 28)).ToString("G"))
            .ToArray();

        for (int i = 0; i < 10; i++)
        {
            Test(() => BinarySearch(array), "Binary Search");
            Test(() => Dictionary(array), "Dictionary");
        }

        Console.WriteLine("========");
        var rr = results.Select(r =>
            new
            {
                Name = r.Key,
                Average = r.Value.Average(),
                Min = r.Value.Min(),
                Max = r.Value.Max()
            }).OrderBy(x => x.Average);
        foreach (var result in rr)
        {
            Console.WriteLine(result.Name + ": " + result.Average + ", Min: " + result.Min + ", Max: " + result.Max);
        }
        Console.WriteLine("========");
    }

    private static void Dictionary(string[] array)
    {
        var dictionary = new Dictionary<string, DateTime>();
        foreach (var dt in array)
        {
            Parse(dictionary, dt);

        }
    }

    private static DateTime Parse(Dictionary<string, DateTime> parsedDates, string dt)
    {
        DateTime result;
        if (parsedDates.TryGetValue(dt, out result))
            return result;
        if (DateTime.TryParse(dt, out result))
        {
            parsedDates[dt] = result;
            return result;
        }
        throw new ApplicationException();
    }

    private static void BinarySearch(string[] array)
    {
        var parsedDates = new List<DateTimePair>();
        foreach (var dt in array)
        {
            Parse(parsedDates, dt);
        }
    }

    private static DateTime Parse(List<DateTimePair> parsedDates, string dt)
    {
        var pair = new DateTimePair { Original = dt };
        var position = parsedDates.BinarySearch(pair);
        if (position < 0)
        {
            // В кеше нет такой даты - будем парсить  
            DateTime res;
            if (DateTime.TryParse(dt, out res))
            {
                pair.Parsed = res;
                parsedDates.Insert(~position, pair);
                return res;
            }
            else
            {
                throw new ApplicationException();
                // Разобрать дату не смогли  
            }
        }
        else
        {
            // В кеше дата найдена - берем оттуда  
            return parsedDates[position].Parsed;
        }
    }

    public class DateTimePair : IComparable<DateTimePair>
    {
        //...  
        public int CompareTo(DateTimePair other)
        {
            return Original.CompareTo(other.Original);
        }

        public string Original { get; set; }
        public DateTime Parsed { get; set; }
    }
}