对于大列表函数超时(c#中的LINQ查询)

本文关键字：中的 LINQ 查询 于大 列表 函数 超时 | 更新日期: 2023-09-27 18:05:48

我使用以下查询

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

而myFileCompare根据名称和长度对两个文件进行比较。

如果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();
        }
    }

对于大列表函数超时(c#中的LINQ查询)

您需要对查询返回的项做什么?基本上，这种繁重的操作最好在一个单独的线程中同时执行，以避免刚才遇到的情况。

EDIT: An idea

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

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

我相信排序数组可以提供更好的性能。我相信的复杂性(除外)是 O (m * n) 。

编辑:另一个想法，应该非常快

  • 从一个服务器存储项目在Set<T>
  • 然后循环遍历第二个数组并在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的最佳算法?

我自己没有尝试过，但这里有一个想法:实现list1作为HashSet，如下所示:

HashSet<FileInfo> List1 = new HashSet<FileInfo>(myFileCompare);

添加所有文件:

foreach(var file in files)
{
    List1.Add(file);
}

删除元素:

List1.ExceptWith(list2);

然后列举:

foreach(var file in List1)
{
    //do something
}

我认为它更快，但就像我说的，我还没有试过。这里是HashSet的一般信息链接。

编辑:

或者更好的是，您可以一步初始化和添加数据:

HashSet<FileInfo> List1 = new HashSet<FileInfo>(files, myFileCompare);

我建议从哈希代码中删除长度，只做fi.FullName。这仍然保持唯一性原则，尽管可能存在哈希冲突(在某些情况下，您认为需要用长度来区分)。但这可能比冗长的"Except"执行更可取。同样，将相等性比较从名称和目录更改为全名，这可能也会提高性能。

相关文章：