大型列表的函数超时(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

您需要如何处理查询返回的项？基本上，在一个单独的线程中同时执行这些繁重的操作将是很棒的，以避免您刚刚面临的情况。

EDIT: A idea

例如，您可以尝试以下算法：

• 使用QuickSort (List<T>.Sort() uses it by default)对两个数组中的项进行排序，在众所周知的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;
    }
}

有用的链接：

• GetHashCode Guidelines in C#
• What is the best algorithm for an overridden System.Object.GetHashCode?

Answer 2

我自己还没有尝试过，但这里有一个想法:将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的一般信息的link。

编辑：或更好，您可以在一个步骤中初始化和添加数据：

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

Answer 3

我建议从散列代码中删除长度，只执行fi.FullName。这仍然是唯一性准则，尽管可能存在散列冲突(在某些情况下，您认为需要长度来区分)。但这可能比更长的“例外”执行更可取。类似地，将您的相等比较从名称和目录更改为fullname，这可能也会更好。