Nil*_*asu 5 memory algorithm distributed-computing stream data-structures
我在最近的一次采访中遇到了这个问题:
你有一个范围内的输入数字流,0 to 60000你有一个函数,它将从该范围获取一个数字,并返回该数字的出现次数,直到那一刻.提供合适的数据结构/算法来实现该系统.
我的解决方案是:
创建一个大小为60001的数组,指向位向量.这些位向量将包含传入数字的计数,并且传入的数字也将用于索引相应数字的数组.随着计数变得太大而不能容纳它们,位向量将动态增加.
因此,如果数字100numbers/sec按此速率进行,则在1百万年内,总数将为= (100*3600*24)*365*1000000 = 3.2*10^15.在最坏的情况下,流中的所有数字都是相同的ceil((log(3.2*10^15) / log 2) )= 52bits,如果数字是均匀分布的(3.2*10^15) / 60001 = 5.33*10^10,那么每个数字的出现次数将需要36 bits每个数字的总数.因此,假设4byte指针我们需要(60001 * 4)/1024 = 234 KB数组的内存,对于具有相同数字的情况,我们需要位向量大小= 52/8 = 7.5 bytes仍然大约234KB.而对于另一种情况,我们需要(60001 * 36 / 8)/1024 = 263.7 KB位向量总计约500KB.因此,用普通的PC和内存来做这件事是非常可行的.
但是访问者说,因为它是无限的流,它最终会溢出并给我提示,如果有很多PC我们怎么能这样做,我们可以在它们之间传递消息或考虑文件系统等.但我一直在想是否这个解决方案当时没有工作,其他人也会这样.不用说,我没有得到这份工作.
如何用更少的内存来解决这个问题？你能想到另一种方法(使用PC网络)吗？
该问题的正式模型可能如下.
我们想知道它是否存在一个恒定的空间有界图灵机,这样,在任何给定的时间内它识别所有夫妇的语言L(数量,到目前为止的出现次数).这意味着所有正确的夫妇都将被接受,所有不正确的夫妻将被拒绝.
作为Hopcroft-Ullman中定理3.13的推论,我们知道由恒定空间有界机器识别的每种语言都是规则的.
通过使用常规语言的泵浦引理可以证明上述语言不是常规语言.因此,您无法通过恒定空间有界机器识别它.