ReconstructQueue

ReconstructQueue.cs

#nullable enable

using BenchmarkDotNet.Attributes;
using System;
using System.Collections.Generic;
using System.Linq;

namespace Cr.ReconstructQueue
{
    public class Problem
    {
        public Problem(int[][] queue, string name)
        {
            if (queue == null)
            {
                throw new ArgumentNullException(nameof(queue));
            }

            if (name == null)
            {
                throw new ArgumentNullException(nameof(name));
            }

            Queue = queue;
            Name = name;
        }

        public int[][] Queue { get; }
        public string Name { get; }

        public override string? ToString()
        {
            return Name;
        }
    }

    public class Bench
    {
        public Problem[] Problems { get; set; } = new[] { 100000, 200000, 300000 }.Select(c => new Problem(ProblemGenerator.RandomShuffledQueue(new Random(0), 100, 200, c).ToTacky(), ""+c)).ToArray();

        [ParamsSource(nameof(Problems))]
        public Problem Problem { get; set; }

        [Benchmark]
        public void ReconstructQueueListTacky()
        {
            ReconstructQueueClass.ReconstructQueueListTacky(Problem.Queue);
        }

        [Benchmark]
        public void ReconstructQueueOslTacky()
        {
            ReconstructQueueClass.ReconstructQueueOrderedShrinkListTacky(Problem.Queue);
        }

        [Benchmark]
        public void ReconstructQueueList()
        {
            ProblemGenerator.ToTacky(ReconstructQueueClass.ReconstructQueueList(ProblemGenerator.FromTacky(Problem.Queue)));
        }

        [Benchmark]
        public void ReconstructQueueOsl()
        {
            ProblemGenerator.ToTacky(ReconstructQueueClass.ReconstructQueueOrderedShrinkList(ProblemGenerator.FromTacky(Problem.Queue)));
        }
    }

    /// <summary>
    /// Represents a person in a queue.
    /// </summary>
    public struct Person
    {
        /// <summary>
        /// Creates a new Person with the given height and position relative to other comparably tall people.
        /// </summary>
        public Person(int height, int tallPosition)
        {
            if (height < 0)
                throw new ArgumentOutOfRangeException("Height must be positive", nameof(height));
            if (tallPosition < 0)
                throw new ArgumentOutOfRangeException("Tall-Position must be positive", nameof(tallPosition));

            Height = height;
            TallPosition = tallPosition;
        }

        /// <summary>
        /// The height of the person.
        /// </summary>
        public int Height { get; }

        /// <summary>
        /// The number of people ahead of this person in the queue who are no shorter than this person.
        /// </summary>
        public int TallPosition { get; }

        public override string ToString()
        {
            return $"({Height}, {TallPosition})";
        }

        public int[] ToTacky() => new int[] { Height, TallPosition };
        public static Person FromTacky(int[] tacky)
        {
            if (tacky == null)
                throw new ArgumentNullException(nameof(tacky));
            if (tacky.Length != 2)
                throw new ArgumentException("Tacky representation must have exactly 2 elements", nameof(tacky));

            return new Person(tacky[0], tacky[1]);
        }
    }

    class Program
    {
        static void Main(string[] args)
        {
            BenchmarkDotNet.Running.BenchmarkRunner.Run<Bench>();
            return;

            // test OrderedShrinkList

            //var osl = new OrderedShrinkList<int>(Enumerable.Range(0, 5));

            //while (osl.Count > 1)
            //{
            //    Console.WriteLine(osl.RemoveAt(1));
            //}


            //return;

            var rnd = new Random();

            var testQueue = ProblemGenerator.RandomQueue(rnd, 10, 20, 10);
            var testProblem = testQueue.ToArray();
            ProblemGenerator.Shuffle(rnd, testProblem);

            Console.WriteLine(string.Join(", ", testQueue));
            Console.WriteLine(string.Join(", ", testProblem));

            var sol1 = ReconstructQueueClass.ReconstructQueueList(testProblem);
            Console.WriteLine(string.Join(", ", sol1));

            var sol2 = ReconstructQueueClass.ReconstructQueueOrderedShrinkList(testProblem);
            Console.WriteLine(string.Join(", ", sol2));
        }
    }

    public static class ProblemGenerator
    {
        /// <summary>
        /// Generates a random queue of people of the given length, which is shuffled before being returned.
        /// </summary>
        public static IReadOnlyList<Person> RandomShuffledQueue(Random rnd, int minHeight, int maxHeight, int length)
        {
            var queue = RandomQueue(rnd, minHeight, maxHeight).Take(length).ToList();
            Shuffle(rnd, queue);
            return queue;
        }

        /// <summary>
        /// Generates a random queue of people of the given length.
        /// </summary>
        public static IReadOnlyList<Person> RandomQueue(Random rnd, int minHeight, int maxHeight, int length)
        {
            return RandomQueue(rnd, minHeight, maxHeight).Take(length).ToList();
        }

        /// <summary>
        /// Generates a random queue of people of arbitrary length.
        /// </summary>
        public static IEnumerable<Person> RandomQueue(Random rnd, int minHeight, int maxHeight)
        {
            int[] counts = new int[maxHeight - minHeight];

            while (true)
            {
                int next = rnd.Next(minHeight, maxHeight);
                yield return new Person(next, counts.Skip(next - minHeight).Sum());
                counts[next - minHeight]++;
            }
        }

        /// <summary>
        /// Shuffles the given list.
        /// </summary>
        public static void Shuffle<T>(Random rnd, IList<T> list)
        {
            for (int i = 0; i < list.Count - 1; i++)
            {
                int o = rnd.Next(i, list.Count);
                if (o != i)
                {
                    T t = list[i];
                    list[i] = list[o];
                    list[o] = t;
                }
            }
        }

        public static int[][] ToTacky(this IReadOnlyList<Person> queue)
        {
            return queue.Select(p => p.ToTacky()).ToArray();
        }

        public static Person[] FromTacky(int[][] tackyQueue)
        {
            return tackyQueue.Select(Person.FromTacky).ToArray();
        }
    }

    public class ReconstructQueueClass
    {
        public static int[][] ReconstructQueueListTacky(int[][] people)
        {
            Array.Sort(people, new PairComparer());

            List<int> positions = Enumerable.Range(0, people.Length).ToList();

            int[][] res = new int[people.Length][];
            for (int i = 0; i < people.Length; i++)
            {
                int index = positions[people[i][1]]; //the index in the result is the number of people before you
                res[index] = people[i].ToArray();
                positions.RemoveAt(people[i][1]); // we remove the index from the list so we keep only the un used ones
            }

            return res;
        }

        public static int[][] ReconstructQueueOrderedShrinkListTacky(int[][] people)
        {
            Array.Sort(people, new PairComparer());

            var positions = new OrderedShrinkList<int>(Enumerable.Range(0, people.Length));

            int[][] res = new int[people.Length][];
            for (int i = 0; i < people.Length; i++)
            {
                int index = positions[people[i][1]]; //the index in the result is the number of people before you
                res[index] = people[i].ToArray();
                positions.RemoveAt(people[i][1]); // we remove the index from the list so we keep only the un used ones
            }

            return res;
        }

        public static IReadOnlyList<Person> ReconstructQueueList(Person[] people)
        {
            Array.Sort(people, new PersonComparer());

            List<int> positions = Enumerable.Range(0, people.Length).ToList();

            Person[] res = new Person[people.Length];
            for (int i = 0; i < people.Length; i++)
            {
                int index = positions[people[i].TallPosition]; //the index in the result is the number of people before you
                res[index] = people[i];
                positions.RemoveAt(people[i].TallPosition); // we remove the index from the list so we keep only the un used ones
            }

            return res;
        }

        public static IReadOnlyList<Person> ReconstructQueueOrderedShrinkList(Person[] people)
        {
            Array.Sort(people, new PersonComparer());

            var positions = new OrderedShrinkList<int>(Enumerable.Range(0, people.Length));

            Person[] res = new Person[people.Length];
            for (int i = 0; i < people.Length; i++)
            {
                int index = positions[people[i].TallPosition]; //the index in the result is the number of people before you
                res[index] = people[i];
                positions.RemoveAt(people[i].TallPosition); // we remove the index from the list so we keep only the un used ones
            }

            return res;
        }
    }

    /// <summary>
    /// Orders people by ascending <see cref="Person.Height"/>, and then by descending <see cref="Person.TallPosition"/>.
    /// Fir example, (Height: 5, TallPosition: 2) &lt; (Height: 5, TallPosition: 0) &lt; (Height: 6, TallPosition: 1)
    /// </summary>
    public class PersonComparer : IComparer<Person>
    {
        public int Compare(Person l, Person r)
        {
            if (l.Height != r.Height)
            {
                return l.Height.CompareTo(r.Height);
            }
            else
            {
                return r.TallPosition.CompareTo(l.TallPosition);
            }
        }
    }

    /// <summary>
    /// sort the people, have min height first
    /// for the same height for example 5,0 and 5,2
    /// 5,2 is before 5,0
    /// </summary>
    public class PairComparer : IComparer<int[]>
    {
        public int Compare(int[] x, int[] y)
        {
            if (x[0] != y[0])
            {
                return x[0] - y[0];// we want min value first
            }
            return y[1] - x[1];
        }
    }

    /// <summary>
    /// A simple shrink-only ordered data-structure with log(n) removal by index, where n is the number of elements initially appeared in the data-structure.
    /// <see cref="RemoveAt(int)"/> is not thread-safe, and concurrent operations may produce incorrect results or corrupt the data-structure.
    /// </summary>
    /// <typeparam name="T">the type of element stored in the data structure.</typeparam>
    public class OrderedShrinkList<T>
    {
        /// <summary>
        /// The Data stored in the List.
        /// </summary>
        private T[] Data { get; }

        /// <summary>
        /// Binary tree of 'left' counts.
        /// </summary>
        private int[] Counts { get; }

        /// <summary>
        /// The number of elements in the List.
        /// </summary>
        public int Count { get; private set; }

        /// <summary>
        /// Determines the next power of two great than <paramref name="n"/>.
        /// </summary>
        private static int NextPowerOfTwo(int n)
        {
            int i = 0;
            int p = 1;
            while (p < n)
            {
                i++;
                p *= 2;
            }

            return p;
        }

        /// <summary>
        /// Creates a new <see cref="OrderedShrinkList{T}"/> with elements from <paramref name="data"/>.
        /// </summary>
        public OrderedShrinkList(IEnumerable<T> data)
        {
            if (data is null)
            {
                throw new ArgumentNullException(nameof(data));
            }

            Data = data.ToArray();
            Count = Data.Length;
            int treeSize = NextPowerOfTwo(Data.Length) - 1;
            Counts = new int[treeSize];

            // build count tree
            int subCount = (treeSize + 1) / 2;
            int subLength = 1;
            int i = 0;
            while (subCount > 0)
            {
                for (int j = 0; j < subLength; j++)
                {
                    Counts[i++] = subCount;
                }

                subCount /= 2;
                subLength *= 2;
            }
        }

        /// <summary>
        /// Removes the element at <paramref name="position"/>.
        /// </summary>
        public T RemoveAt(int position)
        {
            var index = ResolveIndex(position);
            var result = Data[index];
            RemoveAtIndex(index);
            return result;
        }

        /// <summary>
        /// Gets the value associated with <paramref name="position"/>.
        /// </summary>
        public T this[int position]
        {
            get
            {
                return Data[ResolveIndex(position)];
            }
        }

        /// <summary>
        /// Removes the element at the <paramref name="index"/>.
        /// </summary>
        private void RemoveAtIndex(int index)
        {
            Data[index] = default!;

            index += Counts.Length;
            while (index > 0)
            {
                int d = index % 2;
                index = (index - 1) / 2;
                Counts[index] -= d;
            }

            Count--;
        }

        /// <summary>
        /// Maps <paramref name="position"/> to an index in <see cref="Data"/>.
        /// </summary>
        private int ResolveIndex(int position)
        {
            if (position < 0 || position >= Count)
                throw new IndexOutOfRangeException($"Position {position} out of range. Must be no greater than or equal to 0, and less than the current Count {Count}.");

            int rest = position;
            int index = 0;

            while (true)
            {
                if (index >= Counts.Length)
                {
                    System.Diagnostics.Debug.Assert(rest == 0);
                    return index - Counts.Length;
                }

                int count = Counts[index];
                if (rest >= count)
                {
                    rest -= count;
                    index = (index + 1) * 2;
                }
                else
                {
                    index = (index + 1) * 2 - 1;
                }
            }
        }
    }
}

Results.md

BenchmarkDotNet=v0.11.5, OS=Windows 10.0.18362
AMD Ryzen 7 3700X, 1 CPU, 16 logical and 8 physical cores
.NET Core SDK=3.0.100
  [Host]     : .NET Core 3.0.0 (CoreCLR 4.700.19.46205, CoreFX 4.700.19.46214), 64bit RyuJIT
  DefaultJob : .NET Core 3.0.0 (CoreCLR 4.700.19.46205, CoreFX 4.700.19.46214), 64bit RyuJIT

Method	Problem	Mean	Error	StdDev
ReconstructQueueListTacky	100000	231.20 ms	1.7189 ms	1.6079 ms
ReconstructQueueOslTacky	100000	30.49 ms	0.5304 ms	0.4962 ms
ReconstructQueueList	100000	237.75 ms	1.4673 ms	1.3725 ms
ReconstructQueueOsl	100000	36.08 ms	0.2129 ms	0.1778 ms
ReconstructQueueListTacky	200000	915.28 ms	5.8013 ms	5.4266 ms
ReconstructQueueOslTacky	200000	68.73 ms	0.5096 ms	0.4767 ms
ReconstructQueueList	200000	919.02 ms	3.4695 ms	3.0757 ms
ReconstructQueueOsl	200000	74.74 ms	0.1429 ms	0.1266 ms
ReconstructQueueListTacky	300000	2,152.91 ms	10.8296 ms	10.1300 ms
ReconstructQueueOslTacky	300000	117.10 ms	2.0030 ms	1.7756 ms
ReconstructQueueList	300000	2,209.69 ms	41.5395 ms	38.8560 ms
ReconstructQueueOsl	300000	118.51 ms	0.6440 ms	0.6024 ms