1

建立更早的问题：在单程中计算生成器的统计数据。Python

正如我之前提到的，一次通过生成器计算统计数据非常快速且内存高效。复杂的统计和排名属性，如第 90 个百分位和第 n 个最小的，通常需要比标准差和平均值更复杂的工作（在上面解决了）。在处理 map/reduce 作业和大型数据集时，这些方法变得非常重要，因为将数据放入列表或计算多次传递变得非常缓慢。

下面是一个 O(n) 快速排序风格的算法，用于根据排名顺序查找数据。用于查找中位数、百分位数、四分位数和十分位数。当数据已经排序时，等价于 data[n]。但需要列表中可以拆分/透视的所有数据。

如何使用生成器一次性计算中位数、百分位数、四分位数和十分位数？

需要完整列表的快速排序风格算法

import random

def select(data, n):
    "Find the nth rank ordered element (the least value has rank 0)."
    data = list(data)
    if not 0 <= n < len(data):
        raise ValueError('not enough elements for the given rank')
    while True:
        pivot = random.choice(data)
        pcount = 0
        under, over = [], []
        uappend, oappend = under.append, over.append
        for elem in data:
            if elem < pivot:
                uappend(elem)
            elif elem > pivot:
                oappend(elem)
            else:
                pcount += 1
        if n < len(under):
            data = under
        elif n < len(under) + pcount:
            return pivot
        else:
            data = over
            n -= len(under) + pcount
4

1 回答 1

4

您将需要存储大部分数据。直到完全存储它可能会有所回报。除非你愿意接受一个近似算法（当你知道你的数据是独立的时这可能是非常合理的）。

考虑您需要找到以下数据集的中位数：

0  1  2  3  4  5  6  7  8  9 -1 -2 -3 -4 -5 -6 -7 -8 -9

中位数很明显0。但是，如果您只看到前 10 个元素，那是您当时最糟糕的猜测！n/2因此，为了找到 n 个元素流的中位数，您需要在内存中至少保留候选元素。如果你不知道总大小n，你需要保留所有！

以下是每种奇数情况的中位数：

0  _  1  _  2  _  3  _  4  _  4  _  3  _  2  _  1  _  0

虽然他们从来都不是候选人，但您还需要记住元素 5 - 9：

0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18

产生中位数9。对于大小为 n 的系列中的每个元素，我可以找到一个大小为 O(2*n) 的连续系列，其中该元素为中位数。但显然，这些系列不是随机/独立的。

请参阅用于估计统计中位数、众数、偏度、峰度的“在线”（迭代器）算法？有关相关方法的概述。

于 2012-07-04T16:22:16.993 回答