c# - 我有一个性能不佳的方法，我该如何提高它的效率？

Question

我有一个简单的方法来将 FileInfo 对象数组与文件名列表进行比较，以检查哪些文件已经被处理过。然后返回未处理的列表。

此方法的循环迭代了大约 250,000 个 FileInfo 对象。这花费了大量的时间来竞争。

效率低下显然是对 processedFiles 集合的 Contains 方法调用。

首先，我如何检查以确保我对原因的怀疑是真实的，其次，我如何改进方法以加快该过程？

public static List<FileInfo> GetUnprocessedFiles(FileInfo[] allFiles, List<string> processedFiles)
{
List<FileInfo> unprocessedFiles = new List<FileInfo>();
foreach (FileInfo fileInfo in allFiles)
{
    if (!processedFiles.Contains(fileInfo.Name))
    {
        unprocessedFiles.Add(fileInfo);
    }
    }
    return unprocessedFiles;
}

Answer 1

A List<T>的 Contains方法以线性时间运行，因为它可能必须枚举整个列表以证明项目的存在/不存在。我建议你使用 HashSet<string>或类似的代替。 HashSet<T> 的 Contains方法旨在以常量 O(1) 运行时间，即它不应该取决于集合中的项目数量。

这个小改动应该可以使整个方法在线性时间内运行:

public static List<FileInfo> GetUnprocessedFiles(FileInfo[] allFiles, 
                                         List<string> processedFiles)
{
   List<FileInfo> unprocessedFiles = new List<FileInfo>();
   HashSet<string> processedFileSet = new HashSet<string>(processedFiles);

   foreach (FileInfo fileInfo in allFiles)
   {
       if (!processedFileSet.Contains(fileInfo.Name))
       {
           unprocessedFiles.Add(fileInfo);
       }
    }

   return unprocessedFiles;
}

如果可能的话，我会建议 3 项改进:

1. 为了额外效率，在源中将处理过的文件存储在一个集合中，这样这个方法需要一个ISet<T>作为参数。这样，您就不必每次都重建集合。
2. 尽量不要以这种方式混合和匹配相同 实体(string 和FileInfo)的不同表示。选择一个并使用它。
3. 您可能还想考虑 HashSet<T>.ExceptWith方法而不是自己做循环。请记住，这会改变集合。

如果您可以使用 LINQ，并且可以负担得起在每次调用时建立一个集合，那么还有另一种方法:

public static IEnumerable<string> GetUnprocessedFiles
 (IEnumerable<string> allFiles, IEnumerable<string> processedFiles)
{
  // null-checks here
  return allFiles.Except(processedFiles);     
}