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

Question

我有一个字符串数组，一共（100k）。我需要检查之前是否出现过相同的字符串，如果出现，我所要做的就是 return 该字符串。我已经使用嵌套 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

如果您只是想确定您的数组是否有重复的字符串值，请考虑使用 LINQ 来计算出现的次数。

        string[] arrayTest = new string[] { "hello", "hello", "world"};
        string myValue = "hello";
        var stringCount = arrayTest.Where(n => n == myValue).Count();
        if (stringCount > 1) return myValue;

在上面，我们检查"hello"是否不止一次在数组中，如果是，我们return它。

Answer 2

排序初始数组，你可以检查neighbors只：

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)（初始解决方案）

Answer 3

为这个任务使用嵌套循环真的是个坏主意，因为你的答案 O(n*n) 很复杂，需要为 100k 数组调用 Substring() 10.000.000.000 次。

字符串有特定的结构。例如，您可以使用 Trie：

public string StartMatchingProcess(string[] inputArray)
{
    var trie = new Trie();
    foreach(var w in inputArray)
        trie.AddWord(w);
    foreach(var w in inputArray)
        if(trie.HasPrefix(w) || trie.HasWord(w)
            return w;

    return string.Empty;
}

Answer 4

这是一个使用 linq 的完整解决方案。

public class Node
    {
        public char letter { get; }
        public int Index { get; set; }
        public List<Node> ChildList { get; set; } = new List<Node>();

        public Node(char item, int index)
        {
            Index = index;
            letter = item;
        }
    }       

    public class NoPrefixSet
    {
        public Dictionary<char, Node> ParentNode { get; set; } = new Dictionary<char, Node>();

        public string GenerateNodes(string[] inputArray)
        {
            for (int i = 0; i < inputArray.Length; i++)
            {
                if (IsWordPrefix(inputArray[i]))
                {
                    Console.WriteLine("BAD SET");
                    Console.WriteLine(inputArray[i]);
                    return inputArray[i];

                }
            }
            Console.WriteLine("Good Set");
            return "Good Set";
        }

        private void InsertNodeInParent(char item)
            => ParentNode.Add(item, new Node(item, 0));

        private bool IsWordPrefix(string word)
        {
            //Check parent
            Node parentNode = null;
            bool hasNotInserted = false;
            int similarCounter = 0;
            if (!ParentNode.Any(a => a.Key == word[0]))
            {
                InsertNodeInParent(word[0]);
            }
            parentNode = ParentNode.Where(a => a.Key == word[0]).FirstOrDefault().Value;

            for (int letterIndex = 0; letterIndex < word.Length; letterIndex++)
            {
                if (!parentNode.ChildList.Any(a => a.letter == word[letterIndex]))
                {
                    parentNode.ChildList.Add(new Node(word[letterIndex], letterIndex));
                }
                else 
                {
                    if (!parentNode.ChildList.Where(a => a.letter == word[letterIndex]).First().ChildList.Any() || word.Length == letterIndex+1)
                    {
                        if (similarCounter == letterIndex)
                            return hasNotInserted = true;
                    }
                    similarCounter++;

                }
                parentNode = parentNode.ChildList.Where(a => a.letter == word[letterIndex] && a.Index == letterIndex).First();
            }

            return hasNotInserted;
        }

        public void ReadInput()
        {
            long data = Convert.ToInt64(Console.ReadLine());
            string[] stringArray = new string[data];
            for (long i = 0; i < data; i++)
            {
                stringArray[i] = Console.ReadLine();
            }
            GenerateNodes(stringArray);
        }
    }

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

getting a performance hit for nested for loop in C#

c#

for-loop

optimization

prefix

trie