我有一个性能不佳的方法，如何提高其效率？

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

List 的 Contains 方法以线性时间运行，因为它可能必须枚举整个列表才能证明某个项目存在/不存在。我建议您使用 HashSet 或类似的东西。 HashSet的 < code>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 作为参数。这样，您就不必每次都重建集合。
2. 尽量不要以这种方式混合和匹配相同实体的不同表示（字符串和FileInfo）。选择一个并使用它。
3. 您可能还想考虑使用 HashSet.ExceptWith 方法，而不是自己进行循环。请记住，这会改变集合。

如果您可以使用 LINQ，并且您有能力在每次调用时建立一个集合，那么还有另一种方法：

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

Answer 2

我会尝试将processedFiles列表转换为HashSet。对于列表，每次调用 contains 时都需要迭代列表。 HashSet 是一个 O(1) 操作。

Answer 3

您可以使用类似字典/hastable 的类来显着加快查找过程。即使将传入的列表转换为哈希表一次，然后使用该列表也会比您正在使用的快得多。

Answer 4

1. 按文件名对搜索到的数组进行排序，
2. 使用 Array.BinarySearch() 来搜索数组。这应该以大约 O(logN) 的效率出现。

Answer 5

使用排序列表检查列表是否包含元素更快

Answer 6

只是过于迂腐......

如果您知道两个列表都已排序（FileInfo 列表通常已预先排序，因此这种方法可能适用于您），那么您可以实现真正的线性性能，而无需花费时间和内存开销哈希集。哈希集构建仍然需要线性时间来构建，因此复杂度更接近 O(n + m)；在您的情况下，哈希集必须在内部为最多 250k 个字符串分配额外的对象引用，这将在 GC 方面产生成本。

像这种半生不熟的概括可能会有所帮助：

public static IEnumerable<string> GetMismatches(IList<string> fileNames, IList<string> processedFileNames, StringComparer comparer)
    {
        var filesIndex = 0;
        var procFilesIndex = 0;

        while (filesIndex < fileNames.Count)
        {
            if (procFilesIndex >= processedFileNames.Count)
            {
                yield return files[filesIndex++];
            }
            else
            {
                var rc = comparer.Compare(fileNames[filesIndex], processedFileNames[procFilesIndex]);
                if (rc != 0)
                {
                    if (rc < 0)
                    {
                        yield return files[filesIndex++];
                    }
                    else
                    {
                        procFilesIndex++;
                    }
                }
                else
                {
                    filesIndex++;
                    procFilesIndex++;
                }
            }
        }

        yield break;
    }

我强烈同意 Ani 的观点，即坚持通用或规范类型确实是一件非常好的事情。
但我会给我的-1表示未完成的概括，-1表示优雅......