我正在寻找一种确定实时数据捕获百分位数的算法。
例如，考虑服务器应用程序的开发。
服务器的响应时间可能如下：17 ms 33 ms 52 ms 60 ms 55 ms等。
报告第90个百分点的响应时间，第80个百分点的响应时间等很有用。
天真的算法是将每个响应时间插入列表。当需要统计信息时，对列表进行排序并在适当位置获取值。
内存使用量与请求数量成线性比例。
在有限的内存使用情况下，是否存在可以产生“近似”百分位数统计信息的算法？例如，假设我要以一种处理数百万个请求的方式解决此问题，但只想使用一个千字节的内存进行百分位数跟踪（由于对百分位数应该适用于所有请求）。
还要求没有先验知识的分布。例如，我不想提前指定任何范围的存储桶。
我相信有很多很好的近似算法可以解决这个问题。一个好的首选方法是简单地使用固定大小的数组（例如，价值1K的数据）。修正一些概率p。对于每个请求，概率为p，将其响应时间写入数组（替换其中的最旧时间）。由于数组是实时流的二次采样，并且由于二次采样保留了分布，因此对该数组进行统计将为您提供完整实时流的统计信息的近似值。
这种方法有几个优点：它不需要先验信息，并且很容易编码。您可以针对特定服务器快速构建并实验性地确定，在什么时候增加缓冲区对答案的影响可忽略不计。这就是近似值足够精确的地方。
如果发现您需要太多内存来提供足够精确的统计信息，那么您将不得不进一步挖掘。好的关键字是：“流计算”，“流统计”，当然还有“百分位数”。您也可以尝试“愤怒与诅咒”的方法。
