我有一个效率低下的方法，如何提高它的效率？

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;
}

- Ant Swift

---

使用一个好的分析器，例如JetBrains的DotTrace（提供免费试用版）。对于（1）来说非常有用。 - Jackson Pope

Answer 1

一个 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;
}

如果可能，我建议进行三项改进:

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);     
}

- Ani

---

+1；这是否意味着allFiles.Except(processedFiles)在其实现中首先创建Map？ - chiccodoro

@chiccodoro：是的，没错。通过反射查看代码，它目前似乎是使用一个名为Set<T>的内部类来实现，而不是HashSet<T>。 - Ani

FileInfo[]和HashSet<string>之间不匹配的原因是processedFiles的来源是一个.txt文件，而allFiles的来源是DirectoryInfo.GetFiles()方法。将FileInfo数组转换为HashSet<string>是否会增加额外的负载？ - Ant Swift

@Anthony：啊，我明白了。嗯，这取决于你需要什么样的效率。只需对数组进行一次遍历即可完成投影，所以除非有问题，否则我会选择它。说实话，在集合中处理FileInfo类型很麻烦，因为它没有重写Equals和GetHashCode方法。因此，如果您不想进行投影，您可能需要编写自己的IEqalityComparer<T>实现，例如这里的一个：http://msdn.microsoft.com/en-us/library/bb546137.aspx。 - Ani

您提出的更改已经满足了我在当前文件数量下所需的性能水平。我现在已将方法更改为仅包含一行代码：return new HashSet<string>(allFiles.Except(processedFiles));，以期在未来提供良好的效率。 - Ant Swift

Answer 2

我会将processedFiles列表转换为HashSet。使用列表，每次调用contains都需要迭代该列表。而HashSet则是O(1)操作。

- Keith Rousseau

Answer 3

你可以使用类似于字典/哈希表的数据结构来显著加快查找过程。即使将传入的列表转换为哈希表一次，然后使用它，速度也比你目前使用的方法要快得多。

- 0xCAFEBABE

Answer 4

只是过于追求严谨而已...

如果你知道这两个列表都是排序的（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分，因为它没有完成泛化和优雅度方面的要求...

- nowttosay

Answer 5

1. 通过文件名对搜索到的数组进行排序
2. 使用 Array.BinarySearch<T>() 对数组进行搜索。这应该能够以 O(logN) 的效率完成。

- Femaref

Answer 6

使用已排序的列表来检查列表是否包含某个元素更快

- remi bourgarel