0

这是一个算法问题。

我有Dictionary<object,Queue<object>>。每个队列都包含一个或多个元素。我想从字典中删除只有一个元素的所有队列。最快的方法是什么？

伪代码：foreach(item in dict) if(item.Length==1) dict.Remove(item);

在循环中很容易做到（当然不是 foreach），但我想知道哪种方法在这里最快。

为什么我想要它：我使用该字典在大量对象中查找重复元素。字典中的键是对象的散列，值是找到具有相同散列的所有对象的队列。由于我只想要重复项，因此我需要删除关联队列中只有一个对象的所有项目。

更新：

重要的是要知道，在常规情况下，一大组对象中只有几个重复项。我们假设 1% 或更少。因此，保留字典原样并从 scatch 创建一个新的字典可能会更快，只使用第一个字典中的选定元素......然后完全删除第一个字典。我认为这取决于特定算法中使用的计算 Dictionary 类方法的复杂性。

我真的很想在理论上看到这个问题，因为作为一名老师，我想和学生讨论这个问题。我自己没有提供任何具体的解决方案，因为我认为这很容易做到。问题是哪种方法最好、最快。

4

3 回答 3

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

foreach (var item in itemsWithOneEntry) {
    dict.Remove(item));
}
于 2012-11-22T12:32:37.623 回答
1

它不是尝试优化集合的遍历，如何优化集合的内容以使其仅包含重复项？这将需要将您的收集算法更改为类似这样

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-22T13:50:40.013 回答
0

请注意，在您费心使代码变得比实际需要的更复杂之前，您可能应该在实际场景中测量这对性能的影响。大多数想象中的性能问题实际上并不是导致代码缓慢的真正原因。

但是假设您确实发现可以通过避免对长度为 1 的队列进行线性搜索来获得速度优势，那么您可以使用一种称为indexing的技术来解决这个问题。

除了包含所有队列的字典外，您还维护一个仅包含长度为 1 的队列的索引容器（可能是另一个字典），因此当您需要它们时，它们已经可以单独使用。

为此，您需要增强所有修改队列长度的操作，以便它们具有更新索引容器的副作用。

一种方法是定义一个类ObservableQueue。这将是一个瘦包装器，Queue除了它还有一个ContentsChanged在队列中的项目数量发生变化时触发的事件。ObservableQueue到处使用而不是普通的Queue.

然后，当您创建一个新队列时，为其事件登记ContentsChanged一个处理程序，该处理程序检查队列是否只有一个项目。基于此，您可以从索引容器中插入或删除它。

于 2012-11-22T12:47:12.537 回答