复杂的十字路口与地图

Question

我有两张 K、V 类型相同的地图

关键是国家

值是

的映射

所以整体的Map结构是

 Map <String, Map<String, List<City>>> m1, m2;

现在我想找出地图的哪些条目相同，哪些条目不同

例如：

m1 =    { India = [TA -> {City1, City2, City3}   KA -> {City1, City2}]
          USA =   [WI -> {City1, City2, City3},  OH -> {City1, City2}] }

m2 =    { India = [TA -> {City1, City2, City3} ]
          USA =   [WI -> {City1, City3},         DC -> {City1}] }

输出应该是

Common = { India = [TA -> {City1, City2, City3} ]
           USA = [WI -> {City1, City3}] }

有没有比循环遍历整个列表并逐行检查更好的方法来获取此信息（即使已经定义了执行此操作的方法，那也很好）？

我会用这个让我知道在过去的几年里唯一改变的是少数几个城市和几个州。

如果需要，很乐意进一步澄清。

提前致谢。

Answer 1

对于这两个映射，最好的方法是递增每个键。

但是，对于列表，如果列表已排序，请使用 binary search 遍历列表的元素。

干杯！

Answer 2

很大程度上取决于您要用来存储数据的集合类型。另一个因素是您将要使用的技术。然后，它还取决于代码的效率与可读性。我最喜欢的语言是 C#，所以我会选择它。然后实施整个事情 - 类似于你的建议 - 作为 Dictionary<string, Dictionary<string, List<City>>>.

为了获取数据，我使用了 LINQ，因为它为您提供了非常易读的代码。

我按如下方式实现了您的示例（为了简单起见，城市是简单的字符串）：

var m1 = new Dictionary<string,Dictionary<string,List<string>>>
{
    {
        "India", new Dictionary<string, List<string>> 
                    {
                        {"TA", new List<string> {"City1", "City2", "City3"}},
                        {"KA", new List<string> {"City1", "City2"}}
                    }
    },
    {
        "USA", new Dictionary<string, List<string>> 
                    {
                        {"WI", new List<string> {"City1", "City2", "City3"}},
                        {"OH", new List<string> {"City1", "City2"}}
                    }
    }
};

var m2 = new Dictionary<string,Dictionary<string,List<string>>>
{
    {
        "India", new Dictionary<string, List<string>> 
                    {
                        {"TA", new List<string> {"City1", "City2", "City3"}},
                    }
    },
    {
        "USA", new Dictionary<string, List<string>> 
                    {
                        {"WI", new List<string> {"City1", "City3"}},
                        {"DC", new List<string> {"City1"}}
                    }
    }
};

获得结果的操作是应用于嵌套集合的每个级别的 Intersect 方法：

var result = m1.Keys.Intersect(m2.Keys)
                    .ToDictionary(k => k, k => m1[k].Keys.Intersect(m2[k].Keys)
                        .ToDictionary(l => l, l => m1[k][l].Intersect(m2[k][l])));

如果您对其进行调试并展开 result，您将看到它 returns 您在示例中期望的值。

请注意，您的 City class 必须实现 IEquatable<T> 接口，以便它可以在 Intersect 方法中正确处理。 MSDN

上的实施示例

复杂的十字路口与地图

Complicated Intersection With Maps

dictionary

set-theory