检查重复项时的性能

StackOverflow https://stackoverflow.com/questions/91933

题

我一直在开发一个项目，我需要迭代数据集合并删除“主键”重复的条目。我尝试过使用

List<int>

和 

Dictionary<int, bool>

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

有帮助吗？

解决方案

他们在 .NET 3.5 中添加了 HashSet 类。但我想它会与词典相媲美。如果元素少于 100 个，列表可能会表现得更好。

其他提示

编辑：别介意我的评论。我以为你在谈论 C++。我不知道我的帖子是否与 C# 世界相关。

哈希表可能会快一点。由于内存访问方式的原因，二叉树（字典中使用的树）往往相对较慢。如果您的树变得非常大，则尤其如此。

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

只需将一个简单的池分配器插入到字典模板中，您可能会发现速度提升了 10 倍。Afaik boost 有一个组件可以直接使用。

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

可能是最快的方法，但灵活性较差。每次整数集发生变化时，您都必须重做完美的哈希函数（可以自动完成）。

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

首先和你说的正好相反。字典具有索引访问（是哈希表），而 de List 则没有。

如果字典中已有数据，那么所有键都是唯一的，不能有重复项。

我怀疑您将数据存储在另一种数据类型中，并且将其存储到字典中。如果是这种情况，插入数据将适用于两个字典。

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

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

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

位图的执行时间复杂度为 O(1)（每次检查），这是很难击败的。

前段时间有一个问题 从数组中删除重复项. 。出于问题的目的，性能并没有太多考虑，但您可能想看看答案，因为它们可能会给您一些想法。另外，我可能在这里偏离了基础，但如果您尝试从数组中删除重复项，那么可以使用像这样的 LINQ 命令 可枚举.不同 可能会比你自己编写的东西给你带来更好的性能。事实证明有一种方法可以得到 LINQ 在 .NET 2.0 上运行 所以这可能是一条值得研究的路线。

如果您要使用列表，请使用 BinarySearch：

 // 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 的类型：BinarySearch( T 项, IComparer< T > );

许可以下： CC-BY-SA 和 归因
不隶属于 StackOverflow
scroll top