algorithm - 在特定时刻找到无限数字流中特定数字的计数

Question

我在最近的一次采访中遇到了这个问题:

您有一个范围为 0 到 60000 的传入数字流，并且您有一个函数，该函数将从该范围内获取一个数字，并返回该数字直到那一刻出现的次数。给出一个合适的数据结构/算法来实现这个系统。

我的解决方案是:

创建一个大小为 60001 的数组，指向位向量。这些位向量将包含传入数字的计数，并且传入数字也将用于索引到相应数字的数组中。随着计数变得太大而无法容纳，位向量将动态增加。

因此，如果数字以 100numbers/sec 的速度出现，那么在 100 万年后，总数将 = (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 位。因此，假设 4 字节指针，我们需要 (60001 * 4)/1024 = 234 KB 数组内存，对于相同数字的情况，我们需要位向量大小 = 52/8 = 7.5 bytes 仍然在 234KB 左右。对于另一种情况，我们需要 (60001 * 36/8)/1024 = 263.7 KB 位向量总计约 500KB。所以，用普通的PC和内存来做这个是非常可行的。

但面试官说，因为它是无限流，它最终会溢出，并给了我提示，如果有很多 PC，我们如何才能做到这一点，我们可以在它们之间传递消息或考虑文件系统等。但我一直在想如果这个解决方案当时不起作用，其他人也会。不用说，我没有得到这份工作。

如何用更少的内存做这道题？您能想到另一种方法(可能是使用 PC 网络)吗？

Answer 1

该问题的正式模型如下。

我们想知道它是否存在一个恒定的空间有界图灵机，使得在任何给定时间内它都能识别所有夫妇的语言 L(到目前为止出现的次数)。这意味着所有正确的对都将被接受，所有不正确的对将被拒绝。

作为 Hopcroft-Ullman 定理 3.13 的推论，我们知道常量空间有界机器识别的每种语言都是正则的。

可以用正则语言的泵引理证明上述语言不是正则语言。所以你不能用一个恒定的空间有界机器来识别它。