c# - 在 KeyCollection 上使用 IEnumerable.Except 与利用 Dictionary.ContainsKey 进行与性能相关的相互减法和交集

Question

我有两本字典Dictionary<string, object> .我需要找到它们的交集(我的意思只是它们的键交集)和 A\B 和 B\A 减法并对对象进行一些操作(实际上我的对象是 EntityFramework 实体，我必须将它们的状态标记为 Modified ， Added 和 Deleted，尽管它与问题不是很相关)。想象一下最简单的Venn diagram .

我想以最有效的方式进行。我想我有两个选择:

1) 实现一组内部操作的通用扩展方法 IEnumerable KeyCollection 上的方法喜欢ExceptByKey ，例如:

public static Dictionary<TKey, TValue> ExceptByKeys<TKey, TValue>(this Dictionary<TKey, TValue> dict1, Dictionary<TKey, TValue> dict2)
{
    return dict1.Keys.Except(dict2.Keys).ToDictionary(key => key, key => dict1[key]);
}

然后我可以操作这些方法来分别处理三个组中的每一个。来自 there我知道 KeyCollection.Contains方法内部使用 Dictionary<TKey, TValue>.ContainsKey方法所以两者都是O(1)。所以我的 Except然后方法将在 O(n) 中运行，是这样吗？我需要为每个字典使用一次，并以某种方式检测相交的部分，这可以通过首先遍历所有字典来隐式完成字典中的实体并将它们标记为属于交集。那么，它是不是像 O(n) + O(n + m)？

2) 我也可以遍历我的字典调用 ContainsKey另一个字典上的每个元素的方法并做适当的事情。在我看来，这似乎是一个更好的解决方案，因为我只得到 O(n + m) 复杂度。

所以，问题是:- 我的计算是否正确？- 有没有我没有想过的更好的方法来完成我想要的？

2015 年 6 月 19 日更新

所以我选择了第二种情况并且它工作正常。这是我在野外的实现

using (var he = new HostEntities())
{
    var dbHardDrives = he.HardDrive.Where(_ => _.HostName == _address).ToDictionary(_ => _.Name, _ => _);
    foreach (var dbHd in dbHardDrives)
    {
        if (wmiHardDrives.ContainsKey(dbHd.Key))
        {
            he.Entry(dbHd.Value).State = EntityState.Detached;
            he.Entry(wmiHardDrives[dbHd.Key]).State = EntityState.Modified;
        }
        else
        {
            he.Entry(dbHd.Value).State = EntityState.Deleted;
        }
    }
    foreach (var wmiHd in wmiHardDrives)
    {
        if (!dbHardDrives.ContainsKey(wmiHd.Key))
        {
            he.Entry(wmiHd.Value).State = EntityState.Added;
        }
    }
    he.SaveChanges();
}

Answer 1

我觉得你的推理很有道理。 LINQs Except() 迭代第二个集合，将其放入 HashSet Set在遍历第一个集合之前，对 Set 执行查找 - 它是 O(n + m)。因此，您的扩展方法也是 O(n + m)。正如您提到的，如果您想要计算 3 组增减交集，您将不得不多次调用它，使选项 2 更可取。

您正在尝试进行外部联接，并能够分别计算左项、内项和右项。对于 O(n + m) 解决方案，您可以使用类似这样的东西

public static JoinResult<TKey> JoinKeys<TKey, TValue>(this IDictionary<TKey, TValue> first, IDictionary<TKey, TValue> second)
{
    var left = new List<TKey>();
    var inner = new HashSet<TKey>();    // HashSet to optimize lookups
    var right = new List<TKey>();

    foreach (var l in first.Keys)   // O(n)
    {
        if (second.ContainsKey(l))
            inner.Add(l);
        else
            left.Add(l);
    }

    foreach (var r in second.Keys)      // O(m)
    {
        if (!inner.Contains(r))
            right.Add(r);
    }

    return new JoinResult<TKey>
    {
        Left = left,
        Inner = inner,
        Right = right
    };
}

public class JoinResult<T>
{
    public IEnumerable<T> Left { get; set; }
    public IEnumerable<T> Inner { get; set; }
    public IEnumerable<T> Right { get; set; }
}