-2

如果我使用 Lists over Arrays 来解决最长递增子序列，我可以预期的性能损失是多少？

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

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;
    }
4

1 回答 1

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



    }
}
于 2017-10-21T21:07:26.310 回答