假设我们想要一个系统在最后一小时内保持在推文中出现前k个频繁的单词.怎么设计呢？
我可以提出hashmap,heap,log或MapReduce,但我找不到一种非常有效的方法来做到这一点.
实际上这是一个采访中的问题.
首先,我使用哈希图来计算每个单词的频率.我还保留了一个日志,所以随着时间的推移,我可以倒数最老的单词频率.
然后我保留了一个长度为K(Top K数组)的入口数组和一个数字N,它是数组中最小的计数数.
每次出现一个新单词时,我都会更新计数hashmap并获取这个新单词的计数.如果它大于N,我会发现这个单词是否在数组中.如果是,我更新数组中的条目.如果没有,我删除数组中的最小条目并将新单词插入其中.(相应地更新N)
这是问题,我的方法无法处理删除.我可能需要迭代整个计数hashmap以找到新的顶级K.
而且,正如面试官所说,系统应该非常快速地获得结果.我想几台机器一起工作,每台机器都需要一些文字.但是,如何组合结果也成为一个问题.
ric*_*ici 12
如果单词没有加权(权重0和1除外),则可以导出一个简单的数据结构,它使用O(N)辅助存储按顺序维护单词计数,其中滑动中遇到N的唯一单词数量窗口(示例中为一小时).所有操作(添加单词,过期单词,查找最常用的单词)都可以及时执行O(1).由于任何准确的解决方案都需要在滑动窗口中保留所有唯一的单词,因此尽管每个单词的常数因子不小,但这种解决方案并不是渐渐变差.
解决方案的关键是任何给定单词的计数只能递增或递减1,并且所有计数都是整数.因此,可以维持双向链接的计数列表(按顺序),其中列表中的每个节点指向具有该计数的双链字列表.此外,单词列表中的每个节点都指向适当的计数节点.最后,我们维护一个hashmap,它允许我们找到对应于给定单词的节点.
最后,为了在其生命的最后腐烂的话,我们需要从滑动窗口,它的大小为保持整个数据流O(N'),其中N'在滑动窗口中遇到的单词总数.这可以存储为单链表,其中每个节点具有时间戳和指向单词列表中的唯一字的指针.
遇到或过期某个单词时,需要调整其计数.由于计数只能递增或递减1,因此调整总是包括将单词移动到相邻的计数节点(可能存在也可能不存在); 由于计数节点存储在已排序的链表中,因此可以及时找到或创建相邻节点O(1).此外,通过从最大值向后遍历计数列表,可以始终在恒定时间内跟踪最流行的单词(和计数).
在不明显的情况下,这是在给定时间点的数据结构的粗略的ascii艺术图:
Count list word lists (each node points back to the count node)
17 a <--> the <--> for
^
|
v
12 Wilbur <--> drawing
^
|
v
11 feature
现在,假设我们找到了Wilbur.那将把它的数量提高到13; 我们可以从以下事实的成功看12是不是13该13算节点需要创建和插入计数列表.在我们这样做之后,我们Wilbur从当前的单词列表中删除它,将其放入与新计数节点相关联的新创建的空单词列表中,并将计数指针更改Wilbur为指向新计数节点.
然后,假设使用了drawingexpires,那么它的新计数将是11.我们可以看出前一个事实12是11不需要创建新的count节点; 我们只需drawing从其单词列表中删除并将其附加到单词列表关联,并11在我们这样做时修复其计数指针.现在我们注意到与之关联的单词列表12是空的,因此我们可以12从计数列表中删除计数节点并将其删除.
当一个单词的计数达到0,而不是将它附加到0不存在的计数节点时,我们只删除单词节点.如果遇到一个新单词,我们只需将该单词添加到1count节点,如果该节点不存在则创建该计数节点.
在最坏的情况下,每个单词都有唯一的计数,因此计数列表的大小不能大于唯一单词的数量.此外,单词列表的总大小正是唯一单词的数量,因为每个单词都在一个单词列表中,完全过期的单词根本不出现在单词列表中.
--- 编辑
这个算法有点RAM内存,但它确实不应该有任何麻烦持有一小时的推文.甚至一天的价值.几天之后,即使考虑缩写和拼写错误,独特单词的数量也不会有太大变化.即便如此,值得考虑减少内存占用和/或使算法并行的方法.
为了减少内存占用,最简单的方法就是删除几分钟后仍然是唯一的单词.这将大大减少独特的字数,而不会改变流行词的数量.实际上,你可以在不改变最终结果的情况下大幅修剪.
要并行运行算法,可以使用散列函数生成机器号,将单个单词分配给不同的机器.(不相同的哈希函数作为用于构造哈希表的一个.)然后顶端k的话可以通过合并顶部找到k从每个机器字; 通过散列分配保证每台机器的单词集是不同的.