Как мне сравнить и обновить 2 списка с огромным количеством элементов?

Question

Примечание. Решено с помощью объединения LINQ.

Мне нужно сравнить значение списка из списка источников, если оно присутствует в списке адресатов, и если да, то сохранить его втретий список.

Код, который я написал, работает, но он занимает много времени, так как мой список источников содержит 30 тыс. элементов и сравнивает каждое значение элемента с целевым списком в 15 миллионов, что занимает много времени.время.потому что он будет перебирать весь список каждый раз (30k * 15 миллионов раз)

См. код, который, очевидно, не оптимален, но выполняет свою работу.

        // The below code will generate the lists from CSV file
        The lists are below for sample

        **Source List**
        FileId  FilePath      FileChecksum
        1       somepath A    check1
        2       somepath AA   check2
        3       somepath AAB  check3
        4       somepath B    check4
        5       somepath BB   check5

        **Destination List**

        StepId  StatusID  JobId ProjectId FileId     FilePath
        5        6         4    2091      577206853  somepath A
        5        6         4    2092      577206853  somepath AA
        5        6         4    2093      577206853  somepath AAA
        5        6         4    2094      577206853  somepath AB
        5        6         4    2095      577206853  somepath A
        5        6         4    2096      577206853  somepath B
        5        6         4    2097      577206853  somepath BB

        List<Source> SourceList = File.ReadAllLines(@"D:\source.csv").Skip(1).Select(v => Source.SourceFromCSv(v)).ToList();

        List<Destination> DestinationList = File.ReadAllLines(@"D:\Destination.csv").Skip(1).Select(d => Destination.FromDestinationCSV(d)).ToList();

        //This will compare and create a new list
        var result1 =
            from s in SourceList
            from d in DestinationList
            where (d.FilePath.ToLower() == s.FilePath.ToLower())
             select (d.StepId + "," + d.StatusId + "," + d.JobId + "," + 
             d.ProjectId + "," + d.FileId + "," + d.FilePath + "," + 
             s.FileChecksum);



             Expected Result:
             StepId StatusID  JobId ProjectId FileId    FilePath      FileChecksum
             5       6         4    2091      577206853 somepath A    check1
             5       6         4    2092      577206853 somepath AA   check2
             5       6         4    2095      577206853 somepath A    check1
             5       6         4    2096      577206853 somepath B    check4
             5       6         4    2097      577206853 somepath BB   check5

Answer 1

Вы можете заказать оба списка, а затем сравнить строку за строкой.Сложность алгоритма равна O (n log n + n).

Вы сравниваете первую строку данных A с первой строкой данных B, а затем увеличиваете индекс указателя на «большей» строке.Если данные A имеют 8, а данные B имеют 7 и 9, вы будете знать, что 8 не присутствует в данных B, как только вы достигли 9.

Вы должны начать сравнение с максимально возможным индексом.Таким образом, вы получаете быстрое завершение, если список действительно является подсписком.

Answer 2

var query = from s in SourceList
 join d in DestinationList on 
 s.FilePath.ToLower().TrimEnd() equals d.FilePath.ToLower().TrimEnd()
 select (d.StepId + "," + d.StatusId + "," + d.JobId + "," +d.ProjectId + "," + d.FileId + "," + d.FilePath + "," + s.FileChecksum);

LINQ join сделал то же самое менее чем за 5 секунд.

Answer 3

Да, если вам не нужны все функции списка, сделайте базовый тип HashSet<T>, что значительно улучшит поиск. Вашему пользовательскому типу может потребоваться реализовать правильную функцию GetHashCode(), чтобы еще больше повысить скорость поиска.

См:

• HashSet<T>
• GetHashCode()

Не вызывайте new HashSet(query.ToList()), вместо этого преобразуйте непосредственно в хэш-набор при создании экземпляра списка, query.ToHashSet(), при необходимости передавая в Equality Comparer, см. Ниже:

• ToHashSet(IEqualityComparer<T>)

Вместо пользовательской реализации GetHashCode вы также можете реализовать пользовательскую IEqualityComparer для обработки конкретных случаев, таких как ваш, где конкретные поля составляют правила равенства. Visual Studio и Resharper в настоящее время предлагают встроенный рефактор для создания хорошей реализации GetHashCode и Equals.

.

См:

• IEqualityComparer<T>

Затем вы можете использовать IntersectWith, чтобы получить все предметы в обоих наборах за один вызов:

См:

• IntersectWith()

Создание специального объекта, в который вы можете конвертировать Source и Destination, или предоставление им одного и того же базового класса позволит это.

Вы также можете использовать IDictionary<Key, Value> и сделать ключ Item.FilePath.ToLower(), применяются те же принципы, что и выше. Это позволит среде выполнения проверить, существует ли элемент в другом списке, используя GetHashCode строки, которая по умолчанию оптимизирована.

Answer 4

Вы могли бы сделать это наоборот.Вместо того, чтобы выбрать одну из 30 000 записей источника, вы можете выполнить итерации по 30 миллионам записей.затем вы можете остановиться, если вы нашли все 30 тыс. записей или в худшем случае после 30 млн. записей.это все еще лучше, чем 30K * 15M.

Answer 5

Все, что вы делаете в принципе, это добавление контрольной суммы файла в конец списка адресатов.

Создайте хеш или словарь из списка источников, тогда ваш новый список будет выглядеть примерно так:

//create dictionary SourceDictionary<string,string> with key = filepath.tolower and value = checksum
var newList = DestinationList.select(d => $"{d.thing1},{d.thingN}" + SourceDictionary[d.filename.tolower()])

должно быть намного быстрее