java - 用最少的迭代次数求均值

Question

我有一个具有以下属性的测量列表:

1. 测量是昂贵的。更少的测量 -> 更好
2. 他们都是积极的。事实上，有一个正的下限，我无法获得低于该值的任何值。这个下限是我需要有信心知道的。
3. 他们会围绕一个或多个中值分布
4. 当我发现一个小于 median - 2*variance 的异常值时，我知道还有另一个“更好”的中值，因为“最佳”中值和下限之间的距离总是更小大于正态分布宽度的两倍

目标:以最少的迭代次数找到最佳中位数，置信度为 90%。

我更喜欢最小值，但最小的中位数就足够了。

我正在寻找的是一段代码，我在其中提供测量值，它会告诉我中位数，以及我对这个中位数是我所寻找的中位数的信心。

背景:我想为 Java 方法计时。我可以运行几分钟的测试来计算离群值的平均值，但在查看数据时，很明显对于人类来说，这些值会迅速累积到中值附近。

除非 JIT 启动并且中位数突然跳跃。最终，您将得到一条曲线，它在最小中值左侧非常陡峭(即中值左侧的方差很低)，右侧有一个长而软的斜坡，在预 JIT 的位置有一个凸起中位数是。

Sample test data (13KB)

testConnect-count.csv 是值的直方图，testConnect-history.csv 是测量序列。目标是找到一种算法，该算法通过从 testConnect-history.csv

中读取最少数量的值来返回 115000 附近的较小中值

Answer 1

我认为通常的做法是查看延迟的百分位数，因为它们不遵循正态分布，而较长的延迟会伤害您。

在您的情况下，您可以使用第 50 个百分位和第 90 个百分位。

如果你有一个排序的集合，这些很容易计算

List<Long> times = ....
Collections.sort(times);
long median = times.get(times.size()/2);
long ninetyth = times.get(times.size()*9/10);

我使用 trove，因为它可以更有效地进行时序敏感测试。它使用原始值而不是创建对象。

TLongArrayList times = 
times.sort();
long median = times.get(times.size()/2);
long ninetyth = times.get(times.size()*9/10);
long ninetynineth = times.get(times.size()*99/100);

在您的情况下，中位数是 116000，90% 的分块是 170000。99% 的分块是 255000