改变字典<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>最快的方法是什么？

回答

相关问题