获取List之间差异的最快方法

本文关键字：方法 之间 List object 获取 | 更新日期: 2023-09-27 18:04:02

我正在开发一个程序，它能够找到文件之间的差异文件夹为例。我制作了一个方法，它遍历给定文件夹的文件夹结构，并为每个子文件夹构建树。每个节点包含一个文件列表，即该文件夹中的文件。每个节点都有一定数量的子节点，这些子节点对应于该文件夹中的文件夹。

现在的问题是找到一个树中存在的文件，而不是另一个树中的文件。我有一个方法:"私有列表Diff(节点索引1，节点索引2)"，这应该做到这一点。但问题是我比较树的方式。比较两棵树需要花费大量的时间——当每个输入节点包含大约70,000个文件时，Diff方法需要大约3-5分钟才能完成。

我现在是这样做的:

private List<MyFile> Diff(Node index1, Node index2)
    {
        List<MyFile> DifferentFiles = new List<MyFile>();
        List<MyFile> Index1Files = FindFiles(index1);
        List<MyFile> Index2Files = FindFiles(index2);
        List<MyFile> JoinedList = new List<MyFile>();
        JoinedList.AddRange(Index1Files);
        JoinedList.AddRange(Index2Files);
        List<MyFile> JoinedListCopy = new List<MyFile>();
        JoinedListCopy.AddRange(JoinedList);
        List<string> ChecksumList = new List<string>();
        foreach (MyFile m in JoinedList)
        {
            if (ChecksumList.Contains(m.Checksum))
            {
                JoinedListCopy.RemoveAll(x => x.Checksum == m.Checksum);
            }
            else
            {
                ChecksumList.Add(m.Checksum);
            }
        }
        return JoinedListCopy;
    }

Node类是这样的:

class Node
{
    private string _Dir;
    private Node _Parent;
    private List<Node> _Children;
    private List<MyFile> _Files;
}

获取List<object>之间差异的最快方法

与其在List结构中进行大量搜索(这相当慢)，不如将所有校验和放入HashSet中，这样可以更有效地搜索。

private List<MyFile> Diff(Node index1, Node index2)
{
    var Index1Files = FindFiles(index1);
    var Index2Files = FindFiles(index2);
    //this is all of the files in both
    var intersection = new HashSet<string>(Index1Files.Select(file => file.Checksum)
         .Intersect(Index2Files.Select(file => file.Checksum)));
    return Index1Files.Concat(Index2Files)
        .Where(file => !intersection.Contains(file.Checksum))
        .ToList();
}

如何:

    public static IEnumerable<MyFile> FindUniqueFiles(IEnumerable<MyFile> index1, IEnumerable<MyFile> index2)
    {
        HashSet<string> hash = new HashSet<string>();
        foreach (var file in index1.Concat(index2))
        {
            if (!hash.Add(file.Checksum))
            {
                hash.Remove(file.Checksum);
            }
        }
        return index1.Concat(index2).Where(file => hash.Contains(file.Checksum));
    }

这将在一个树不包含重复的假设下工作。Servy的答案将在所有情况下工作。

您是否为树中的每个元素保留整个FileSystemObject ?如果是这样的话，我认为你的内存开销将是巨大的。为什么不直接使用文件名或校验和并将其放入列表中，然后对其进行比较呢?

我可以看到，这不仅仅是一个"distinct"函数，你真正要寻找的是在JoinedListCopy集合中只存在一次的所有实例，而不仅仅是JoinedListCopy集合中所有不同实例的列表。

Servy给出了一个很好的答案，我建议使用另一种方法，它利用了linq的一些更有趣的特性，或者至少我觉得它们很有趣。

var diff_Files = (from a in Index1Files
                 join b in Index2Files
                 on a.CheckSum equals b.CheckSum
                 where !(Index2Files.Contains(a) || Index1Files.Contains(b))).ToList()

另一种构造"where"的方法可能会更好，就代码相等而言，文件实例实际上可能不相同…

where !(Index2Files.Any(c=>c.Checksum == a.Checksum) || Index1Files.Any(c=>c.Checksum == b.Checksum))

查看单个校验和，而不是整个文件对象实例。

基本策略本质上就是您已经在做的，只是更有效一点:连接集合并相互过滤，以确保您只获得唯一的条目。

另一种方法是使用linq 中的计数函数。
var diff_Files = JoinedListCopy.Where(a=> JoinedListCopy.Count(b=>b.CheckSum == a.CheckSum) == 1).ToList();

嵌套linq并不总是世界上最有效的东西，但它应该工作得相当好，获得只出现一次的所有实例。实际上，我最喜欢这种方法，因为它把事情搞砸的可能性最小，但是我首先使用的连接可能更有效。

相关文章：