Lea*_*ner 0 algorithm hash bigdata
我的采访中提到了这个问题.我想知道解决方案.
给出一个文本文件,每行包含一个单词,文件大小超过1TB.任务是仅打印文件中频率为k的单词.
我没有完全回答这个问题.但我想,我是以正确的方式开始的.您使用散列技术,代码至少花费O(n)时间(因为它必须通读文件)
任何人都可以回答我这是否可以有效地完成.
通常,这类问题是"Top K"或"选择"算法的主题.这是关于一般主题的维基百科文章:维基百科:选择算法.它似乎已经普遍与"大数据"系统一起流行,也许是为了超越上一代的访谈,这些访谈的重点是在每个认真的候选人都记住了快速排序和密码代码的时候排序算法.
实际上,这仅仅是构建"大数据"(Hadoop和其他Map/Reduce系统)的教科书问题.如果数据分布在N个节点上,则每个节点可以计算单独的部分直方图(将它们的直方图函数映射到整个数据集)并合并它们的结果(将其小计减少为总计).
对于采访场景,这是一个受欢迎的问题,因为没有简单的技巧.您可以列举学术文献中的几种已发表的方法,或者您可以从头解决这个问题.
如果"词汇量"相对较小(例如,在典型的英语词典中只有几万个单词 - 那么25万字词汇量相当广泛).在这种情况下,我们希望计数可以适合典型现代硬件的RAM.如果这个数据集中的"单词"更广泛 - 超过数十或数亿 - 那么这种方法就不再可行了.
可以想象,人们可以尝试自适应或统计方法.如果我们知道没有任何单个"单词"的主要集群......数据集的任何统计上显着的样本与其他任何单词大致相似......我们可以构建直方图并扔掉那些"单词"(和他们的计数)比其他人明显更罕见.如果数据仅作为流呈现,并且我们没有对术语分布给予任何硬性保证,那么这不是一种可行的方法.但是如果我们在一些随机访问文件系统中有数据,那么我们可以稀疏地随机地对数据集进行采样以构建一组非常可能的顶部K*M(其中M是我们期望的K元素的任意倍数,因此它将全部适合RAM).
散列可能有助于我们找到每个单词的计数器,但是如果我们试图仅保留哈希的计数而不在数据结构中保留"单词"本身,则必须考虑冲突的可能性.一般来说,我认为堆会更好(可能包括将内存堆底部的内容丢弃到存储堆或trie中).
我之前说过"自适应",因为人们可以使用缓存(最终统计建模)来保持RAM中当前最频繁的"单词"并将最不频繁的单词输出到存储中(以防止最初频繁"单词"的某些退化数据集)让位给一些最初罕见的单词,当一个人深入挖掘数据集时,这个单词变得更加频繁.
虽然对这些考虑因素的对话探索在某些访谈中可能会很好用,但我建议您熟悉我引用的维基百科文章的各个部分,以便您可以将伪代码概述到其中至少一个或两个并表明你在这篇材料中确实有一些学术背景.
绝对不要忽视在提出"Top K"类问题的访谈中讨论分布式处理.这样做即使只是为了澄清所提问题的限制,并承认这些问题一直是现代"大数据"分布式处理系统的驱动力.
这里也是一个关于同一个主题的问题:StackOverflow:在大词序列中找到前K个常用词的最有效方法.