改變字典<K,V>最快的方法是什麼？

這是一個算法問題。我有Dictionary<object,Queue<object>>。每個隊列都包含一個或多個元素。我想刪除字典中只有一個元素的所有隊列。什麼是最快的方法呢？改變字典<K,V>最快的方法是什麼？

僞代碼：foreach(item in dict) if(item.Length==1) dict.Remove(item);

這是很容易做到在一個循環（沒有的foreach，當然），但我想知道哪種方法在這裏是一個最快的。

爲什麼我想要它：我使用該字典在一大組對象中查找重複的元素。鍵入字典是對象的一種散列，值是用相同散列找到的所有對象的隊列。由於我只需要重複，我需要刪除所有項目只有在關聯隊列中的單個對象。

更新：

可能知道，在常規情況下，也有隻是在一個大組對象的幾個副本很重要的。我們假設1％或更少。因此，離開詞典可能會更快，並通過從第一個單元中選擇的元素從scatch創建一個新的單詞...然後完整地處理第一個詞典。我認爲這取決於在特定算法中使用的計算字典類的方法的共同性。

我真的很想在理論層面看到這個問題，因爲作爲一名老師，我想與學生討論這個問題。我自己並沒有提供任何具體的解決方案，因爲我認爲這很容易做到。問題是哪種方法最好，最快。

來源

2012-11-22 Al Kepp

說實話，感覺就像一些不成熟的優化......有多少東西是你處理和你確定你需要使它更快？你在正常循環中經歷了什麼樣的時間？ – Ian

它不是試圖優化集合遍歷如何優化集合的內容，以便它只包含重複？這需要改變你的收集算法而不是像這樣

var duplicates = new Dictionary<object,Queue<object>>; 
var possibleDuplicates = new Dictionary<object,object>(); 
foreach(var item in original){ 
    if(possibleDuplicates.ContainsKey(item)){ 
     duplicates.Add(item, new Queue<object>{possibleDuplicates[item],item}); 
     possibleDuplicates.Remove(item); 
    } else if(duplicates.ContainsKey(item)){ 
     duplicates[item].Add(item); 
    } else { 
     possibleDuplicates.Add(item); 
    } 
}

來源

2012-11-22 13:50:40

沒有明確的證據表明這個答案提供了最好的解決方案，但我認爲這是答案中提供的解決方案中最好的一個。這就是我接受這個的原因。 –

var itemsWithOneEntry = dict.Where(x => x.Value.Count == 1) 
          .Select(x => x.Key) 
          .ToList(); 

foreach (var item in itemsWithOneEntry) { 
    dict.Remove(item)); 
}

來源

2012-11-22 12:32:37

這不會將它們從字典中刪除 – Diego

@Diego，「那不會從字典中刪除」 - 爲什麼你會這麼說？在我看來，它喜歡它爲每個由Where子句選擇的鍵調用'dict.Remove'。 – Joe

@Joe，答案被編輯。 – Diego

請注意，在打算讓代碼變得比實際需要更復雜之前，您應該測量一下在實際情況下對性能的影響。大多數想象中的性能問題實際上不是慢代碼的真正原因。

但是，假設您發現通過避免線性搜索長度爲1的隊列可以獲得速度優勢，您可以使用稱爲索引的技術來解決此問題。

，以及您的包含所有隊列字典，你維護索引容器（可能是另一個字典）僅包含長度爲1的隊列，所以當你需要他們，他們已經單獨提供。

爲此，您需要增強所有修改隊列長度的操作，以便它們具有更新索引容器的副作用。

一種方法是定義一個類ObservableQueue。這將是Queue周圍的一個簡單封裝，但它也有一個ContentsChanged事件，該事件在隊列中的項目數發生更改時觸發。到處使用ObservableQueue而不是簡單的Queue。

然後，當你創建一個新的隊列，爭取其ContentsChanged事件檢查是否隊列只有一個項目的處理程序。基於此，您可以將其從索引容器中插入或刪除。

來源

2012-11-22 12:47:12

改變字典<K,V>最快的方法是什麼？

回答

相關問題