检查重复项时的性能

我一直在研究一个项目，我需要遍历数据集合并删除“主键”重复的条目。我已经使用检查重复项时的性能

List<int>

和

Dictionary<int, bool>

随着我发现表现略好字典试过，尽管我从来没有需要布尔标记每个条目。我的期望是，这是因为List允许索引访问，而Dictionary不允许。我想知道的是，有没有更好的解决方案来解决这个问题。我不需要再次访问这些条目，我只需要跟踪我所看到的“主键”，并确保我只对具有新主键的条目执行添加工作。我正在使用C＃和.NET 2.0。并且我无法控制修复输入数据以从源代码删除重复项（不幸的是！）。所以你可以有一个缩放的感觉，总的来说，我在应用程序中检查重复次数约1,000,000次，但是不超过约64,000次的子集需要是唯一的。

来源

2008-09-18 Timothy Carter

他们在.NET 3.5中添加了HashSet类。但我想它会和字典一致。如果你少于说100个元素，List可能会表现更好。

来源

2008-09-18 12:12:21 leppie

HashSet正是我想要的，不幸的是，我们仅限于.net 2.0，然而，使用链接@Rob关于使.net 2.0中的Linq工作，我试图让HashSet在我们的环境中工作。 – 2008-09-19 11:12:43

我真的不明白你在问什么。

首先与你说的相反。字典有索引访问（是一个哈希表），而列表没有。

如果您已经有字典中的数据，那么所有密钥都是唯一的，不能有重复。

我认为你有以另一种数据类型存储的数据，并将它存储到字典中。如果是这种情况，插入数据将与两个字典一起工作。

foreach (int key in keys) 
{ 
    if (!MyDataDict.ContainsKey(key)) 
    { 
    if (!MyDuplicatesDict.ContainsKey(key)) 
     MyDuplicatesDict.Add(key); 
    } 
    else 
    MyDataDict.Add(key); 
}

来源

2008-09-18 12:16:02

编辑：没关系我的评论。我以为你在谈论C++。我不知道我的帖子是否与C＃世界相关..

哈希表可能会更快。由于内存被访问的方式，二叉树（这是字典中使用的）往往相对较慢。如果你的树变得非常大，尤其如此。

但是，在更改数据结构之前，您是否尝试过为自己的字典使用自定义池分配器？我敢打赌，没有花时间遍历树本身，但在数百万次的分配和释放中，字典会为你做。

您可能会看到一个因子10的速度提升只是将简单的池分配器插入到字典模板中。 Afaik boost有一个可以直接使用的组件。

另一种选择：如果您知道只有64.000个条目存在于您的整数中，您可以将它们写入文件并为其创建一个完美的散列函数。这样，您可以使用散列函数将您的整数映射到0到64.000范围内并对位数组进行索引。

可能是最快的方式，但不够灵活。每当整数集更改时，您都必须重做您的完美哈希函数（可以自动完成）。

来源

2008-09-18 12:17:43

如果您正在检查整数的唯一性，并且整数范围受到限制，那么您可以使用一个数组。

为了更好的打包，你可以实现一个位图数据结构（基本上是一个数组，但是数组中的每个int通过使用每个键1位在键空间中表示32个整数）。这样，如果你的最大数量是1,000,000，你只需要~30.5KB的内存用于数据结构。

执行位图将是O（1）（每支票），这是很难击败。

来源

2008-09-18 12:21:50

回到removing duplicates from an array有一个问题。为了这个问题的目的，表现不是很重要，但你可能想看看答案，因为他们可能会给你一些想法。另外，我可能不在这里，但如果你想从数组中删除重复项，那么LINQ命令如Enumerable.Distinct可能比你自己写的东西给你提供更好的性能。事实证明有一种方法可以获得LINQ working on .NET 2.0，所以这可能是一条值得研究的路线。

来源

2008-09-18 12:26:30 rjzii

如果你打算使用一个列表，使用二分查找：

// initailize to a size if you know your set size 
List<int> FoundKeys = new List<int>(64000); 
Dictionary<int,int> FoundDuplicates = new Dictionary<int,int>(); 

foreach (int Key in MyKeys) 
{ 
    // this is an O(log N) operation 
    int index = FoundKeys.BinarySearch(Key); 
    if (index < 0) 
    { 
     // if the Key is not in our list, 
     // index is the two's compliment of the next value that is in the list 
     // i.e. the position it should occupy, and we maintain sorted-ness! 
     FoundKeys.Insert(~index, Key); 
    } 
    else 
    { 
     if (DuplicateKeys.ContainsKey(Key)) 
     { 
      DuplicateKeys[Key]++; 
     } 
     else 
     { 
      DuplicateKeys.Add(Key, 1); 
     } 
    } 
}

您也可以使用此为任何类型，你可以通过使用过载定义的IComparer：二分查找（T项目， IComparer < T>）;

来源

2008-09-18 16:39:55

检查重复项时的性能

回答

相关问题