優化構建字典清單列表

我有一個包含元素像（listElement）的列表：{E1，E2，E3，E4，E5，E6，E7}優化構建字典清單列表

他們是一羣像在列表list（listOfList）：{{e1，e2，e3，e4}，{e1，e2，e3}，{e2，e3，e4}，{e1，e2}，{e2，e3}，{e3，e4} {E5}，{E6，E7}}

我要的是把在一個字典列表>>（字典）這樣的：

重點，（價值）
E1（ {E1，E2 ，{e1，e2，e4}，{e1，e2，e3}，{e1，e2}，{e2，e3}，{e1，e2}，{e2，e3} {e1，e2，e3}，{e2，e3}，{e2，e3，e4}，{e2，e3} {e2，e3}
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萬個元素但字典中。

我知道使用一個爲每個可以是最好的，但我相信它可能做別的事情。

我的問題是有人有一個想法來優化字典的創建，和/或一些網站或書籍，可以幫助我優化代碼？

來源

2013-10-13 Mart

我編輯了你的標題。請參閱：「[應該在其標題中包含」標籤「]（http://meta.stackexchange.com/questions/19190/）」，其中的共識是「不，他們不應該」。 –

哦對不起，沒有看到 – Mart

對於listElement的每一項，您都在迭代ListOfList中的所有列表。（包含通常會在到達列表末尾之前停止，但這會給您帶來O（k * n）時間複雜度，其中k是listElement的長度，n是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）時間：

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

您可以通過迭代一次ListOfLists名單的元素改進複雜性（字典查找和List.Add具有分期的O（1）複雜性）。您對不能比這個問題複雜得多。

來源

2013-10-13 13:20:38 lisp

謝謝，我會試試這個 – Mart

@AgentFire不，它不是。如果幾乎相同。 – lisp

它快100倍，非常感謝 – Mart

嗯，你不能做任何事情比遍歷所有列表中的所有元素更快，因爲你無法預測哪個列表包含哪些項目。

但是你可以優化你的代碼位：

說你有你的名單列表：

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-13 13:15:07 AgentFire

優化構建字典清單列表

回答

相關問題