动态数值数组中的动态阈值确定

Question

我有一个〜1000个对象的数组，这些对象是随时间推移而发展的浮点值（以无法预先确定的方式;假设它是黑匣子）。在每个固定的时间间隔内，我想要设置一个阈值，将最高值的5-15％分开，使得在任何可以最自然地进行区分的区域进行切割，因为数据点之间存在最大差距在数组中。

对我来说，实现这种算法的最佳方式是什么？显然（我认为）在每个时间间隔结束时采取的第一步是对数组进行排序，但之后我不确定解决此问题的最有效方法是什么。我有一种感觉，没有必要列出排序阵列中感兴趣区域中连续数据点之间的所有空白，并且有一种比蛮力更快的方法来解决这个问题，但我不确定这是什么。有任何想法吗？

Answer 1

您可以编写自己的快速排序/选择例程，该程序不会针对完全位于5％-15％范围之外的子数组发出递归调用。但只有1,000件商品，我不确定这是否值得麻烦。

另一种可能性是使用花哨的数据结构随着值的变化在线追踪最大差距（例如，用子树数（用于快速索引）和最大子树间隙装饰的二叉搜索树）。这绝对不清楚这是否值得麻烦。