計算集合中元素百分位數的最快方法

Question

我有興趣瞭解計算集合中元素百分位數的最快方法。該集合是動態的 - 可以添加和刪除元素，並且元素的值可以隨時間變化。一個真實世界的例子就是SO用戶的聲譽。計算每位用戶最高X％的X的最快方法是什麼？

Answer 1

如果你想要一個內存數據結構，你需要一個order statistics tree，這是一個二叉搜索樹的擴充版本。這支持在O（log（n））時間內以排序順序查找第N個值，插入和刪除。

如果您使用的是SQL數據庫，則在特定列上保留索引並使用top percent查詢應該是有效的。