32

在某些库代码中，我有一个可以包含 50,000 项或更多项的列表。

库的调用者可以调用导致字符串被添加到列表中的方法。如何有效地检查要添加的字符串的唯一性？

目前，在添加字符串之前，我会扫描整个列表并将每个字符串与要添加的字符串进行比较。这开始显示超过 10,000 个项目的规模问题。

我将对此进行基准测试，但对洞察力感兴趣。

  • 如果我将 List<> 替换为 Dictionary<> ，随着列表增加到 10,000 个或更多项目， ContainsKey() 会明显更快吗？
  • 如果我将唯一性检查推迟到添加所有项目之后，它会更快吗？那时我需要检查每个元素与其他元素，仍然是 n^^2 操作。

编辑

一些基本的基准测试结果。我创建了一个抽象类，它公开了 2 个方法：填充和扫描。Fill 只是用 n 个项目填充集合（我使用了 50,000 个）。Scan 扫描列表 m 次（我使用了 5000 次）以查看是否存在给定值。然后我为 List 构建了该类的实现，为 HashSet 构建了另一个实现。

使用的字符串长度统一为 11 个字符，通过抽象类中的方法随机生成。

一个非常基本的微基准。

Hello from Cheeso.Tests.ListTester
filling 50000 items...
scanning 5000 items...
Time to fill: 00:00:00.4428266
Time to scan: 00:00:13.0291180

Hello from Cheeso.Tests.HashSetTester
filling 50000 items...
scanning 5000 items...
Time to fill: 00:00:00.3797751
Time to scan: 00:00:00.4364431

因此，对于该长度的字符串，HashSet 在扫描唯一性时大约比 List 快 25 倍。此外，对于这种大小的集合，在向集合中添加项目时，HashSet 对 List 的惩罚为零。

结果很有趣且无效。为了得到有效的结果，我需要做热身间隔，多次试验，随机选择实施。但我相信这只会稍微改变标准。

感谢大家。

编辑2

在添加随机化和多次试验后，HashSet 在这种情况下始终优于 List，大约 20 倍。

这些结果不一定适用于可变长度的字符串、更复杂的对象或不同的集合大小。

4

6 回答 6

60

您应该使用HashSet<T>专为您正在做的事情而设计的课程。

于 2009-12-07T14:30:04.827 回答
19

使用HashSet<string> 代替List<string>，那么它应该可以很好地扩展。

于 2009-12-07T14:30:38.273 回答
5

根据我的测试，与:)HashSet<string>相比不需要时间List<string>

于 2009-12-07T14:37:09.030 回答
3

可能是题外话，但如果你想以独立于语言的方式扩展非常大的独特字符串集（数百万+），你可以查看Bloom Filters。

于 2009-12-07T15:28:39.037 回答
0

我读过字典<> 是作为关联数组实现的。在某些语言中（不一定与 .NET 相关），字符串索引存储为树结构，该结构根据节点中的字符在每个节点处分叉。请参阅http://en.wikipedia.org/wiki/Associative_arrays。

Aho 和 Corasick 在 1973 年设计了一个类似的数据结构（我认为）。如果您在这样的结构中存储 50,000 个字符串，那么存储多少字符串并不重要。长度更重要的字符串。如果它们的长度大致相同，那么您可能永远不会看到查找速度变慢，因为搜索算法在运行时相对于您正在搜索的字符串的长度是线性的。即使对于红黑树或 AVL 树，搜索运行时间更多地取决于您要搜索的字符串的长度，而不是索引中的元素数量。但是，如果您选择使用散列函数实现索引键，您现在会产生散列字符串的成本（将是 O(m)，m = 字符串长度）以及在索引中查找字符串的成本，即可能是 O(log(n))，n = 索引中的元素数。

编辑：我不是 .NET 大师。其他更有经验的人提出了另一种结构。我会接受他们的话而不是我的话。

编辑2：您的分析对于比较独特性有点偏离。如果您使用散列结构或字典，那么由于我在上面发布的推理，它不会是 O(n^2) 操作。如果您继续使用列表，那么它是 O(n^2) *（集合中字符串的最大长度）是正确的，因为您每次都必须检查列表中的每个元素。

于 2009-12-07T14:34:15.073 回答
0

该Contains(T)功能不适合您吗？

于 2009-12-07T14:42:24.527 回答