C# Collections vs Arrays: Longest Increasing Subsequence Benefits

Question

What's the performance penalty that I can expect if I'm using Lists over Arrays to solve the Longest Increasing Subsequence?

Will the dynamic nature of Lists improve average performance because we're not dealing with sizes we won't actually use?

PS: Any tips on improving performance while still maintaining some readability?

   public static int Run(int[] nums)
    {
        var length = nums.Length;

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

        candidates.Add(new List<int> { nums[0] });

        for (int i = 1; i < length; i++)
        {
            var valueFromArray = nums[i];

            var potentialReplacements = candidates.Where(t => t[t.Count-1] > valueFromArray);

            foreach (var collection in potentialReplacements)
            {
                var collectionCount = collection.Count;

                if ((collection.Count > 1 && collection[collectionCount - 2] < valueFromArray) || (collectionCount == 1))
                {
                    collection.RemoveAt(collectionCount - 1);
                    collection.Add(valueFromArray);
                }
            }

            if (!candidates.Any(t => t[t.Count - 1] >= valueFromArray))
            {
                var newList = new List<int>();

                foreach(var value in candidates[candidates.Count - 1])
                {
                    newList.Add(value);
                }

                newList.Add(nums[i]);
                candidates.Add(newList);
            }
        }

        return candidates[candidates.Count - 1].Count;
    }

Answer 1

Depending on the solution the results may vary. Arrays are faster when compared with lists of the same size. How more fast? Lets take a look at the c# solution below. This is a simple O(n^2) solution. I coded a version with arrays only and another one with lists only. I'm running it 1000 times and recording the values for both. Then I just print the average improvement of the array version over the list version. I'm getting over 50% improvement on my computer. Notice that this solution uses arrays and lists with the same sizes always. Than means I never created an array bigger than the size the lists are gonna grow to in the lists version. Once you start creating arrays with a Max size that may not be filled the comparison stops to be fair. C# code below:

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

namespace hashExample
{
    class Program
    {
        static int RunArray(int[] array)
        {
            int[] dp = new int[array.Length];
            dp[0] = 1;
            for (int i = 1; i < array.Length; i++)
            {
                dp[i] = 1;
                for (int j = 0; j < i; j++)
                    if (array[i] > array[j] && dp[i] < dp[j] + 1)
                            dp[i] = dp[j] + 1;
            }
            return dp.Max();
        }

        static int RunList(List<int> array)
        {
            List<int> dp = new List<int>(array.Count);
            dp.Add(1);
            for (int i = 1; i < array.Count; i++)
            {
                dp.Add(1);
                for (int j = 0; j < i; j++)
                    if (array[i] > array[j] && dp[i] < dp[j] + 1)
                        dp[i] = dp[j] + 1;
            }
            return dp.Max();
        }

        static void Main(string[] args)
        {
            int arrayLen = 1000;
            Random r = new Random();
            List<double> values = new List<double>();
            Stopwatch clock = new Stopwatch();
            Console.WriteLine("Running...");
            for (int i = 0; i < 100; i++)
            {
                List<int> list = new List<int>();
                int[] array = new int[arrayLen];
                for (int j = 0; j < arrayLen;j++)
                {
                    int e = r.Next();
                    array[j] = e;
                    list.Add(e);
                }

                clock.Restart();
                RunArray(array);
                clock.Stop();
                double timeArray = clock.ElapsedMilliseconds;
                clock.Restart();
                RunList(list);
                clock.Stop();
                double timeList = clock.ElapsedMilliseconds;
                //Console.WriteLine(Math.Round(timeArray/timeList*100,2) + "%");
                values.Add(timeArray / timeList);
            }
            Console.WriteLine("Arrays are " + Math.Round(values.Average()*100,1) + "% faster");
            Console.WriteLine("Done");
        }



    }
}