3

我有一个包含像 (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 万个元素。

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

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

4

2 回答 2

1

好吧，你不能比迭代所有列表中的所有元素更快，因为你无法预测哪个列表包含哪些项目。

但是你可以稍微优化你的代码：

假设您有列表列表：

List<List<E>> listOfList = new List<List<E>>()
{
    new List<E>() { e1, e2, e3, e4 },
    new List<E>() { e1, e2, e3 },
    ... 
};

然后，您可以制作字典：

Dictionary<E, List<List<E>>> dic = new Dictionary<E, List<List<E>>>();

给你：

foreach (List<E> list in listOfList)
{
    foreach (E item in list)
    {
        List<List<E>> itemList;

        if (!dic.TryGetValue(item, out itemList))
        {
            dic[item] = itemList = new List<List<E>>();
        }

        itemList.Add(list);
    }
}
于 2013-10-13T13:15:07.300 回答
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) 复杂度）。对于这个问题，您无法获得比这更好的复杂性。

于 2013-10-13T13:20:38.723 回答