C# 集合与数组：最长递增子序列的优势

Question

如果我使用列表而不是数组来求解最长递增子序列，预计会有什么性能损失？

列表的动态特性是否会提高平均性能，因为我们不处理我们实际上不会使用的大小？

PS：关于在提高性能的同时仍保持一定可读性的任何提示？

   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

根据解决方案，结果可能会有所不同。与相同大小的列表相比，数组更快。多快？让我们看看下面的 c# 解决方案。这是一个简单的 O(n^2) 解决方案。我编写了一个仅包含数组的版本和另一个仅包含列表的版本。我运行它 1000 次并记录两者的值。然后我只打印数组版本相对于列表版本的平均改进。我的计算机性能提高了 50% 以上。请注意，此解决方案始终使用相同大小的数组和列表。这意味着我从来没有创建一个大于列表版本中列表将增长到的大小的数组。一旦您开始创建可能无法填充的最大大小的数组，比较就会停止以保持公平。下面的 C# 代码：

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");
        }



    }
}

C# 集合与数组：最长递增子序列的优势

C# Collections vs Arrays: Longest Increasing Subsequence Benefits

c#

algorithm

generic-collections

lis