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

Question

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

• ItemID
• Всего просмотров

В первом списке отсутствуют значения для TotalViews, поэтому я назначаю их из второго списка, в котором есть эти реквизиты:

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

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

Answer 2

Это похоже на ответ 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... так что если данные становятся больше, они должны расти медленнее, чем метод сортировки слиянием, и, безусловно, более простой код. (Это также не требует сравнения идентификатора элемента для заказа - только равенство.)

Answer 3

Код будет выглядеть ниже. Не уверен, что тип HitCountItemID. Если это аноним, тогда просто сделайте 'var 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 4

Я предполагаю, что у вас есть 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 ударил конец).