5

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

您有一个范围内的传入数字流，0 to 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 bits每个数字的总数。因此，假设 4 字节指针我们需要(60001 * 4)/1024 = 234 KB用于数组的内存，并且对于具有相同数字的情况，我们需要位向量大小 =52/8 = 7.5 bytes仍然在 234KB 左右。而对于另一种情况，我们需要(60001 * 36 / 8)/1024 = 263.7 KB总计约 500KB 的位向量。所以，用普通的PC和内存来做这件事是非常可行的。

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

如何用更少的内存来解决这个问题？你能想到另一种方法吗（可能是使用网络PC）？

4

3 回答 3

5

该问题的正式模型可能如下。

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

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

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

于 2012-07-29T13:36:53.047 回答
0

您可以轻松地使用基于索引的搜索，通过使用像 int arr[60000][1] 这样的数组，每当您获得一个数字（例如 5000）时，直接访问 index(num-1) = (5000-1) as, arr[ num-1][1]，并增加数字，现在每当您想知道特定 num 发生了多少次时，您只需通过 arr[num-1][1] 访问它，您就会得到计数对于那个数字，它是最简单的线性时间实现。

于 2012-07-30T11:31:52.743 回答
-1

这不是外部排序吗？将无限流存储在文件中。在文件中执行 seek() （RandomAccessFile.seek()在 Java 中）并获取适当的时间戳。这类似于二分搜索，因为数据是按时间戳排序的。一旦你得到适当的时间戳，问题就变成了从无限的数字集中计算一个特定的数字。在这里，由于数字范围有限，因此可以进行计数排序，而不是在内存中进行快速排序。

于 2012-07-29T16:17:58.480 回答