我正在寻找一种算法来确定实时数据捕获的百分位数.
例如,考虑开发服务器应用程序.
服务器的响应时间可能如下:17 ms 33 ms 52 ms 60 ms 55 ms等.
报告第90百分位响应时间,第80百分位响应时间等是有用的.
朴素算法是将每个响应时间插入列表中.请求统计信息时,对列表进行排序并将值放在适当的位置.
内存使用量与请求数量呈线性关系.
是否有一种算法可以在内存使用量有限的情况下产生"近似"百分位数统计量？例如,假设我想以一种处理数百万个请求的方式来解决这个问题,但只想使用一千字节的内存进行百分位跟踪(丢弃旧请求的跟踪不是一个选项,因为百分位数应该是满足所有要求).
还要求不存在分布的先验知识.例如,我不希望提前指定任何范围的存储桶.