c# - リストの違いを取得する最速の方法

Question

I'm developing a program which is able to find the difference in files between to folders for instance. I've made a method which traverses the folder structure of a given folder, and builds a tree for each subfolder. Each node contains a list of files, which is the files in that folder. Each node has an amount of children, which corresponds to folders in that folder.

Now the problem is to find the files present in one tree, but not in the other. I have a method: "private List Diff(Node index1, Node index2)", which should do this. But the problem is the way that I'm comparing the trees. To compare two trees takes a huge amount of times - when each of the input nodes contains about 70,000 files, the Diff method takes about 3-5 minutes to complete.

I'm currently doing it this way:

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

And the Node class looks like this:

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

score 4 · Accepted Answer

構造体を何度も検索する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();
}

score 1 · Accepted Answer

どうですか：

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

これは、1 つのツリーに重複が含まれないという前提で機能します。Servy の回答は、すべての場合に有効です。

score 0 · Accepted Answer

これは単なる「個別の」関数ではないことがわかります。実際に探しているのは、単に JoinedListCopy コレクション内のすべての個別のインスタンスのリストではなく、JoinedListCopy コレクション内に 1 回だけ存在するすべてのインスタンスです。

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 !(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は常に世界で最も効率的なものではありませんが、それはかなりうまく機能し、一度だけ発生するすべてのインスタンスを取得する必要があります. 実際には、何かを台無しにする可能性が最も低く、このアプローチが最も気に入っていますが、最初に使用した結合の方が効率的かもしれません。

score 0 · Accepted Answer

ツリー内のすべての要素に対して FileSystemObject 全体を保持していますか? もしそうなら、あなたのメモリオーバーヘッドは巨大になると思います。ファイル名またはチェックサムを使用してリストに入れ、それを比較してみませんか?

4 に答える 4

Related

Reference