using System;

using System.Collections.Generic;

using System.Diagnostics;

using System.Linq;

using System.Runtime.InteropServices;

using static MoreLinq.Extensions.PartialSortExtension;

​

public static class Program

{

    public static void Main()

    {

        Console.WriteLine(RuntimeInformation.FrameworkDescription);

        Random random = new Random();

        const int count = 2_000_000;

        const int k = 100;

        double[] valuesArray = Enumerable.Range(1, count).Select(_ => random.NextDouble()).ToArray();

        IEnumerable<double> values = valuesArray.HideIdentity();

​

        {

            // Warmup

            var comparer = new MyComparer<double>();

            var fewValues = values.Take(1000);

            fewValues.OrderByDescending(x => x, comparer).Take(k).Sum();

            fewValues.PartialSort(k, comparer, MoreLinq.OrderByDirection.Descending).Sum();

            fewValues.TopN(k, comparer).Sum();

        }

​

        Console.WriteLine("Extract the {0:#,0} maximum elements from {1:#,0} random values, and calculate the sum.", k, values.Count());

        Console.WriteLine();

        const string format = "Duration: {0,5:#,0} msec, Comparisons: {1,10:#,0}, Sum: {2:#,0.000000}";

        {

            var comparer = new MyComparer<double>();

            var stopwatch = Stopwatch.StartNew();

            var sum = values.OrderByDescending(x => x, comparer).Take(k).Sum();

            stopwatch.Stop();

            Console.WriteLine("OrderByDescending+Take              " + format,

                stopwatch.ElapsedMilliseconds, comparer.Counter, sum);

        }

        {

            var comparer = new MyComparer<double>();

            var stopwatch = Stopwatch.StartNew();

            var sum = values.OrderByDescending(x => x, comparer).HideIdentity().Take(k).Sum();

            stopwatch.Stop();

            Console.WriteLine("OrderByDescending+HideIdentity+Take " + format,

                stopwatch.ElapsedMilliseconds, comparer.Counter, sum);

        }

        {

            var comparer = new MyComparer<double>();

            var stopwatch = Stopwatch.StartNew();

            var sum = values.PartialSort(k, comparer, MoreLinq.OrderByDirection.Descending).Sum();

            stopwatch.Stop();

            Console.WriteLine("MoreLinq.PartialSort                " + format,

                stopwatch.ElapsedMilliseconds, comparer.Counter, sum);

        }

        {

            var comparer = new MyComparer<double>();

            var stopwatch = Stopwatch.StartNew();

            var sum = values.TopN(k, comparer).Sum();

            stopwatch.Stop();

            Console.WriteLine("TopN                                " + format,

                stopwatch.ElapsedMilliseconds, comparer.Counter, sum);

        }

    }

​

    static IEnumerable<T> HideIdentity<T>(this IEnumerable<T> source)

    {

        foreach (var item in source) yield return item;

    }

​

    class MyComparer<T> : IComparer<T>

    {

        public long Counter = 0;

        public int Compare(T x, T y)

        {

            Counter++;

            return Comparer<T>.Default.Compare(x, y);

        }

    }

​

    /// <summary>

    /// Selects the top N elements from the source sequence. The selected elements

    /// are returned in descending order.

    /// </summary>

    public static IEnumerable<T> TopN<T>(this IEnumerable<T> source, int n,

        IComparer<T> comparer = default)

    {

        ArgumentNullException.ThrowIfNull(source);

        if (n < 1) throw new ArgumentOutOfRangeException(nameof(n));

        comparer ??= Comparer<T>.Default;

        PriorityQueue<bool, T> top = new(comparer);

        foreach (var item in source)

        {

            if (top.Count < n)

                top.Enqueue(default, item);

            else

                top.EnqueueDequeue(default, item);

        }

        List<T> topList = new(top.Count);

        while (top.TryDequeue(out _, out var item)) topList.Add(item);

        for (int i = topList.Count - 1; i >= 0; i--) yield return topList[i];

    }

}

​