在C#中比较并更新两个列表

Question

背景是我在内存中有一组昂贵的缓存值，另外还有一组相关数据，这些数据获取起来很便宜，而且不能被缓存（业务规则）。我已经让它们都正常工作了，但我想知道是否有更便宜的方法来更新这种情况...

    foreach (var nonCachedItem in searchItemsNonCached)
    {
        foreach (var cachedItem in searchItemsCached)
        {
            if (cachedItem.ID == nonCachedItem.ID)
                nonCachedItem.Description = cachedItem.Description;
        }
    }

这基本上只是将缓存信息与我刚刚获取的信息匹配。它完全有效，负载几乎可以忽略不计，但效率对我来说非常重要。

编辑：在上面的代码中，searchItemsNonCached和searchItemsCached都是SearchItem列表，其中SearchItem是一个定制对象。

- Mikey Hogarth

---

searchItemsNonCached 和 searchItemCached 分别是什么类型？它们的搜索速度比 O(n) 更快吗？它们是否已排序？ - Lou Franco

另一个您可以使用的功能是并行化搜索。 - Jahan Zinedine

Answer 1

将缓存的项存储在字典中。现在，只有在键存在时才能进行更新。

- Adam Dymitruk

Answer 2

使用缓存项加载一个Dictionary，然后循环遍历每个未缓存的项，在字典中查找匹配项。这是O(n)的，而不是嵌套循环的O(n^2)。

var cachedDictionary = new Dictionary<int, YourType>();
foreach (var item in searchItemsCached)
{
  cachedDictionary.Add(item.ID, item);
}
foreach (var item in searchItemsNonCached)
{
  YourType match;
  if (cachedDictionary.TryGetValue(out match))
  {
    item.Description = match.Description;
  }
}

如果你一开始就使用字典来缓存项目（而不是使用列表），那么你就可以避免在查找匹配项之前加载它。

- Brian Gideon

Answer 3

你所尝试的是一种连接（在数据库中的意义上），具体来说是等值连接。你可以查看维基百科文章中关于连接算法的部分。你上面列出的代码是一个嵌套循环连接，adymitruk的建议是哈希连接，但正如Lou Franco所评论的那样，最好的方法可能取决于你的集合有什么样的排序或结构（如果有的话）。

如果searchItemCached只是一个无序列表，那么哈希连接可能是你最好的选择——只需从其中一个集合或另一个集合构建一个字典，以ID作为键，然后通过从字典中查找匹配项来遍历另一个集合。如果searchItemCached已经是按ID键入的字典，则哈希连接绝对是你最好的选择。如果searchItemCached和searchItemsNonCached都按ID排序，则排序合并连接可能是最好的方法。

- Aaron

---

哈希连接使用了大量的内存，应该注意这一点，但是顺序是两个输入计数的总和。O(input1.count + input2.count)。 - Gabriel Guimarães

@Gabriel 很好的观点，这里存在时间和空间的权衡。虽然如果 searchItemCached 已经是一个字典，则不需要额外的空间。 - Aaron

抱歉，我应该提到它们都是定制对象列表。 - Mikey Hogarth

这些列表是否按特定顺序排列？如果这些列表是从一个以ID字段为索引的表中检索出来的（这很常见），它们可能已经按ID排序了（您可以明确要求数据库按ID排序以确保；如果有索引，那么这种“排序”将是免费的）。在这种情况下，排序合并连接可能会变得非常容易。 - Aaron

Answer 4

另一种方法是编写一个Linq表达式，通过ID将两个列表连接起来，并创建具有更新值的相同类型的新对象。

例如：

from nc in searchItemsNonCached
join c in searchItemCached on nc.ID equals c.ID
select new (same type) // and assign the desc from c.Description

- AD.Net