Как ускорить сравнение многих полей с помощью IEqualityComparer?

Question

У меня есть список AE_AlignedPartners элементов в БД, который я извлекаю с помощью:

List<AE_AlignedPartners> ae_alignedPartners_olds = ctx.AE_AlignedPartners.AsNoTracking().ToList();

Затем я получил и сериализовал новый список (того же типа объекта) с помощью JSON:

List<AE_AlignedPartners> ae_alignedPartners_news = GetJSONPartnersList();

Чем я получаю пересечения обоих:

var IDSIntersections = (from itemNew in ae_alignedPartners_news
                        join itemOld in ae_alignedPartners_olds on itemNew.ObjectID equals itemOld.ObjectID
                        select itemNew).Select(p => p.ObjectID).ToList();

Теперь, из-за этих пересечений, мне нужно проверить, были ли изменены некоторые записи, проверить много полей ичем добавить в «мониторинг» список обновлений.Вот код:

IList<AE_AlignedPartners> ae_alignedPartners_toUpdate = new List<AE_AlignedPartners>();
foreach (var item in IDSIntersections)
{
    var itemOld = ae_alignedPartners_olds.First(p => p.ObjectID == item);
    var itemNew = ae_alignedPartners_news.First(p => p.ObjectID == item);

    if (itemOld.Field1 != itemNew.Field1 ||
        itemOld.Field2 != itemNew.Field2 ||
        itemOld.Field3 != itemNew.Field3 ||
        itemOld.Field4 != itemNew.Field4 ||
        itemOld.Field5 != itemNew.Field5 ||
        itemOld.Field6 != itemNew.Field6 ||
        itemOld.Field7 != itemNew.Field7 ||
        itemOld.Field8 != itemNew.Field8 ||
        itemOld.Field9 != itemNew.Field9)
    {
        AE_AlignedPartners toUpdate = mapper.Map<AE_AlignedPartners, AE_AlignedPartners>(itemNew);
        toUpdate.ID = itemOld.ID;

        ae_alignedPartners_toUpdate.Add(toUpdate);
    }
}

Который очень медленный (~ 4 минуты в выпуске с ~ 70k записями).

Недавно я обнаружил здесь IEqualityComparer, который действительно ускоряет процесс сравнения.

Могу ли я воспользоваться этим в этом случае?Или что является действительной оптимизацией?

Я бы не использовал предложенный FullOuterJoin, поскольку это будет означать много рефакторинга прямо сейчас (я сделаю это в следующем проекте, обещание).

Есть советы?Спасибо

Answer 1

Пользовательский IEqualityComparer<AE_AlignedPartners> был бы хорош, но не потому, что он улучшает производительность, он должен сделать то же самое сравнение.Но поскольку инкапсуляция логики делает ее более понятной, удобочитаемой и пригодной для повторного использования.Вы можете использовать его для многих методов LINQ.

Что медленно, так это то, что вы всегда ищите старый и новый элемент через ObjectId в foreach -петле.

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

var intersections = from itemNew in ae_alignedPartners_news
                    join itemOld in ae_alignedPartners_olds on itemNew.ObjectID equals itemOld.ObjectID
                    select new { New = itemNew, Old = itemOld };

foreach(var x in intersections)
{
    var itemOld = x.Old;
    var itemNew = x.New;
    // ... 
}

Answer 2

У вас есть вложенные циклы реализация

// O(N) : Loop over IDSIntersections
foreach (var item in IDSIntersections)
{
    // O(N) : Again, loop over ae_alignedPartners_olds
    var itemOld = ae_alignedPartners_olds.First(p => p.ObjectID == item);
    var itemNew = ae_alignedPartners_news.First(p => p.ObjectID == item);
    ...

В худшем случае вы будете иметь O(N) * O(N) = O(N**2) сложность времени;миллиарды петель: 70k * 70k ~ 5e9.Давайте избавимся от внутренних циклов с помощью словарей :

// O(N)
var dictOld = ae_alignedPartners_olds
  .GroupBy(p => p.ObjectID) // ObjectID should be a int, string or provide good GetHashCode()
  .ToDictionary(chunk => chunk.Key,
                chunk => chunk.First());

// O(N)
var dictNew = ae_alignedPartners_news
  .GroupBy(p => p.ObjectID) 
  .ToDictionary(chunk => chunk.Key,
                chunk => chunk.First());

// O(N)
foreach (var item in IDSIntersections)
{
   // O(1) : no loops when finding value by key in dictionary
   var itemOld = dictOld[item];      
   var itemNew = dictNew[item];
   ... 

Теперь у нас будет около 3 * O(N) циклов: 3 * 70k ~ 2e5