finding quartiles
Instead of doing std::sort(quantile.begin(), quantile.end())
a somewhat cheaper way would be
auto const Q1 = quantile.size() / 4;
auto const Q2 = quantile.size() / 2;
auto const Q3 = Q1 + Q2;
std::nth_element(quantile.begin(), quantile.begin() + Q1, quantile.end());
std::nth_element(quantile.begin() + Q1 + 1, quantile.begin() + Q2, quantile.end());
std::nth_element(quantile.begin() + Q2 + 1, quantile.begin() + Q3, quantile.end());
This would not sort the complete array, but only do a "between groups" sort of the 4 quartile. This saves on the "within groups" sort that a full std::sort
would do.
If your quantile
array is not large, it's a small optimization. But the scaling behavior of std::nth_element
is O(N)
however, rather than O(N log N)
of a std::sort
.
Here is Quantile function which is MATLAB's equivalent with linear interpolation:
#include <algorithm>
#include <cmath>
#include <vector>
template<typename T>
static inline double Lerp(T v0, T v1, T t)
{
return (1 - t)*v0 + t*v1;
}
template<typename T>
static inline std::vector<T> Quantile(const std::vector<T>& inData, const std::vector<T>& probs)
{
if (inData.empty())
{
return std::vector<T>();
}
if (1 == inData.size())
{
return std::vector<T>(1, inData[0]);
}
std::vector<T> data = inData;
std::sort(data.begin(), data.end());
std::vector<T> quantiles;
for (size_t i = 0; i < probs.size(); ++i)
{
T poi = Lerp<T>(-0.5, data.size() - 0.5, probs[i]);
size_t left = std::max(int64_t(std::floor(poi)), int64_t(0));
size_t right = std::min(int64_t(std::ceil(poi)), int64_t(data.size() - 1));
T datLeft = data.at(left);
T datRight = data.at(right);
T quantile = Lerp<T>(datLeft, datRight, poi - left);
quantiles.push_back(quantile);
}
return quantiles;
}
Find quartiles:
std::vector<double> in = { 1,2,3,4,5,6,7,8,9,10,11 };
auto quartiles = Quantile<double>(in, { 0.25, 0.5, 0.75 });