Сравнить 2 списка с лучшей производительностью возможно?

Question

У меня есть 2 списка. Один - это список всех файлов в папке, а другой - список из базы данных. Я должен сравнить эти списки, и мне интересно, есть ли лучший способ сделать это, потому что я думаю, что производительность страдает от этого. Вот несколько способов, которые я сделал:

for(int i=0; i < docListFallback.Count; i++ )
{
    if (docListFallback[i].id == metadataItem.UniqueID.ToString())
    {
        if (docListFallback[i].modifiedDate < metadataItem.Geaendert)
        {
            isDocumentMissing = true;
            downloadFile = isDocumentMissing;
        }
        docListFallback.Remove(docListFallback[i]);
        break;
    }
}

и это

for (int i = 0; i < docListModDate.Count; i++)
{
    if (docListModDate[i].id == metadataItem.UniqueID.ToString())
    {
        if (docListModDate[i].modifiedDate != metadataItem.Geaendert)
        {
           await _spManager.fileStorage.modifyDate(metadataItem.Geaendert, docListModDate[i].id);
        }
        docListModDate.Remove(docListModDate[i]);
        break;
    }
}

и это

for(int i = 0; i < cleanupDocList.Count; i++)
{
    for(int j = 0; j < existingDocuments.Count; j++)
    {
        if(cleanupDocList[i].id == existingDocuments[j].UniqueID.ToString())
        {
            addToDelList = false;
            break;
        }
        else
        {
            addToDelList = true;
        }
    }
    if(addToDelList)
    {
        toDelete.Add(cleanupDocList[i].filename);
    }
}

foreach(string fileToDelete in toDelete)
{
    await _spManager.fileStorage.DeleteFileAsync(fileToDelete);
}

Answer 1

Я бы использовал для этого Линк Except(), чтобы получить двустороннее сравнение, чтобы найти все элементы, которые есть в списке list1, но не в list2, и наоборот.

Вот пример использования списков строк. Здесь также показано, как найти элементы в обоих списках:

using System;
using System.Collections.Generic;
using System.Linq;

namespace Demo
{
    static class Program
    {
        public static void Main()
        {
            List<string> list1 = new List<string>{"A", "B", "C", "D", "E"};
            List<string> list2 = new List<string>{"D", "E", "F", "G", "H"};

            var inList1ButNotList2 = list1.Except(list2);
            var inList2ButNotList1 = list2.Except(list1);
            var inBothLists        = list1.Intersect(list2);

            Console.WriteLine("In list1 but not list2 = " + string.Join(", ", inList1ButNotList2));
            Console.WriteLine("In list2 but not list1 = " + string.Join(", ", inList2ButNotList1));
            Console.WriteLine("In both lists          = " + string.Join(", ", inBothLists));
        }
    }
}

Чтобы использовать этот подход для вашей задачи, вам нужно иметь две коллекции элементов одного типа для сравнения и метод сравнения. В приведенном выше коде я просто использую компаратор равенства строк по умолчанию, но вы можете создать свой собственный компаратор равенства, например:

public class MyComparer : IEqualityComparer<string> // Instead of string, put your own type.
{
    public bool Equals(string x, string y)
    {
        return string.Equals(x, y); // You'd implement your own comparison here.
    }

    public int GetHashCode(string obj)
    {
        return obj.GetHashCode();
    }
}

, который вы можете передать Except() методам:

static class Program
{
    public static void Main()
    {
        List<string> list1 = new List<string>{"A", "B", "C", "D", "E"};
        List<string> list2 = new List<string>{"D", "E", "F", "G", "H"};

        var comparer = new MyComparer();

        var inList1ButNotList2 = list1.Except(list2,    comparer);
        var inList2ButNotList1 = list2.Except(list1,    comparer);
        var inBothLists        = list1.Intersect(list2, comparer);

        Console.WriteLine("In list1 but not list2 = " + string.Join(", ", inList1ButNotList2));
        Console.WriteLine("In list2 but not list1 = " + string.Join(", ", inList2ButNotList1));
        Console.WriteLine("In both lists          = " + string.Join(", ", inBothLists));
    }
}

Answer 2

Проблема производительности здесь:

for(int i = 0; i < cleanupDocList.Count; i++)
{
    for(int j = 0; j < existingDocuments.Count; j++)
    {
      ...
    }
}

То, что происходит здесь, относится к каждому файлу в cleanupDocList, в котором вы перечисляете все файлы в existingDocuments. Это означает, что если в обоих списках N файлов, сложность по времени равна O(N^2), что не оптимально.

В этом случае вы можете наблюдать только то, что вас интересует, это UniqueID, поэтому вы можете сначала создать HashSet<string> всех идентификаторов в списке existingDocuments, а затем просто проверить, элемент существует в хэш-наборе. Это намного быстрее, поскольку HashSet<> реализован в виде хеш-таблицы , которая имеет постоянную среднюю сложность времени для поиска (O(1)), что означает, что мы в целом получили O(N*1)=O(N) сложность времени, которая значительный, особенно с ростом N.

Код будет выглядеть так:

var existingIds = new HashSet<string>(
        existingDocuments.Select(doc => doc.UniqueID.ToString()));

for(int i = 0; i < cleanupDocList.Count; i++)
{
    if (existingIds.Contains(cleanupDocList[i].id))
    { 
        toDelete.Add(cleanupDocList[i].filename);
    }
}

foreach(string fileToDelete in toDelete)
{
    await _spManager.fileStorage.DeleteFileAsync(fileToDelete);
}    

Самое замечательное, что этот подход не только улучшил производительность, но и значительно упростил код. Давайте назовем это беспроигрышным :-)!