c# - 列表列表的优化构建字典

我有一个包含类似 (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 over a for each 可能是最好的，但我相信它可以做其他事情。

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

最佳答案

对于 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) 复杂度)。对于此问题，您无法获得比这更好的复杂性。

关于c# - 列表列表的优化构建字典，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/19345437/

E3

c# - 列表列表的优化构建字典