在C# / LINQ中比较和赋值两个列表的最快方法是什么？

Question

我写了一段代码，用于比较C#中的两个列表。第一个列表包含以下属性：

• ItemID
• TotalViews

第一个列表缺少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个项的大型列表上更快地工作？

- User987

---

请在以后更加努力地格式化你的问题。你已经问了100多个问题了——这足够让你掌握Markdown如何使用了。没有任何借口可以解释你的帖子在我修改之前格式不好的情况。请注意，格式化是重要的，因为它可以让你的问题更容易阅读和理解。 - Jon Skeet

如果您提供一个 [mcve]，那将非常有帮助。有多种方法可以解决这个问题...字典可能是一个明显的起点，但我们不知道 HitCountItemIDS 中是否可能有两个具有相同 ID 的元素。 - Jon Skeet

我脑海中浮现的一种优化方法是通过ID对两个列表进行排序，并使用类似于MergeSort的方式同时遍历这两个列表。LINQ 并不意味着是最快的方式，而是编写快速且易读的代码。 - Dmytro Bogatov

如果您有一个或两个已排序的列表，那么您可以更好地提高其性能。这取决于您如何保持结果以及是否对它们进行了索引。 - Tatranskymedved

Dictionary<string, ABC_TYPE> dict = HitCountItemID.GropupBy(x => x.ItemID, y => y).ToDictionary(x => x.Key, y => y.FirstOrDefault()); 查找将是 dict[item.Item] - jdweng

Answer 1

这与jdweng的答案类似，但更简单，并且不会因缺少项目ID而抛出异常：

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的大小...因此，随着数据变得更大，它应该比归并排序方法增长得更慢，并且代码肯定更简单。(它也不需要比较项目ID以进行排序，只需相等即可。)

- Jon Skeet

---

哇，多好的优化啊，所有答案中最棒的，非常简单，比我的原来代码快多了！=) - User987

Answer 2

代码应该如下所示。不确定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;
        }
    }
}

- jdweng

---

这个方法会比归并排序和其他人提到的方法更快吗？ - User987

@User987 - 不是，但肯定更加清晰。 - Dmytro Bogatov

@DmytroBogatov 这个解析商家数据（parsedMerchantData）是 ConcurrentBag 还是 List 是有关系的吗？目前它的类型是 ConcurrentBag ... 如果我将其转换为 List，是否可以获得更快的性能？ - User987

@User987 - 你不能简单地将它转换为List，你需要重建结构，这会有性能惩罚。我不知道LINQ内部算法，但我感觉不应该转换为列表。GroupBy无论顺序如何都会遍历所有元素。 - Dmytro Bogatov

这将因为任何缺失的项而出错 - 你需要使用TryGetValue而不是索引器。(但这也是我会这样做的方式 - 它很可能比归并排序方法更有效率。它应该是O(N+M)，基本上。)鉴于项目ID是唯一的声明，你不需要GroupBy调用 - 只需var dict = HitCountItemIDS.ToDictionary(x => x.ItemID);事实上，你甚至可以只使用命中计数...会添加一个答案。 - Jon Skeet

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到达末尾就会停止）。

- Tatranskymedved

Answer 4

以下是伪代码：

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))，这是我看到的最快的方法。

- Dmytro Bogatov

---

在这种情况下没有必要排序，排序会增加时间。使用 Linq GroupBy() 应该比 c# 代码运行更快。 - jdweng