вектор — быстрый расчет в процентах C ++
Я пытаюсь написать процентиль функцию, которая принимает 2 вектора на входе и 1 вектор на выходе. Одним из входных векторов (Distr) будет распределение случайных чисел. Другой входной вектор (Тесты) будет вектором значений, которые я хочу вычислить в процентилях из Distr. Выходными данными будет вектор (такого же размера, как у тестов), который возвращает процентиль для каждого значения в тестах.
Ниже приведен пример того, что я хочу:
Input Distr = {3, 5, 8, 12}
Input Tests = {4, 9}
Output Percentile = {0.375, 0.8125}
Следующее — моя реализация в C ++:
vector<double> Percentile(vector<double> Distr, vector<double> Tests)
{
double prevValue, nextValue;
vector<double> result;
unsigned distrSize = Distr.size();
std::sort(Distr.begin(), Distr.end());
for (vector<double>::iterator test = Tests.begin(); test != Tests.end(); test++)
{
if (*test <= Distr.front())
{
result.push_back((double) 1 / distrSize); // min percentile returned (not important)
}
else if (Distr.back() <= *test)
{
result.push_back(1); // max percentile returned (not important)
}
else
{
prevValue = Distr[0];
for (unsigned sortedDistrIdx = 1; sortedDistrIdx < distrSize; sortedDistrIdx++)
{
nextValue = Distr[sortedDistrIdx];
if (nextValue <= *test)
{
prevValue = nextValue;
}
else
{
// linear interpolation
result.push_back(((*test - prevValue) / (nextValue - prevValue) + sortedDistrIdx) / distrSize);
break;
}
}
}
}
return result;
}
Размеры как Distr, так и Tests могут быть от 2000 до 30000.
Существуют ли какие-либо библиотеки, которые могут рассчитывать процентиль, как показано выше (или аналогичные)? Если нет, то как я могу сделать приведенный выше код быстрее?
Решение
Существует линейный алгоритм для вашей задачи (линейное время логарифмическое в обоих размерах). Вам нужно отсортировать оба вектора, а затем иметь два итератора, проходящих через каждый (itDistr, itTest). Есть три варианта:
1.
* itDistr < * itTest
Здесь вам нечего, кроме приращения itDistr,
2.
* itDistr> = * itTest
Это тот случай, когда вы нашли тестовый пример, где *itTest является элементом интервала [ *(itDistr-1), *itDistr ), Таким образом, вы должны сделать интерполяцию, которую вы использовали (линейную), а затем увеличить itTest,
Третья возможность — это когда любой из них достигает конца своего контейнера-вектора. Вы также должны определить, что происходит в начале и в и, это зависит от того, как вы определяете распределение по серии ваших чисел.
Существуют ли какие-либо библиотеки, которые могут рассчитывать процентиль, как показано выше (или аналогичные)?
Возможно, но это легко реализовать, и вы можете точно контролировать метод интерполяции.
Другие решения
Я бы сделал что-то вроде
vector<double> Percentile(vector<double> Distr, vector<double> Tests)
{
double prevValue, nextValue;
vector<double> result;
unsigned distrSize = Distr.size();
std::sort(Distr.begin(), Distr.end());
for (vector<double>::iterator test = Tests.begin(); test != Tests.end(); test++)
{
if (*test <= Distr.front())
{
result.push_back((double) 1 / distrSize); // min percentile returned (not important)
}
else if (Distr.back() <= *test)
{
result.push_back(1); // max percentile returned (not important)
}
else
{
auto it = lower_bound(Distr.begin(), Distr.end(), *test);
prevValue = *(it - 1);
nextValue = *(it + 1);
// linear interpolation
result.push_back(((*test - prevValue) / (nextValue - prevValue) + (it - Distr.begin())) / distrSize);
}
}
return result;
}
Обратите внимание, что вместо линейного поиска Distr для каждого теста я использую тот факт, что Distr сортируется и вместо этого выполняется бинарный поиск (используя нижняя граница).
Линейный поиск Distr для каждого элемента тестов был бы основным периодом времени, если оба из них велики.
Когда Distr намного больше, намного быстрее выполнять бинарный поиск, а не линейный. В STD доступен алгоритм двоичного поиска. Вам не нужно писать один.
Когда Tests почти такой же большой, как Distr, или больше, быстрее выполнить сортировку по индексу, а затем последовательно просмотреть два отсортированных списка, сохраняя результаты, а затем вывести сохраненные результаты в следующем проходе.
Редактировать: я вижу, что ответ Csaba Balint дает немного больше деталей о том, что я имел в виду под «последовательностью двух отсортированных списков вместе».
Изменить: основные методы обсуждаются:
1) Сортировать оба списка, а затем обрабатывать линейно вместе, время NlogN + MlogM
2) Сортировка только одного списка и двоичный поиск, время (N + M) logM
3) Сортировать только другой список и раздел, время, которое я не выяснил, но в случае N и M аналогично, оно должно быть больше, чем метод 1 или 2, а в случае N достаточно крошечный должен быть меньше, чем методы 1 или 2.
Этот ответ относится к случаю, когда input изначально случайный (не отсортированный) и test.size() меньше чем input.size(), которая является наиболее распространенной ситуацией.
Предположим, что есть только одно тестовое значение. Тогда вам нужно только разделить input по отношению к этой стоимости а также получить верхнюю (нижнюю) границу нижней (верхней) части, чтобы вычислить соответствующий процентиль. Это намного быстрее, чем полная сортировка на входе (которую быстрая сортировка реализует как рекурсию разделов).
Если test.size()>1тогда вы сначала сортируете test (в идеале, test уже отсортирован, и вы можете пропустить этот шаг), а затем продолжить работу с тестовыми элементами в порядке возрастания, каждый раз отделяя только верхнюю часть от предыдущего раздела. Так как мы также отслеживаем нижнюю границу верхнего раздела (а также верхнюю границу нижнего раздела), мы можем определить, нет ли входных данных между последовательными тестовыми элементами, и избежать разбиения.
Этот алгоритм должен быть почти оптимальным, так как ненужная информация не генерируется (как это было бы с полным видом input).
Если последующее разбиение разбивает входные данные примерно пополам, алгоритм будет оптимальным. Это может быть аппроксимировано, если действовать не в порядке возрастания test, но путем последующего деления пополам testто есть начиная с медианного тестового элемента, затем первого & третий квартиль и т.д ..