take ii!

take2.cs

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

namespace ConsoleApp95
{
    class Node
    {
        public Node prev;
        public Node next;

        public int value;
    }

    class Program
    {
        static IEnumerable<int> DataSetRandomSeed42()
        {
            var r = new Random(42);
            for (var i = 0; i < 5_000_000; ++i)
                yield return r.Next();
        }

        static IEnumerable<int> DataSetAscending()
        {
            for (var i = 0; i < 5_000_000; ++i)
                yield return i;
        }

        static IEnumerable<int> DataSetDescending()
        {
            for (var i = 0; i < 5_000_000; ++i)
                yield return -i;
        }

        static IEnumerable<int> DataSetAdverserial()
        {
            for (var i = 0; i < 48; ++i)
                yield return int.MaxValue + i;

            for (var i = 48; i < 5_000_000; ++i)
                yield return -i;
        }

        static void Main(string[] args)
        {
            Console.WriteLine($"Environment.Is64BitProcess={Environment.Is64BitProcess}");
            Console.WriteLine($"Environment.Version={Environment.Version}");
            Console.WriteLine($"Environment.OSVersion={Environment.OSVersion}");

#if true
            var sw = Stopwatch.StartNew();
            for (var i = 0; i < 10; ++i)
            {
                sw.Restart();
                var sortedTake = SortedTake(DataSetAdverserial(), 50);
                Console.WriteLine(sw.ElapsedMilliseconds);
            }
#else


            for (var i = 0; i < 5; ++i)
            {
                RunTest(DataSetRandomSeed42, nameof(DataSetRandomSeed42));
                RunTest(DataSetAscending, nameof(DataSetAscending));
                RunTest(DataSetDescending, nameof(DataSetDescending));
                RunTest(DataSetAdverserial, nameof(DataSetAdverserial));

                Console.WriteLine();
            }
#endif
        }

        private static void RunTest(Func<IEnumerable<int>> getData, string description)
        {
            var data = getData();

            var sw = Stopwatch.StartNew();

            var takeCount = 50;

            sw.Restart();
            var sortedTake = SortedTake(data, takeCount);
            var sortedTakeTime = sw.ElapsedMilliseconds;

            sw.Restart();
            var linqTake =
                data
                .OrderBy(i => i)
                .Select(i => i)
                .Take(takeCount)
                .ToList();
            var linqTakeTime = sw.ElapsedMilliseconds;

            if (!sortedTake.SequenceEqual(linqTake))
                throw new Exception("Algo mismatch");

            System.Console.WriteLine($"{description}\t{sortedTakeTime}\t{linqTakeTime}\t({(float)sortedTakeTime / linqTakeTime * 100:0.00}%)");
        }

        private static IList<int> SortedTake(IEnumerable<int> data, int takeCount)
        {
            var enumerator = data.GetEnumerator();

            var initialValues = new List<int>();
            while (enumerator.MoveNext() && initialValues.Count < takeCount)
                initialValues.Add(enumerator.Current);
            initialValues.Sort();
            if (initialValues.Count < takeCount)
                return initialValues;

            var indexes = new List<Node>();
            var indexerIndex = takeCount;
            Node lastNode = null;
            for (var i = takeCount - 1; i >= 0; --i)
            {
                var node = new Node { prev = lastNode, value = initialValues[i] };
                if (lastNode != null)
                    lastNode.next = node;
                if (indexerIndex > i)
                {
                    indexes.Add(node);
                    indexerIndex = (int)(indexerIndex / 1.55);
                }
                lastNode = node;
            }

            while (enumerator.MoveNext())
            {
                var value = enumerator.Current;
                var n = 0;
                for (; n < indexes.Count; ++n)
                {
                    if (value >= indexes[n].value)
                        break;
                }
                if (n == 0)
                    continue;
                else
                {
                    var insert = indexes[0];
                    insert.value = value;
                    if (value >= insert.next.value)
                        continue;

                    indexes[0] = insert.next;
                    insert.next.prev = null;

                    if (n == indexes.Count)
                    {
                        var tail = indexes[indexes.Count - 1];
                        tail.next = insert;

                        insert.next = null;
                        insert.prev = tail;
                    }
                    else
                    {
                        var search = indexes[n];
                        while (value >= search.value)
                            search = search.prev;

                        insert.next = search.next;
                        insert.next.prev = insert;
                        insert.prev = search;

                        search.next = insert;
                    }
                }

                for (--n; n > 0; --n)
                    indexes[n] = indexes[n].next;
            }

            var results = new List<int>();
            var nn = indexes[indexes.Count - 1];
            while (nn != null)
            {
                results.Add(nn.value);
                nn = nn.prev;
            }

            return results;
        }
    }
}