Как найти квантиль вектора, который содержит значения и их вхождения в c ++?
У меня есть вектор, элементы которого являются парами со значением и его количество вхождений (значения являются уникальными). Я хочу найти векторный квантиль, как если бы значения были повторены счетчик раз вхождений. Каков наилучший способ сделать это в отношении сложности во время выполнения?
Например. если вектор состоит из 3 элементов (1,4), (2,5), (3,1), то 0,1-квантиль равен 1, а 0,5-квантиль равен 2, поскольку весь вектор равен 1, 1, 1, 1, 2, 2, 2, 2, 2, 3.
nth_element сделает это, если я создам вектор с повторяющимися элементами, но я не хочу, потому что это требует много памяти.
У меня есть такие же вопросы для карты вместо вектора, так как я могу заменить последний на первый.
Решение
Заметьте, что Q-й квантиль, Q в [0,1], является частью Q доли пути через все элементы полностью расширенного вектора (или отображения — это не имеет значения).
За O (n) время вы можете суммировать счет, например, 10 в вашем примере. Затем умножьте это на Q, чтобы получить целевой индекс, поэтому для Q = 0,5 у вас есть target = 5.
Теперь за O (n) вы можете снова сканировать элементы компактного вектора, суммируя счет до достижения целевого индекса (5). В вашем примере это произошло бы в (2, 5). Первое значение здесь является ответом.
Другие решения
с использованием part_sum и lower_bound можно найти квантили в логарифмическом порядке:
#include <iostream>
#include <iterator>
#include <map>
#include <vector>
#include <algorithm>
#include <utility>
#include <numeric>
#include <iostream>
int main()
{
std::vector<std::pair<int, int>> v {{1,4}, {2,5}, {3,1}};
std::map<int,int> cum;
std::swap(v.begin()->first, v.begin()->second);
std::partial_sum(v.begin(), v.end(), std::inserter(cum, cum.begin()),
[](const std::pair<int,int>& a, const std::pair<int,int>& b)
{
return std::make_pair(a.first + b.second, b.first);
}
);
std::swap(v.begin()->first, v.begin()->second);
auto quantile = 0.1;
std::cout << cum.lower_bound(quantile * cum.rbegin()->first)->second << std::endl;
quantile = 0.5;
std::cout << cum.lower_bound(quantile * cum.rbegin()->first)->second << std::endl;
return 0;
}