计算十亿个元素列表中唯一元素的最快方法是什么?

我将跳过数据结构练习,只使用SQL数据库。为什么要编写另一个必须分析和调试的自定义数据结构,只需使用数据库。他们很擅长回答这样的问题。

我会考虑 Trie 或A Directed acyclic word graph 这应该比哈希表更节省空间。测试字符串的成员资格将是o(len),其中len是输入字符串的长度,这可能与字符串哈希函数相同。

这可以在最坏的情况下解决。( n )使用时间 radix sort 计数排序作为每个字符位置的稳定排序。理论上这比使用哈希表(o( n )应输入但不保证)或mergesort(o( n 日志 n )使用trie也会导致最坏的情况( n )-时间解决方案(持续时间查找 n 键,因为所有字符串的有界长度都是一个小常量),所以这是可比的。我不知道他们在实践中是如何比较的。基数排序也很容易实现,并且有很多现有的实现。

如果所有字符串都是 D 字符或更短,且不同字符的数目为 K ,然后基数排序取0( D ( n + K )排序时间 n 钥匙。排序后,您可以在o中遍历已排序的列表( n )每次到达一个新字符串时,都要计时并递增一个计数器。这将是不同字符串的数目。自从 D 是~15和 K 相对于 n (十亿),运行时间还不错。

这使用O( DN )不过,空间(容纳每个字符串),所以空间效率比尝试要低。

如果项目是字符串,可以比较…然后我建议放弃哈希表的想法,使用更像二进制搜索树的方法。在C中有几个实现(框架中没有内置的实现)。一定要找到一个平衡的,像红黑树或AVL树。

优点是树中的每个对象都相对较小(只包含它的对象,以及一个到其父级和两个叶的链接),因此您可以拥有一整批对象。

另外,因为它是排序的,所以检索和插入时间都是O日志(N)。

由于您指定了单个对象不能包含所有字符串,所以我假定您在磁盘或其他一些外部内存中具有这些字符串。在这种情况下,我可能会选择排序。从已排序的列表中提取唯一元素很简单。合并排序对于外部排序很流行,并且只需要相当于您拥有的空间量的额外空间。首先将输入划分为适合内存的部分,对其进行排序,然后开始合并。

有了几十亿个字符串,即使只有百分之几是唯一的,哈希冲突的可能性也相当高(.NET哈希代码是32位int,产生大约40亿个唯一哈希值。如果只有1亿个唯一字符串,那么哈希冲突的风险可能会非常高)。统计数据不是我的强项,但是一些谷歌研究发现,完美分布的32位散列的碰撞概率是(n-1)/2^32,其中n是散列的唯一事物的数量。

使用一个使用大量位的算法,可以降低哈希冲突的概率, such as SHA-1 .

假设有足够的哈希算法,一个接近您已经尝试过的方法是创建一个哈希表数组。将可能的哈希值划分为足够的数值范围,以便任何给定的块都不会超过每个对象的2GB限制。根据哈希值选择正确的哈希表,然后搜索该哈希表。例如,您可以创建256个哈希表,并使用(hashvalue)%256从0..255获取哈希表编号。在将字符串分配给bucket以及检查/检索它时,请使用相同的算法。

分而治之-用前2个字母对数据进行分区(例如)

XX字典=>字符串字典=>计数

字典在内部组织为列表列表。在64位计算机上,您不会接近(2GB/8)^2限制。

我会使用数据库,任何数据库都可以。

可能是最快的,因为现代数据库针对速度和内存使用进行了优化。

您只需要一个带索引的列,然后就可以计算记录的数量。

你试过散列图(在.NET中的字典)吗? Dictionary<String, byte> 在x86上,每个条目只占用5个字节(4个用于指向字符串池的指针,1个用于字节),这大约是400米的元素。如果有许多副本,它们应该能够匹配。在实现方面,它可能非常慢(或者不工作),因为您还需要将所有这些字符串存储在内存中。

如果字符串非常相似,也可以编写自己的 Trie 实施。

否则,最好的方法是在磁盘上对数据进行排序(之后,计算唯一的元素是微不足道的),或者使用较低级别的、更像内存的语言,如C++。

我同意其他关于数据库解决方案的海报,但除此之外,合理智能地使用触发器和潜在的可爱的索引方案(即字符串的数字表示)将是最快的方法,imho。

+1对于SQL/DB解决方案,保持简单——允许您专注于手头的实际任务。

但为了学术目的,我想加上我的2分。

-1表示哈希表。(我还不能投反对票)。因为它们是使用存储桶实现的,所以在许多实际的实现中,存储成本可能很高。另外,我同意埃里克J的观点,碰撞的可能性会破坏时间效率的优势。

Lee,trie或dawg的构造将占用空间以及一些额外的时间(初始化延迟)。如果这不是一个问题(将来可能也需要对字符串集执行类似搜索的操作,并且您有足够的可用内存),那么尝试是一个不错的选择。

空间将是基数排序或类似实现(如Kirarinsnow所提到的)的问题,因为数据集很大。

下面是一次重复计数的解决方案,限制了可使用的空间。

如果我们有存储空间在我的内存中存储10亿个元素,我们可以通过 heap-sort 在_(n log n)时间中,然后通过在o(n)时间中遍历集合一次并执行以下操作:

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

如果我们没有那么多的可用内存,我们可以将磁盘上的输入文件分成更小的文件(直到大小足够小,可以将集合保存在内存中);然后使用上述技术对每个这样的小文件进行排序,然后将它们合并在一起。这需要对主输入文件进行多次传递。

我想远离 quick-sort 因为数据集很大。如果我能为第二种情况挤出一些内存,我最好使用它来减少传递的次数,而不是浪费在合并排序/快速排序中(实际上,它很大程度上取决于我们手头上的输入类型)。

编辑:只有在需要长时间存储此数据时,SQL/DB解决方案才是好的。