algorithm - 分摊分布(和百分位数)的计算，适用于 App Engine？

Question

这适用于 Google App Engine，但不一定限于此。

在 Google App Engine 上，数据库不是关系型的，因此无法实现聚合函数(例如 sum、average 等)。每行彼此独立。要计算总和和平均值，应用程序只需通过重新计算每个单独的新写入数据库来分摊其计算，以便它始终是最新的。

如何计算百分位数和频率分布(即密度)？我想做一个值域的密度图，这组值可能是百万级的。遍历整个数据集(每个查询的限制是返回 1000 行)并据此进行计算可能是可行的，但我宁愿采用一些聪明的方法。

是否有某种算法可以计算或近似计算一段时间内的密度/频率/百分位数分布？

顺便说一句，数据是不确定的，因为最大值和最小值可能到处都是。因此，分布必须采用大约 95% 的数据，并且仅基于该数据进行密度计算。

Answer 1

一遍又一遍地获取整行(一次限制为 1000...)以便每行获得一个数字肯定没有吸引力。因此，通过在包含数字列表的单独实体中记录单个数字来对数据进行非规范化(我相信每个查询的限制为 1 MB，因此每个列表的 4 字节数字不超过 250,000 个数字)。

因此，添加数字时还要获取最新的“添加数据值列表”实体，如果已满，则创建一个新实体，附加新数字，保存。如果统计数据中的微小错误不是致命的，那么可能不需要进行交易，正如您似乎暗示的那样。

如果一个项目的数据可以更改，则有单独的同类实体记录“已删除”的数据值；将一个项目的值从 23 更改为 45，将 23 添加到最新的“已删除值”列表，并将 45 添加到最新的“添加值”列表 - 这也包括项目删除。