c# - list of list优化构建字典

Question

我有一个列表，其中包含类似 (listElement) 的元素:{e1,e2,e3,e4,e5,e6,e7}

它们就像列表列表(listOfList)中的那样分组: { {e1,e2,e3,e4}, {e1,e2,e3}, {e2,e3,e4}, {e1,e2}, {e2,e3}, {e3,e4}, {e5}, { e6,e7}

我想要的是将列表放入字典>> (dict) 中:

• 键，(值)
• e1, ({e1,e2,e3,e4},{e1,e2,e3},{e1,e2})
• e2, ({e1,e2,e3,e4},{e1,e2,e3},{e2,e3,e4},{e1,e2},{e2,e3})
• e3, ({e1,e2,e3,e4},{e1,e2,e3},{e2,e3,e4},{e2,e3},{e3,e4})
• e4, (({e1,e2,e3,e4},{e2,e3,e4},{e3,e4})
• e5, ({e5}) = e6, ({e6,e7})

现在我有这样的代码:

foreach (element in listElement){
   var elementListOfList = listOfList,where(e=>e.countain(f));
   dict[f.id] = elementListOfList;
}

问题是字典的构建真的太长了，因为我有大约 100 万个元素，但在字典中。

我知道使用 for 而不是 for each 可能是最好的，但我确信它可以做其他事情。

我的问题是有人有优化字典创建的想法，和/或可以帮助我优化代码的网站或书籍？

Answer 1

对于 listElement 的每个项目，您正在迭代 ListOfList 中的所有列表。 (包含通常会在到达列表末尾之前停止，但尽管如此，这会给您 O(k*n) 时间复杂度，其中 k 是 listElement 的长度，n 是 ListOfLists 中所有列表的所有元素的数量)。

你的循环大致等同于:

foreach (var element in listElement)
    foreach (var list in ListOfList)
        foreach (var elem in list)
            if (element == elem)
            {
                dict[elem].Add(list);
                break;
            }

您可以通过仅迭代一次 ListOfLists 列表的元素来改进它:

var dict = listElement.ToDictionary(e => e, e => new List<List<YourType>>());
foreach (var list in ListOfList)
    foreach (var elem in list)
        dict[elem].Add(list);

这为您提供了 O(k+n) 时间复杂度(字典查找和 List.Add 已分摊 O(1) 复杂度)。对于这个问题，您无法获得比这更好的复杂性。