如何快速计算一个十亿元素列表中唯一元素的数量？

Question

我的问题有些特殊。假设有数十亿个字符串，而这些字符串通常不超过15个字符。我需要找出这个列表中唯一元素的数量。

首先，我应该使用什么对象？你不能忘记，如果我添加一个新元素，我必须检查它是否已经存在于列表中。这并不是问题，但在几百万个单词之后，它可能会严重减慢进程。

这就是为什么我认为哈希表是这个任务的理想选择，因为检查列表只需要log(1)的时间。不幸的是，在 .net 中，单个对象只能达到2GB。

下一步将是实现一个自定义哈希表，其中包含一个2GB哈希表的列表。

我在想，也许你们中有人知道更好的解决方案。（计算机规格非常高。）

- Andras Csehi

---

你是否预计会有许多独特的元素，还是大多数字符串都是重复的？ - JaakkoK

最快的编码方式：将所有内容添加到一个SQL Server表中，然后发出查询。 - Mehrdad Afshari

字符串中的字符限制为一个字节或更少（例如 ANSI、ASCII）或 Unicode 或其他？ - ThinkJet

我需要找出唯一元素的数量 - 你是在计算同一字符串的多个出现次数，查找字符串是否在集合中，还是做其他事情？ - Mathias

看起来我应该把我的评论发表为答案。然而，虽然这在实践中大多数情况下是适用的，但我认为这不是这个问题的可接受答案（因为它不太可能是最快的解决方案），如果提问者想要在他自己的数据库引擎中实现它，那该怎么办呢？ - Mehrdad Afshari

Answer 1

我建议跳过数据结构练习，直接使用SQL数据库。 为什么要编写另一个需要分析和调试的自定义数据结构，而不直接使用数据库呢？数据库非常擅长回答这样的查询。

- D.Shawley

---

这实际上取决于他的应用约束条件，而且这个假设可能并不一定成立。 - Eric J.

这是一个编程问题，不是查询问题。（是的，查询也是程序，但我们避免这种情况。）此外，OP将问题标记为C#。 - Thomas Eding

像SQL Server这样的数据库引擎是针对大量数据进行了优化。任何基于内存的算法都有可能会花费太长时间并导致过多的分页和/或线程争用。我认为您不应排除使用数据库作为此情况下最快的可能性。 - John Saunders

这是一个非常糟糕的想法，与使用trie迭代数据进行单次操作相比，这将需要很长时间来跟踪已经看到的字符串。我唯一的遗憾是我只能给这个提议投一次反对票。 - Terry Mahaffey

(1) 数据库针对集合操作进行了优化 - 存在性、交集、计数等。(2) 据我上次检查，C# 有数据库访问功能。(3) 如果数据集大于可用/高效内存大小，则自定义数据结构会变得非常困难 - 想想如何将trie的部分页面输出到磁盘并仍使其高效。(4) 不要忽视加载数据的成本，如果需要多次加载。(5) 尝试编写一个多个线程可以遍历并允许修改的trie。 - D.Shawley

Answer 2

我会考虑使用 Trie 或者有向无环字图(Directed acyclic word graph)，这样比哈希表更节省空间。测试一个字符串是否属于其中的一个集合可以在O(len)时间内完成，其中 len 表示输入字符串的长度，这与字符串哈希函数的时间复杂度相同。

- Lee

---

我没有确切的数据，但我认为 Trie 树会比数据库更快。 - David Rodríguez - dribeas

附加好处：Trie树的实现非常非常容易。 - Thomas Eding

不要混淆我们的 N。在一个 DAWG 中测试成员资格将是 O(n)，但其中 n 是字符串中字符的数量，而不是集合中字符串的数量。这是一个巨大的区别。 - Lucas

我使用了有向无环图（Directed Acyclic Word Graphs），非常有效。 - Norman Ramsey

一个包含这么多单词的 Trie，可能会根据数据和 Trie 节点的实现（即使是索引也需要 4 个字节...）而不适合于 2G。 - comingstorm

就像我之前说的那样，作为最早的回答之一——为什么没有人喜欢 Raja 呢？ - BlueRaja - Danny Pflughoeft

Answer 3

这个问题可以使用 基数排序和计数排序作为每个字符位置的稳定排序，最坏情况下时间复杂度为O(n)。这在理论上比使用哈希表（期望O(n)但不能保证）或归并排序（O(n log n)）更好。使用字典树也会得到一个最坏情况下O(n)的解决方案（常数时间查找n个键，因为所有字符串都有一个有界长度，是一个小常数），因此这是可比较的。我不确定它们在实践中如何比较。基数排序也相当容易实现，并且有很多现成的实现。

如果所有的字符串都是d个字符或更短，并且不同字符的数量是k，那么基数排序需要O（d（n + k））的时间来对n个关键字进行排序。排序后，您可以在O（n）的时间内遍历已排序的列表，并在每次到达新字符串时递增计数器。这将是不同字符串的数量。由于d约为15，而k相对于n（十亿）而言较小，因此运行时间并不太差。

但是，这会使用O（dn）的空间（来保存每个字符串），因此它比tries的空间效率低。

- KirarinSnow

---

比建议使用数据库更好，但是对数据进行排序过于繁琐，并且问题空间中不需要。任何这样做的解决方案都不是最优的。然而，trie树被设计用来解决几乎完全相同的问题。 - Terry Mahaffey

@Terry Mahaffey：比较排序（例如归并排序）并不是最优的选择。然而，问题的限制允许使用基数排序，这是最优的选择（渐进地）。被排序的标记是有界长度的字符串，并且每个位置上可能的字符数量是有限的。我同意trie更好（出于空间原因），但并不是因为基数排序不是最优的选择。 - KirarinSnow

Answer 4

如果这些项是可比较的字符串...那么我建议放弃使用哈希表的想法，转而使用更像二叉搜索树的数据结构。在C#中有几种实现方式（没有内置于框架中的实现）。请确保获取一个平衡的实现，如红黑树或AVL树。

优点在于树中每个对象相对较小（仅包含其对象和指向其父节点和两个叶子节点的链接），因此您可以拥有一大堆它们。

此外，由于它是排序的，检索和插入时间都是O log(n)。

- Nick

Answer 5

由于您指定单个对象无法包含所有字符串，我想你应该把字符串存储在磁盘或其他外部存储器中。如果是这样的话，我会选择排序算法。从排序后的列表中提取唯一元素相当简单。合并排序算法在外部排序中很受欢迎，并且只需要额外的空间与您所拥有的空间相等。首先将输入分成适合内存大小的块，对它们进行排序，然后开始合并。

- JaakkoK

Answer 6

有数十亿个字符串，即使只有几个百分比是独特的，哈希碰撞的机会也非常高（.NET哈希码是32位整数，产生大约40亿个唯一的哈希值。如果您只有100万个唯一的字符串，哈希碰撞的风险可能是无法接受的）。统计学不是我的强项，但通过一些谷歌研究可以得知，对于完美分布的32位哈希来说，碰撞的概率是（N-1）/ 2^32，其中N是被哈希的唯一事物的数量。

使用使用更多位数的算法，例如SHA-1，可以大大降低哈希碰撞的概率。

假设有一个足够好的哈希算法，一个类似于你已经尝试过的简单方法是创建一个哈希表数组。将可能的哈希值分成足够多的数字范围，以便任何给定的块不会超过每个对象的2GB限制。根据哈希值的大小选择正确的哈希表，然后在该哈希表中搜索。例如，您可以创建256个哈希表，并使用(HashValue)%256来获取0..255之间的哈希表编号。当分配字符串到桶时，使用相同的算法进行分配，并在检查/检索时使用相同的算法。

- Eric J.

Answer 7

对于SQL / Db解决方案给出+1，简单易懂 - 将使您能够专注于手头的真正任务。

但仅供学术用途，我想要添加我的2美分。

对于哈希表给出-1（我还不能投票）。因为它们使用桶来实现，存储成本在许多实际实现中可能会很大。此外，我同意Eric J的观点，碰撞的机会将削弱时间效率的优势。

Lee，构建trie或DAWG也需要占用空间以及额外的时间（初始化延迟）。如果这不是问题（当您将来可能需要对字符串集执行搜索等操作，并且可用内存充足时），则尝试trie可能是一个不错的选择。

由于数据集巨大，Radix sort或类似实现的空间将是问题（如KirarinSnow所提到的）。

以下是我为一次重复计数限制了可以使用多少空间的解决方案。

如果我们的内存有足够的空间来容纳10亿个元素，我们可以使用堆排序在Θ(n log n)时间内进行原地排序，然后只需在O(n)时间内遍历集合一次并执行以下操作：

if (a[i] == a[i+1])
    dupCount++;

如果我们没有足够的内存可用，我们可以将磁盘上的输入文件分成较小的文件（直到大小足够小以容纳在内存中的集合）；然后使用上述技术对每个这样的小文件进行排序；然后将它们合并在一起。这需要对主输入文件进行多次处理。

我想避免使用快速排序，因为数据集非常庞大。如果我能为第二种情况挤出一些内存，我会更愿意用它来减少通行证数量，而不是浪费在归并排序/快速排序中（实际上，这严重取决于我们手头的输入类型）。

编辑：仅当您需要长时间存储此数据时，SQl/DB解决方案才是好的。

- Edward I

Answer 8

分而治之 - 按前两个字母（例如）对数据进行分区

xx的字典 => 字符串的字典 => 计数

- pm100

---

我的倾向是让第一个分区更有效。不要只关注两个字符，而是关注字符串哈希的前16位。 - Loren Pechtel

要获取字符串的哈希值，需要扫描整个字符串。检查前几个字符可能会更快（虽然可能会受总线速度限制，而且由于缓存一次加载一行，也可能不会更快）。 - Pete Kirkham

Answer 9

我会使用数据库，任何一个都可以。

最好选择速度最快的，因为现代数据库针对速度和内存使用进行了优化。

你只需要一个带有索引的列，然后就可以计算记录数。

- GvS

---

我怀疑一般用途的数据库能否在这种情况下胜过专门优化的算法。一般用途的数据库需要平衡多个竞争性需求（插入速度、更新速度、查询速度、内存与CPU之间的平衡）。而专门优化的算法可以根据OP的需求进行调整。 - Eric J.

但是什么最快？将数据转储到数据库中，还是选择、发明和调整专门的算法。如果您可以将所有内容保存在内存中，并且不遇到Array、List<>或Dictionary<>的内部限制，则实现大致相同，代码性能可能更快。但是，如果您达到了这些限制... - GvS

Answer 10

如果您需要一个接近唯一计数的近似值，那么可以考虑使用HyperLogLog算法。它用于获取大型数据集（如您所提到的）的基数的近似估计。Google BigQuery和Reddit等许多现代数据库都已经实现了这个算法。它非常快速，并且可以在最小内存下工作。

- RKangel