在 C# 中获得嵌套 for 循环的性能影响

Question

我有一个字符串数组，总共（100k）。我需要检查之前是否出现过相同的字符串，如果出现，我所要做的就是返回该字符串。我已经使用嵌套 for 循环编写了代码，但不幸的是我的性能很差。为 (string[100K]) 正确处理函数需要 1.9 分钟，而我希望它在几秒钟内完成。

我关心的不是逻辑。我关心的是 LOOP。如何提高循环的效率。

public string StartMatchingProcess(string[]inputArray)
{
    string[] stringArray = inputArray;
    string result = string.Empty;

    for (long i = 0; i < stringArray.Length; i++)
    {
        for (long j = 0; j <= i; j++)
        {
            if(i == j) break;

            if (IsPrefix(stringArray[i], stringArray[j]))
            {
                return stringArray[i];
            }
        }
    }
    Console.WriteLine("GOOD SET");
    return result;
}

public bool IsPrefix(string string1,string string2)
{
    if (AreString1ValuesValid(string1, string2))
    {
        if (string1 == string2.Substring(0, string1.Length))
        {
            Console.WriteLine("BAD SET");
            Console.WriteLine(string1);
            return true;
        }
    }
    else if (AreString2ValuesValid(string1, string2))
    {
        if (string2 == string1.Substring(0, string2.Length))
        {
            Console.WriteLine("BAD SET");
            Console.WriteLine(string1);
            return true;
        }
    }
    return false;
}


public bool AreString1ValuesValid(string string1, string string2)
        => string1.Length <= string2.Length;

public bool AreString2ValuesValid(string string1, string string2)
       => string2.Length <= string1.Length;

Answer 1

对初始数组进行排序，您只能检查邻居：

public string StartMatchingProcess(string[] inputArray) {
  if (null == inputArray)
    throw new ArgumentNullException(nameof(inputArray));

  string[] sorted = inputArray.OrderBy(item => item).ToArray();

  for (int i = 1; i < sorted.Length; ++i) {
    string prior = sorted[i - 1];
    string current = sorted[i];

    if (current.StartsWith(prior))
      return prior;
  }

  return "";
}

因此，您将拥有O(n * log(n))时间复杂度与O(n**2)（初始解决方案）