求大佬帮忙解释一下C#代码的性能问题

Question

我是一名 C# 开发人员，我正在 LeetCode 上训练我的编码和算法技能。
现在我正在处理问题 5：longest palindromic substring.
我希望有人能解释原因。
我对这个问题的版本 1 的解决方案是：

public string LongestPalindrome(string s)
{
    // Step 0: Handles invalid or special cases.
    if (string.IsNullOrWhiteSpace(s) ||
        s.Length == 1 ||
        s.Distinct().Count() == 1 ||
        s.Reverse().SequenceEqual(s))
        {
            return s;
        }

        if (s.Length == 2)
        {
            return s.First().Equals(s.Last()) ? s : s.First().ToString();
        }

        if (s.Distinct().Count() == s.Length)
        {
            return s.First().ToString();
        }

        // Step 1: Handles normal cases.
        var longestPalindromeSubstring = string.Empty;

        for (var index = 0; index < s.Length && s.Length - index > longestPalindromeSubstring.Length; index++)
        {
            var currentChar = s[index];
            var currentCharLastIndex = s.LastIndexOf(currentChar);

            if (index == currentCharLastIndex)
            {
                if (!string.IsNullOrWhiteSpace(longestPalindromeSubstring) ||
                        longestPalindromeSubstring.Length > 1)
                {
                    continue;
                }

                longestPalindromeSubstring = currentChar.ToString();
            }

            var currentCharIndexes = new Stack<int>();

            for (var nextIndex = index + 1; nextIndex <= currentCharLastIndex; nextIndex++)
            {
                if (s[nextIndex] == currentChar)
                {
                    currentCharIndexes.Push(nextIndex);
                }
            }

            while (currentCharIndexes.Any())
            {
                var relatedIndex = currentCharIndexes.Pop();
                var possibleStr = s.Substring(index, relatedIndex - index + 1);
                var reversedPossibleStr = new string(possibleStr.Reverse().ToArray());

                if (!possibleStr.Equals(reversedPossibleStr) ||
                    possibleStr.Length < longestPalindromeSubstring.Length ||
                    possibleStr.Equals(longestPalindromeSubstring))
                {
                    continue;
                }

                longestPalindromeSubstring = possibleStr;
            }
        }

        return longestPalindromeSubstring;
    }

但是上面的解决方案未能通过 LeetCode 验证，因为问题：超出时间限制。
然后我只是做了一个小更新，解决方案version 2通过了，改变的部分只是添加了ToCharArray() 调用 Reverse() 方法之前的方法：

var reversedPossibleStr = new string(possibleStr.ToCharArray().Reverse().ToArray());

if (!possibleStr.Equals(reversedPossibleStr) ||
     possibleStr.Length < longestPalindromeSubstring.Length ||
     possibleStr.Equals(longestPalindromeSubstring))
{
     continue;
}
…………

但我不确定它为什么可以工作，我只是猜测数组中的数据将按顺序内存排列space，这可能有助于提高性能，谁能解释一下更多详情。提前谢谢你。

Answer 1

Reverse 方法使用EnumerableHelpers.ToArray to fetch the count of the input enumerable. If the enumerable doesn't implement ICollection<T> interface, it will use a list-like approach 创建一个数组，该数组将多次扩展该数组。不幸的是 string 没有实现 ICollection<char>，虽然它知道它包含多少个字符，所以 string.Reverse() 比 string.ToCharArray().Reverse().

慢

求大佬帮忙解释一下C#代码的性能问题

Ask someone's help to explain the performance issue of C# code

c#

algorithm