using System;

using System.Collections.Generic;

using System.Diagnostics;

using System.Linq;

using Medallion.Collections;

​

namespace ConsoleApp2

{

    class Program

    {

        public static (int String, int Frequency)[] RandomStrings(int length, Random random)

        {

            return Enumerable.Range(0, length)

                .Select(_ => random.Next(100_000))

                .GroupBy(s => s)

                .Select(g => (g.Key, g.Count()))

                .ToArray();

        }

​

        static void Main(string[] args)

        {

            var n = 1_000_000;

            var k = 10;

            // Increase this if run locally. .NET Fiddle has a runtime limitation :(

            var repetitions = 4;

​

            RunExperiment("Sort", repetitions: repetitions, length: n, k: k, method: SortEverything, new Random(0));

            RunExperiment("ChaosMonkey", repetitions, n, k, ChaosMonkey, new Random(0));

            RunExperiment("CountingSort", repetitions, n, k, CountingSort, new Random(0));

            RunExperiment("Mo B. Max-Heap", repetitions, n, k, Mo, new Random(0));

            RunExperiment("Mo B. Alternative (Quickselect)", repetitions, n, k, QuickSelect, new Random(0));

            Console.ReadLine();

        }

​

        public static void RunExperiment(string name, int repetitions, int length, int k,

            Func<int, int, (int, int)[], List<int>> method, Random random)

        {

            Stopwatch sw = new Stopwatch();

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

            {

                var randomStrings = RandomStrings(length, random);

                sw.Start();

                method(length, k, randomStrings);

                sw.Stop();

            }

            Console.WriteLine($"Average time for {name}: {((double)sw.ElapsedMilliseconds)/repetitions} ms");

        }

​

        public static List<int> SortEverything(int length, int k, (int String, int Frequency)[] frequencyMap)

        {

            return frequencyMap

                .OrderBy(x => -x.Frequency)

                .Select(x => x.String)

                .Take(k)

                .ToList();

        }

​

        public static List<int> Mo(int length, int k, (int String, int Frequency)[] frequencyMap)

        {

            PriorityQueue<(int String, int Frequency)> queue = 

                new PriorityQueue<(int String, int Frequency)>(frequencyMap, Comparer<(int String, int Frequency)>

                .Create((x, y) => y.Frequency.CompareTo(x.Frequency)));

​

            List<int> result = new List<int>(k);

​

            for (int i = 0; i < k; i++)

            {

                result.Add(queue.Dequeue().String);

            }

​

            return result;

        }

​

        public static List<int> CountingSort(int length, int k, (int String, int Frequency)[] frequencyMap)

        {

            var max = frequencyMap.Max(x => x.Frequency);

            var count = new List<int>[max + 1];

            foreach (var x in frequencyMap)

            {

                if (count[x.Frequency] == null)

                {

                    count[x.Frequency] = new List<int>(x.String);

                }

                else

                {

                    count[x.Frequency].Add(x.String);

                }

            }

​

            List<int> result = new List<int>();

​

            for (int i = count.Length - 1; i >= 0; i--)

            {

                if (count[i] == null) continue;

                result.AddRange(count[i].Take(k - result.Count));

                if (result.Count == k) break;

            }

​

            return result;

        }

​

        public static List<int> ChaosMonkey(int length, int k, (int String, int Frequency)[] frequencyMap)

        {

            var queue = new PriorityQueue<(int String, int Frequency)>(Comparer<(int String, int Frequency)>

                .Create((x, y) => x.Frequency.CompareTo(y.Frequency)));

​

            foreach (var x in frequencyMap)

            {

                queue.Enqueue(x);

                if (queue.Count > k)

                {

                    queue.Dequeue();

                }

            }

​

            return queue

                .Select(x => x.String)

                .ToList();

        }

​

        public static List<int> QuickSelect(int length, int k, (int String, int Frequency)[] frequencyMap)

        {

            QuickSelect(frequencyMap, k);

            return frequencyMap

                .Take(k)

                .Select(x => x.String)

                .ToList();

        }

​

        // Adadpted from https://codereview.stackexchange.com/questions/222889/quick-select-c

        public static void QuickSelect((int String, int Frequency)[] input, int k)

        {

            //keep original array

            int startIndex = 0;

            var endIndex = input.Length - 1;

            var pivotIndex = k;

            Random r = new Random();

            while (endIndex > startIndex)

            {

                pivotIndex = QuickSelectPartition(input, startIndex, endIndex, pivotIndex);

                if (pivotIndex == k)

                {

                    break;

                }

                if (pivotIndex > k)

                {

                    endIndex = pivotIndex - 1;

                }

                else

                {

                    startIndex = pivotIndex + 1;

                }

​

                pivotIndex = r.Next(startIndex, endIndex);

            }

        }

​

        static int QuickSelectPartition((int String, int Frequency)[] array, int startIndex, int endIndex, int pivotIndex)

        {

            int pivotValue = array[pivotIndex].Frequency;

            Swap(pivotIndex, endIndex, array);

            for (int i = startIndex; i < endIndex; i++)

            {

                if (array[i].Frequency.CompareTo(pivotValue) < 0)

                {

                    continue;

                }

                Swap(i, startIndex, array);

                startIndex++;

            }

            Swap(endIndex, startIndex, array);

            return startIndex;

        }

​

        static void Swap(int i, int j, (int String, int Frequency)[] array)

        {

            var temp = array[i];

            array[i] = array[j];

            array[j] = temp;

        }

    }

}

​