我需要从输入读取排序数组到 awk/gawk 并获取中位数。我不想存储整个数组，而是想为计算获取恒定的空间。
您是否知道有任何算法可以做到这一点？给定数组已排序但其大小未知。
提前致谢!
最佳答案
没有算法可以准确找到以固定内存量运行的未知长度的排序序列的中值。
要了解这一点，请考虑这样一种算法。假设它有一个长度为 N 的缓冲区，用于保存序列中的项目。在这个缓冲区满之前，该算法只是将项目放入其中，同时跟踪中位数。
当算法扫描第 N+1 项及以后的项时，它必须在每一步中选择一个项来丢弃。假设它已经扫描了 2N 项，丢弃了其中的一半。让我们相信它，并说它还没有降低输入流的中值。
考虑它何时扫描第 2N+1 个项目。它应该掉落哪个元素？它不能丢弃到目前为止保留的最少元素，因为输入可能在此项目之后耗尽，在这种情况下，最低的可能是中位数。同样，对于它可能丢弃的任何可能元素，输入序列都有一个 future ，使这个丢弃的元素成为中位数。
如果您愿意采用近似 结果，那么this estimator可能适合你。
关于algorithm - 如何在不保存整个数组且空间不变的情况下计算排序数组的精确中位数？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/7721297/