c# - C# 中 foreach() 的复杂性。网

Question

friend 们，我正在使用 C# 。 NET，我需要从文件中读取 800 万行并对其进行计算。当我在 C 语言中执行相同的操作时，需要时间，但不会太多，而在 C# 中，它会在我下面提到的循环中达到非常非常高的时间复杂度。 foreach() 的复杂度是否很高？两者之间差异的原因可能是什么？

foreach(string currLine in file.lines)
{
    Tuple tpl = new Tuple(currLine,file.keyLength);
    Console.WriteLine(file.lines.IndexOf(currLine));

    if(tpl.isWeakKey(B)==true)
    {
        int nextKey=tpl.findNextKey(B);

        if (differentKeys.ContainsKey(nextKey))
        {
            differentKeys[nextKey] = differentKeys[nextKey]+1;
        }
        else
        {
            differentKeys[nextKey] = 1;
        }
    }
}

Answer 1

您在循环内调用IndexOf方法来获取当前索引。该方法的复杂度为 O(n)，这意味着整个循环的复杂度为 O(n²)。

如果您只使用索引并手动递增它，您将得到更类似于 C 代码的内容。

另一种更 C# 风格的方法(据我所知)是使用 LINQ 为您提供索引:

foreach(string currLine in file.lines.Select((Text, Index) => new { Text, Index)))
{
    Tuple tpl = new Tuple(currLine.Text,file.keyLength);
    Console.WriteLine(currLine.Index);

    // ** No need to compare with boolean. if, already expect a boolean.
    if(tpl.isWeakKey(B))
    {
        int nextKey=tpl.findNextKey(B);

        if (differentKeys.ContainsKey(nextKey))
        {
            differentKeys[nextKey] = differentKeys[nextKey]+1;
        }
        else
        {
            differentKeys[nextKey] = 1;
        }
    }
}