C# - 字典的交集<int, SortedList<int, List<int>>>

Question

考虑以下代码：

Dictionary<int, SortedList<int, List<int>>> ddl1 = new Dictionary<int, SortedList<int, List<int>>>();

ddl1.Add(1, new SortedList<int,List<int>>());
ddl1[1].Add(2, new List<int>());
ddl1[1][2].Add(3);
ddl1[1][2].Add(4);
ddl1[1][2].Add(5);

ddl1[1].Add(3, new List<int>());
ddl1[1][3].Add(3);
ddl1[1][3].Add(4);
ddl1[1][3].Add(5);


ddl1.Add(2, new SortedList<int, List<int>>());
ddl1[2].Add(2, new List<int>());
ddl1[2][2].Add(3);
ddl1[2][2].Add(4);
ddl1[2][2].Add(5);


Dictionary<int, SortedList<int, List<int>>> ddl2 = 
         new Dictionary<int, SortedList<int, List<int>>>();

ddl2.Add(1, new SortedList<int, List<int>>());

ddl2[1].Add(3, new List<int>());
ddl2[1][3].Add(3);
ddl2[1][3].Add(4);



ddl2.Add(2, new SortedList<int, List<int>>());
ddl2[2].Add(2, new List<int>());
ddl2[2][2].Add(3);

我正在寻找这两个复杂词典的交集。结果应包含

1 { 3 {3,4} }
2 { 2 {3 } }

有人可以帮我解决这个问题的 LINQ 查询吗？另外，它是否比手动 foreach 和 .contains 方法更有效？提前致谢！

Answer 1

简而言之，最好用 foreach 手动完成。我想如果你真的想通过 LINQ 来做到这一点，你将不得不创建一些自定义 IEqualityComparers，这不会比手动 foreach 解决方案更少编码工作。

但是，如果您通过 LINQ 执行此操作，则可能会受益于 PLINQ。除此之外，我不明白为什么 LINQ 解决方案可以更快。

不过，您当然可以利用 Intersect。但是请记住，每次按照评论中的建议调用 ToDictionary 时，都会创建一个新字典，这会耗费时间和内存。

所以这是我能想到的最佳解决方案，假设您仍然需要 SortedList。如果没有，请替换为常用词典。

var result = new Dictionary<int, SortedList<int, List<int>><();
foreach (var key1 in ddl1.Keys.Intersect(ddl2.Keys))
{
    var subList1 = ddl1[key1];
    var subList2 = ddl2[key1];
    var common1 = new SortedList<int, List<int>>();
    result.Add(key1, common1);
    foreach (var key2 in subList1.Keys.Intersect(subList2.Keys))
    {
        var subList1L2 = subList1[key2];
        var subList2L2 = subList2[key2];
        var common2 = subList1L2.Intersect(subList2L2).ToList();
        if (common2.Count > 0) common1.Add(key2, common2);
    }
}

Answer 2

诀窍是在字典键和上加入两个字典，SortedList 键：

var q1 = from d1 in ddl1
         from sl1 in d1.Value
         select new { d1.Key, sl1 };
var q2 = from d2 in ddl2
         from sl2 in d2.Value
         select new { d2.Key, sl2 };

var q = from ds1 in q1
        join ds2 in q2
        on         new { key1 = ds1.Key, key2 = ds1.sl1.Key } 
            equals new { key1 = ds2.Key, key2 = ds2.sl2.Key } 
        select new
        { 
            key1 = ds1.Key,
            key2 = ds1.sl1.Key,
            Intersect = ds1.sl1.Value.Intersect(ds2.sl2.Value)
        };

子查询 (q1, q2) 将字典扁平化为列表的列表，因此对于连接，可以组合字典键和列表键。

现在您可以对并行化是否确实提高性能进行基准测试，首先是使用 q2.AsParallel()，然后是 q1.AsParallel()。

Answer 3

试试这个方法：

public static IDictionary<int, SortedList<int, List<int>>> Intersect(IDictionary<int, SortedList<int, List<int>>> x, IDictionary<int, SortedList<int, List<int>>> y) {
    IDictionary<int, SortedList<int, List<int>>> one = x.Keys.Intersect(y.Keys).ToDictionary(k => k, k => x[k]);
    foreach (KeyValuePair<int, SortedList<int, List<int>>> kvp in one.ToList()) {
        one[kvp.Key] = new SortedList<int,List<int>>(kvp.Value.Keys.Intersect(y[kvp.Key].Keys).ToDictionary(k => k, k => y[kvp.Key][k]));
    }
    return one;
}

C# - 字典的交集<int, SortedList<int, List<int>>>

C# - Intersection of Dictionary<int, SortedList<int, List<int>>>

c#

.net

linq

dictionary

intersection