A robust timing estimate
A measurement was repeated n times, giving n numbers—the time of each run in milliseconds. As in the article on honest benchmarking, compute from them:
- the minimum;
- the median;
- the arithmetic mean of all measurements;
- the mean without outliers: the mean of the measurements x with Q₁ − 1.5·(Q₃ − Q₁) ≤ x ≤ Q₃ + 1.5·(Q₃ − Q₁);
- how many measurements were thrown away as outliers.
The quantile of level p is defined like this: sort the measurements in ascending order, v₀ ≤ v₁ ≤ … ≤ vn−1, take the position i = p·(n − 1), its integer part ⌊i⌋ and fractional part f. The quantile is v⌊i⌋ + (v⌊i⌋+1 − v⌊i⌋)·f (if ⌊i⌋ is the last index, just v⌊i⌋). The median is the quantile of level 0.5, Q₁ and Q₃ those of levels 0.25 and 0.75. This is what numpy.quantile does by default.
Input
The first line holds n (1 ≤ n ≤ 200,000), the second n positive numbers no larger than 10⁴, with six digits after the point.
Output
Five lines: the minimum, the median, the mean, the mean without outliers—each with an error of at most 10⁻⁶—and the integer number of measurements thrown away.
Examples
Example 1
10 1.280000 1.310000 1.270000 4.170000 1.300000 1.290000 1.330000 1.280000 2.950000 1.320000
1.270000 1.305000 1.750000 1.297500 2
Limits
- Time · Python
- 4000 ms
- Time · Go
- 1000 ms
- Memory
- 256 MB
- Judging
- 8 tests
Walkthrough
Open it step by step: each step gives away a little more. You can jump straight to the solution, but a problem solved with one hint stays with you longer.
1Hint 1
The minimum and the mean take one pass. The median and the quartiles need the order. What does getting it cost?
2The idea
Sort a copy of the measurements once—and every quantile is taken from the sorted array by the formula in the statement. Then one pass over the measurements: keep those inside the “fence” [Q₁ − 1.5·IQR, Q₃ + 1.5·IQR], where IQR = Q₃ − Q₁ is the interquartile range. This is Tukey's rule, the same criterion box plots use to draw their “whiskers”.
3Walkthrough
The quantile function: position i = p·(n − 1), take the two neighbouring elements and interpolate. For n = 1 both positions are element zero, and every quantile equals the only measurement. For an even n the median comes out as the half-sum of the two middle elements—the formula does that by itself, with no special case.
There will be no division by zero: at least one measurement always stays inside the fence. For n ≥ 3 that is the element v⌊(n−1)/2⌋: its position is not left of Q₁'s and not right of the median's, so Q₁ ≤ v⌊(n−1)/2⌋ ≤ Q₃. For n ≤ 2 the fence holds the smallest measurement—check by substitution.
Look at the first example: the mean is 1.75 ms, and without outliers 1.30. Two slow runs out of ten pulled the mean up by a third. The minimum and the median hardly feel them.
3+Solution
4Complexity
Sorting is O(n log n), the rest O(n). You can do without a full sort: a quantile is found in O(n) on average with quickselect. For 200,000 numbers the difference is invisible; for billions it matters.
5Common mistakes
- The median as v[n // 2]. For an even n this is the upper of the two middles, while their half-sum is needed.
- Quartiles at index n // 4. Another definition of a quantile gives other numbers. Statistics has about a dozen definitions; the problem uses one particular one, the same as numpy's default.
- Discarding by mean ± 3 sigma. A popular rule, but it works badly for the lopsided distribution of timings: the tail inflates sigma and hides itself.