计算数据集第99百分位数的最有效方法

Question

我的数据库里有100个整数。我把它们按升序排序。现在，对于第99百分位数，我取排序后的第99位数。

在给定的时间t之后，一个新的数字进入数据库，一个旧的数字被丢弃。当前代码只需取100整数并重新排序它们。

因为有99个数字是由原始的100个整数集和时间后的100个整数集合所共享的，所以t。是否有更有效的方法来计算第99百分位数、第95百分位数、第90百分位数等等？

PS:所有这些都是在MySQL数据库下完成的。

Answer 1

让我们将N称为数组A的大小(此处为N = 100)，您正在寻找K-th最小元素(经过一些修改请求后)。

最简单的解决方案可能是一种修改的插入排序:保留N-K+1最大元素的(排序)数组(让我们称之为B)。

• 丢弃元素e：遍历B (例如，while B[i] < e)(*)。如果是B[i] = e，则将所有元素< i移到右侧。
• 插入元素e：获取较低的索引i，以便使B[i] > e。将所有元素>= i移到右侧，并设置B[i] := e。
• 获取K-th更小的元素:返回B[0]。

时间复杂性:每个请求的O(N-K)。

(*)实际上，您可以使用二进制搜索来加快搜索步骤，但它不会改变整个时间复杂度。

如果N-K非常大，那么使用二叉树(每个请求的O(log(N-K))时间复杂度)是很有趣的。但考虑到数据集的实际大小(以及编程语言)，这将不是“盈利”。

Answer 2

如果您的数据是随机分布的，您可以尝试通过假设线性分布来猜测位置。

guessPosition = newnumber*(max-min)/100

然后从那点开始快速搜索。

当被发现时，把它插入正确的位置。

Answer 3

因此，插入到普通表，并添加一个触发器插入到一个额外的，排序表。每次插入额外的表时，添加新元素，然后使用索引快速找到最小(或最大)元素。放下那个元素。现在，如果项目(K)的数量很小，要么重新计算新的百分位数。或者，将元素的和保存在某个地方，减去丢弃的值并添加附加值。然后两者都有和(不迭代整个列表)，元素总数的数量也应该很快从DB中得到。应该是对数(N)的ish时间。我认为这是一个谷歌面试问题(减去DB部分)。