1

我需要从输入读取排序数组到 awk/gawk 并获得中位数。我不想存储整个数组并试图获得用于计算的恒定空间。

你知道有什么算法这样做吗?给定数组已排序但其大小未知。

先感谢您!

4

3 回答 3

4

进行两次,使用第一次只是计算数组的大小,如果需要,将数据存储在文件中。否则你不能在不存储数组的情况下做到这一点,因为如果你在读取 n 个项目后获取程序的状态,然后通过提供足够大的数字,你可以检索最后 n/2 个项目中的任何一个作为中值,所以该程序实际上必须至少记住这些项目。

于 2011-10-11T04:48:34.903 回答
4

没有算法可以准确地找到以固定内存量运行的未知长度的排序序列的中值。

要看到这一点,请考虑这样的算法。假设它有一个长度缓冲区N来保存序列中的项目。在此缓冲区已满之前,算法只是将项目放入其中,并在此过程中跟踪中位数。

当算法扫描第N+1th 项及以后的项目时,它必须在每一步中选择一个要删除的项目。假设它已经扫描了2N项目,丢弃了一半。让我们给它一个怀疑的好处,并说它还没有降低输入流的中位数。

考虑何时扫描第2N+1th 项。它应该掉落哪个物品?它不能丢弃它迄今为止保留的最少元素,因为输入可能在此项目之后用尽,在这种情况下,最低的可能是中位数。同样,对于它可能丢弃的任何可能元素,输入序列的未来会使这个丢弃的元素成为中值。

如果您愿意获取近似结果,那么此估算器可能适合您。

于 2011-10-11T06:00:26.120 回答
2

基本上,您要求的是查找N数组大小的“算法”,因为中位数将是元素数(N+1)/2(暂时忽略偶数/奇数细节)。

我想不出不涉及两次传递的算法。根据定义,您需要先通过才能弄清楚N.

在扫描元素i+1时,您可以保留先前i/2元素的缓冲区。当您到达数组的末尾时,中位数将只是缓冲区中的第一个值,即只需要一次通过。这样做的问题是你必须为缓冲区分配足够的内存来包含N/2元素——但你不知道是什么N,所以你不知道缓冲区应该有多大!此外,如果N值太大而无法存储,正如您在问题中所述,那么可能N/2值也太大而无法存储(否则我的建议是:只需将 RAM 翻倍)。

所以这种缓冲方法不是一种选择。两次通过。一来搞清楚N,一来获取元素(N+1)/2

于 2011-10-11T06:18:52.283 回答