C#/LINQ быстрый способ сравнения двух списков и присвоения значения

Question

Я сделал код, который в основном сравнивает два списка в C#. Первый список содержит свойства, как это:

• Itemid
• TOTALVIEWS

Первый список испытывает недостаток значения для TOTALVIEWS поэтому я задаю их из 2-го списка, который имеет следующие реквизиты:

• ItemID
• HitCount // это свойство для TotalViews, которое должно быть назначено

код выглядит следующим образом:

foreach (var item in parsedMerchantData) 
{ 
    var itemInB = HitCountItemIDS.FirstOrDefault(x => x.ItemID == item.ItemID); 
    if (itemInB != null) 
    { 
     if (itemInB.HitCount != -1) 
     { 
      item.TotalViews = itemInB.HitCount; 
     } 
     else 
     { 
      item.TotalViews = 0; 
     } 
    } 
} 

Есть ли более эффективный способ, чтобы написать это с помощью LINQ или реализующего собственного компаратора, который будет работать быстрее на больших списках, содержит иногда 100000 элементов самого по себе?

Answer 1

Вот псевдо-код:

var arr1 = parsedMerchantData.OrderBy(x => x.ItemID).ToArray(); 
var arr2 = HitCountItemID.OrderBy(x => x.ItemID).ToArray(); 

var i, j = 0; 
while(i + j < arr1.Length() + arr2.Length()) // or similar condition 
{ 
    if (arr1[i].ItemID < arr2[j].ItemID) { 
     if (i < arr1.Length() - 1) { 
      i++; 
     } 
     continue; 
    } 

    if (arr1[i].ItemID > arr2[j].ItemID) { 
     if (j < arr2.Length() - 1) { 
      j++; 
     } 
     continue; 
    } 

    if (arr1[i].ItemID == arr2[j].ItemID) { 
     arr1[i].TotalViews = arr2[j].HitCount != -1 ? arr2[j].HitCount : 0; 
    } 

    // Make sure you do not let i and j grow higher then lengths of arrays 
} 

Идея заключается в том, чтобы применить алгоритмы сортировки слиянием. Что касается сложности, вы проводите O (n * log (n)), сортируя каждый список, тогда O (n) проходит через них. Сумма равна O (n * log (n)), и это самый быстрый способ, который я вижу.

Answer 2

Код будет выглядеть ниже. Не уверен, что такое тип HitCountItemID. Если анонимным, то просто сделать «уаг Dict»:

Dictionary<string, ABC_TYPE> dict = HitCountItemID.GropupBy(x => x.ItemID, y => y).ToDictionary(x => x.Key, y => y.FirstOrDefault()) 
foreach (var item in parsedMerchantData) 
{ 
    var itemInB = dict[item.ItemID]; 
    if (itemInB != null) 
    { 
     if (itemInB.HitCount != -1) 
     { 
      item.TotalViews = itemInB.HitCount; 
     } 
     else 
     { 
      item.TotalViews = 0; 
     } 
    } 
} 

Answer 3

Я предполагаю, что Вы держите в руках 2 списка во время выполнения программы/сбора данных, таким образом Вы можете сортировать их во время установки. Или, если они находятся в БД, и есть индекс в ID, который он тоже работает.

Если это так, вы должны иметь возможность выполнять только один проход через каждый массив, что бы оптимизировать программу по-настоящему высоко (теперь вы получили о сложности n^2 в зависимости от значений), после того, как вы измените, у вас будет n.

int i = 0, j = 0; 

while(i < parsedMerchantData.Count && j < HitCountItemIDS.Count) 
{ 
    var item = parsedMerchantData[i]; 
    var itemInB = HitCountItemIDS[j]; 

    if (itemInB.ItemID == item.ItemID) 
    { 
     item.TotalViews = (itemInB.HitCount > 0) ? itemInB.HitCount : 0; 
     i++; 
     j++; 
    } 
    else if(itemInB.ItemID < item.ItemID) 
     i++; 
    else //itemInB.ItemID > item.ItemID 
     j++; 
} 

Код должен выглядеть так, как один выше, Вы должны добавить больше контроля над тем, когда она заканчивается &, что должно СЛУЧИЛОСЬ со значениями остальных (это остановит когда либо i или j попал в конец).

Answer 4

Это как ответ jdweng, но немного проще, и это не будет сгенерировано исключение для отсутствующих идентификаторы позиций:

var hitCountsById = HitCountItemIDS.ToDictionary(x => x.ItemID, x => x.HitCount); 
foreach (var item in parsedMerchantData) 
{ 
    int hitCount; 
    // We don't care about the return value of TryGetValue here... 
    hitCountsById.TryGetValue(item.ItemID, out hitCount); 
    item.HitCount = hitCount == -1 ? 0 : hitCount; 
} 

Это должно быть O (N + M), где N является размер HitCountItemIDs и M - размер parsedMerchantData ... так что, поскольку данные становятся больше, он должен расти медленнее, чем подход слияния-сортировки и, безусловно, более простой код. (Это не требует сравнения идентификатора товара для заказа - либо равенства.)