1

我一直在做一个项目，我需要遍历数据集合并删除“主键”重复的条目。我试过使用

List<int>

和

Dictionary<int, bool>

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

4

6 回答 6

3

他们在 .NET 3.5 中添加了 HashSet 类。但我想它会与字典相提并论。如果您的元素少于 100 个，则 List 可能会表现得更好。

于 2008-09-18T12:12:21.320 回答
1

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

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

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

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

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

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

于 2008-09-18T12:17:43.570 回答
0

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

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

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

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

foreach (int key in keys)
{
  if (!MyDataDict.ContainsKey(key))
  {
    if (!MyDuplicatesDict.ContainsKey(key))
      MyDuplicatesDict.Add(key);
  }
  else
    MyDataDict.Add(key); 
}
于 2008-09-18T12:16:02.653 回答
0

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

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

位图的执行将是 O(1)（每次检查），这很难被击败。

于 2008-09-18T12:21:50.003 回答
0

不久前有一个关于从数组中删除重复项的问题。出于问题的目的，性能并不是一个考虑因素，但您可能想看看答案，因为它们可能会给您一些想法。另外，我在这里可能不合适，但是如果您尝试从数组中删除重复项，那么像Enumerable.Distinct这样的 LINQ 命令可能会给您带来比您自己编写的更好的性能。事实证明，有一种方法可以让LINQ 在 .NET 2.0 上运行，因此这可能是一条值得研究的路线。

于 2008-09-18T12:26:30.943 回答
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 item, IComparer< T > );

于 2008-09-18T16:39:55.873 回答