using System;

using System.Linq;

using System.Collections;

using System.Collections.Generic;

using System.Text;

using System.Diagnostics;

public class Program

{

    public static void Main()

    {

        // https://stackoverflow.com/questions/150750/hashset-vs-list-performance/13089134?noredirect=1#comment76605526_13089134

        test(10, 5, 10, true);

        test(20);

        test(50);

        test(100);

        test(1000);

        test(10, 50, 10, true);

        test(1000, 50);

    }

    // Define other methods and classes here

    static Random r = new Random();

    static string getRandomString(int size) {

        var sb = new StringBuilder();

        for(int i = 0; i < size; i++) sb.Append( (char)('a' + r.Next(0, 25)));

        return sb.ToString();

    }

    static ICollection<string> createTestList<T>(int setSize, int minWordLength = 5, int wordLengthVariance = 10, int previewSize = 0) where T : ICollection<string>, new() {

        var set = new T();

        for(int i = 0; i < setSize; i++) set.Add(getRandomString(r.Next(minWordLength, minWordLength + wordLengthVariance)));

        if(previewSize > 0) set.Take(previewSize).Dump(string.Format("Test size {0} sample {1}", setSize, previewSize));

        return set;

    }

    static List<T> getSearchKeys<T>(ICollection<T> set) {

        return _getSearchKeys(set).ToList();

    }

    static IEnumerable<T> _getSearchKeys<T>(ICollection<T> set) {

        // first

        yield return set.First();

        // early

        yield return set.ElementAt(set.Count / 10);

        // middle

        yield return set.ElementAt(set.Count / 2);

        // late

        yield return set.ElementAt(set.Count / 10 * 9 - 1);

        // last

        yield return set.Last();    

    }

    static void test(int setSize, int minWordLength = 5, int wordLengthVariance = 10, bool preview = false) {

        var list = createTestList<List<string>>(setSize, minWordLength, wordLengthVariance);

        var hashset = new HashSet<string>(list);

        var keys = getSearchKeys(list);

        if(preview) {

            list.Dump("Set");

            keys.Dump("Find");

        }

        // the thing that runs each test 10k times and prints the results, see https://gist.github.com/zaus/8055941

        new Perf {

            { "list, first", n => list.Contains(keys[0]) },

            { "hashset, first", n => hashset.Contains(keys[0]) },

            { "list, early", n => list.Contains(keys[1]) },

            { "hashset, early", n => hashset.Contains(keys[1]) },

            { "list, middle", n => list.Contains(keys[2]) },

            { "hashset, middle", n => hashset.Contains(keys[2]) },

            { "list, late", n => list.Contains(keys[3]) },

            { "hashset, late", n => hashset.Contains(keys[3]) },

            { "list, last", n => list.Contains(keys[4]) },

            { "hashset, last", n => hashset.Contains(keys[4]) },

        }.Vs(string.Format("Comparing set size {0} min word size {1}-{2}", setSize, minWordLength, minWordLength+wordLengthVariance));

    }

}

​

public static class ObjectExtensions {

    public static void Dump<T>(this T o, string title = null) {

        if(title != null) Console.WriteLine("====== {0} ======", title);

        var e = o as IEnumerable;

        if(o is String || e == null) Console.WriteLine(o.ToString());

        else foreach(var i in e) Console.WriteLine(i);

        Console.WriteLine();

    }

    /// <summary> Performance check -- how long do 10K repetitions of the listed tasks take?</summary>

    public static TimeSpan[] Vs(this Dictionary<string, Action<int>> tasks, string reportTitle = null, int repetitions = 10000, bool noShow = false) {

        // tasks.Dump();

        var n = tasks.Count();

        var r = new Dictionary<string, TimeSpan>();

        foreach (var task in tasks)

        {

            r.Add(task.Key, task.Key.Perf(task.Value, repetitions, true));

        }

​

        if (!noShow)

        {

            reportTitle = (reportTitle ?? "Vs");// + ": (" + string.Join(") vs (", tasks.Keys) + ")";

​

            // get the best

            KeyValuePair<string, TimeSpan> minPair;

            var minIndex = indexOfMost(r, (a, b) => a.Value > b.Value, out minPair);

            var min = minPair.Value;

​

            r

                .OrderBy(kv => kv.Value)

                .Select(kv => new {

                    Test = kv.Key,

                    Compare = (kv.Value.TotalMilliseconds / min.TotalMilliseconds).ToString("0.00x"),

                    Elapsed = perfElapsed(kv.Value, repetitions),

                })

                // .ToDictionary(kv => kv.Key, kv => perfElapsed(kv.Value))

                // r.Select(ts => perfElapsed(ts)).Concat(new[] { "winner: " + (hasSubs ? subReportTitles.ElementAt(minIndex) : minIndex + "th") })

                /*

                Tuple.Create(

                    r.Select(ts => perfElapsed(ts))

                    , "winner: " + (hasSubs ? subReportTitles.ElementAt(minIndex) : minIndex + "th")

                    )

                */

                .Dump(reportTitle);

​

            (">> winner: " + tasks.Keys.ElementAt(minIndex)).Dump();

        }

​

        return r.Select(kv => kv.Value).ToArray();

    }

    /// <summary> Performance check -- how long do X repetitions of a task take?</summary>

    public static TimeSpan Perf(this string reportTitle, Action<int> task, int repetitions = 10000, bool noShow = false) {

        // http://stackoverflow.com/questions/28637/is-datetime-now-the-best-way-to-measure-a-functions-performance

        Stopwatch sw = Stopwatch.StartNew();

​

        for (int i = 0; i < repetitions; i++) {

            task(i);

        }

​

        sw.Stop();

        if( !noShow ) perfElapsed(sw.Elapsed, repetitions).Dump(string.IsNullOrEmpty(reportTitle) ? null : string.Format("{0} ({1}x)", reportTitle, repetitions));

        return sw.Elapsed;

    }

    private static string perfElapsed(TimeSpan ts, int repetitions) {

        return string.Format("{0} ticks elapsed ({1} ms) [in {2:0.#}K reps, {3} ms per]", ts.Ticks, ts.TotalMilliseconds, repetitions/1000D, ts.TotalMilliseconds / (double) repetitions);

    }

​

    private static int indexOfMost<T>(IEnumerable<T> list, Func<T, T, bool> compare, out T min) {

        int i = 0, j = 0;

        min = list.First();

        foreach(var s in list) {

            if(compare(min, s)) {

                min = s;

                j = i;

            }

            i++;

        }

        return j;

    }

}

​

​

/// <summary>Silly convenience initializer for creating Vs tasks with a dictionary;

///     can use <code>new Perf { { "task1", n => whatever }, {"task2", n => bar}...}.Vs()</code>

///     <para>see http://stackoverflow.com/a/14000325/1037948 </para>

/// </summary>

/// <remarks>Doesn't automatically call <see cref="Vs"/> because...</remarks>

public class Perf : Dictionary<string, Action<int>> {}

​

/// <summary>Silly convenience initializer for creating Vs tasks with a dictionary that can also provides some output;

///     can use <code>new Perf<T> { { "task1", n => whatever }, {"task2", n => bar}...}.Vs()</code>

///     <para>see http://stackoverflow.com/a/14000325/1037948 </para>

/// <example><code>

///     var p = new Perf{string} {

///         { "int", n => i.GetType().Name },

///         { "double", n => d.GetType().Name },

///         { "string", n => s.GetType().Name },

///         { "object", n => o.GetType().Name },

///         { "struct", n => t.GetType().Name },

///         { "anon", n => a.GetType().Name },

///     }.Vs("gettype");

/// </code></example>

/// </summary>

/// <remarks>Doesn't automatically call <see cref="Vs"/> because...</remarks>

public class Perf<T> : Dictionary<string, Func<int, T>> {}

​

​