在C#中迭代通用列表时的性能问题

Question

假设我们有一些具有共同属性的业务对象：

public class A
{
    // Properties in common
    public int Common { get; set; }
    public string aValue { get; set; }
    // Some other goes here.
}

public class B
{
    // Properties in common
    public int Common { get; set; }
    public string bValue { get; set; }

    // Some other goes here.
}

在我们的业务逻辑中，有两个类似于下面这样的列表：

List<A> aList = new List<A>();
List<B> bList = new List<B>();

（假设我们已经为每个列表填充了至少100个实例）

好的，让我们开始解决问题，我们需要迭代aList以设置bList中每个实例的一个属性，这个属性与共同的属性匹配，就像这样：

foreach (A a in aList)
{
    B b = bList.Find(x => x.Common == a.Common);
    if (b != null)
        b.bValue = a.aValue;
}

有没有更好的方法来改进这个操作呢？因为它使我们的应用程序花费太多时间才能完成。

谢谢。

- sammiiuu

---

我不相信100个元素会导致任何性能问题。有多少个？ - gdoron

@gdoron 这取决于你调用这个函数的频率 :) - Sergey Kalinichenko

@gdoron 我想我忘了提到这个应用程序是为Windows Mobile设备设计的，因此该应用程序受移动设备资源的限制。 - sammiiuu

Answer 1

这种方法性能不佳，因为在列表上进行Find操作是线性的。由此产生的算法是O(n ^ 2)。

您应该从具有公共属性的bList创建Dictionary，并通过键查找而不是使用Find进行搜索; 字典查找是平均O(1)的，因此它将使您的算法与列表长度成线性关系。

var dict = bList.ToDictionary(b => b.Common);
foreach (A a in aList) {
    B b;
    if (dict.TryGetValue(a.Common, out b) {
        b.bValue = a.aValue;
    }
}

- Sergey Kalinichenko

---

很好的答案，包括大O(:D)。 - user1241335

难道不可以这样写吗？B b = dict[a.Common]; if (b != null){ b.bValue = a.aValue;} - gdoron

@gdoron 很遗憾，如果该项不存在，则[]操作符将失败。 TryGetValue 比 Contains+ [] 更直接，因为它允许您通过键避免额外的查找。 - Sergey Kalinichenko

Answer 2

为了高效地查找特定的键值对，你不应该使用列表，而应该使用字典。在列表中查找特定项需要 O(N) 的时间复杂度，而在字典中只需要 O(1)。

Dictionary<int, B> bDict = new Dictionary<int, B>();
foreach (B b in bList) bDict.Add(b.Common, b);

foreach (A a in aList) {
  if (bDict.ContainsKey(a.Common)) 
    bDict[a.Common].bValue = a.aValue;
}

- Andreas

Answer 3

将你的bList复制到一个以Common为键的字典类型容器中，并在循环中使用该容器，而不是bList本身。

- 500 - Internal Server Error

Answer 4

我相信如果你在linq中进行连接，它会在两个列表上为你执行哈希连接，这将节省你手动创建字典的时间，就像其他答案中建议的那样。我没有在这台机器上安装studio来为你准备一个示例，稍后会尝试更新。

如果项目数量非常少，Linq甚至可能足够聪明，不会启动哈希连接。

编辑： 试试这样的代码：

var joined = from a in aList
                    join b in bList on a.Common equals b.Common
                    select new {
                            A = a,
                            B = b
                    };

            foreach (var item in joined)
            {
                    item.B.bValue = item.A.aValue;
            }

- Graham Murray

---

+1 这就是我会给出的答案。使用 join 也可以避免在源列表中处理不匹配项时使用 TryGetValue 或其他方法。 - phoog