功能超时用于大型列表(C#中的LINQ查询)

Question

我使用以下查询

var queryList1Only = (from file in list1
                                  select file).Except(list2, myFileCompare);

同时myFileCompare根据名称和长度比较2个文件.

如果list1和list2很小(在我测试时说100个文件),查询返回结果,然后我将list1增加到30,000个文件,list2增加到20,000个文件,查询现在说"Function Evaluation Timed Out".

我在网上搜索,发现调试可能会导致它,所以我删除了所有断点并运行代码,现在程序只是冻结,没有任何输出,queryList1Only我试图打印出来检查它.

编辑:这是myFileCompare的代码

class FileCompare : System.Collections.Generic.IEqualityComparer<System.IO.FileInfo>
    {

        public FileCompare() { }

        public bool Equals(System.IO.FileInfo f1, System.IO.FileInfo f2)
        {
            return (f1.Name == f2.Name && f1.Directory.Name == f2.Directory.Name && 
                    f1.Length == f2.Length);
        }

        // Return a hash that reflects the comparison criteria. According to the 
        // rules for IEqualityComparer<T>, if Equals is true, then the hash codes must
        // also be equal. Because equality as defined here is a simple value equality, not
        // reference identity, it is possible that two or more objects will produce the same
        // hash code.
        public int GetHashCode(System.IO.FileInfo fi)
        {
            string s = String.Format("{0}{1}", fi.Name, fi.Length);
            return s.GetHashCode();
        }

    }

Answer 1

您需要如何处理查询返回的项目？基本上，如此繁重的操作最好在单独的线程中同时执行，以避免您刚刚遇到的情况。

编辑：一个想法

作为一种情况，您可以尝试以下算法：

• QuickSort使用（List<T>.Sort() 默认使用它）对两个数组中的项目进行排序，通过良好的实现，它会非常快GetHashCode()
• 然后在众所周知的for()循环中遍历列表并比较具有相同索引的元素
• 当任何数组的计数达到另一个列表的最大索引时 - 选择后一个列表中的所有项目作为不同的（基本上它们根本不存在于前一个列表中）。

我相信使用排序数组会带来更好的性能。我相信except()的复杂度是O(m*n)。

编辑：另一个想法，应该很快

• 从一台服务器将项目存储在Set<T>
• 然后循环遍历第二个数组并在 a 内搜索Set<T>，这会非常快！基本上O(mlogm) + O(n)因为您只需要遍历单个数组并在具有良好哈希函数的集合中进行搜索（使用GetHashCode()我提供的更新逻辑）非常快。试试看！

// some kind of C# pseudocode ;)
public IEnumerable<FileInfo> GetDifference()
{           
    ISet<FileInfo> firstServerFilesMap = new HashSet<FileInfo>();

    // adding items to set
    firstServerFilesMap.Add();

    List<FileInfo> secondServerFiles = new List<FileInfo>();

    // adding items to list
    firstServerFilesMap.Add();

    foreach (var secondServerFile in secondServerFiles)
    {
        if (!firstServerFilesMap.Contains(secondServerFile))
        {
            yield return secondServerFile;
        }
    }
}

编辑：有关平等逻辑的更多详细信息在评论中提供

尝试一下这个实施

public bool Equals(System.IO.FileInfo f1, System.IO.FileInfo f2)
{
      if ( f1 == null || f2 == null)
      {
          return false;
      }

      return (f1.Name == f2.Name && f1.Directory.Name == f2.Directory.Name && 
             f1.Length == f2.Length);
}

public int GetHashCode(System.IO.FileInfo fi)
{
    unchecked
    {
        int hash = 17;    
        hash = hash * 23 + fi.Name.GetHashCode();
        hash = hash * 23 + fi.Directory.Name.GetHashCode();
        hash = hash * 23 + fi.Length.GetHashCode();

        return hash;
    }
}

有用的链接：

• C# 中的 GetHashCode 指南
• 重写 System.Object.GetHashCode 的最佳算法是什么？