C++ Fast Percentile Calculation

Question

Я пытаюсь написать функцию процентиля, которая принимает 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 и испытаний может быть от 2000 до 30000.

Существуют ли существующие библиотеки, которые могут вычислять процентили, как показано выше (или аналогичные)? Если нет, как я могу сделать вышеприведенный код быстрее?

Answer 1

Линейный поиск по каждому элементу испытаний будет основным временем, если оба из них являются большими.

Когда Distr намного больше, гораздо быстрее выполнять двоичный поиск вместо линейного. Существует бинарный алгоритм поиска, доступный в std. Вам не нужно писать.

Когда Тесты имеют почти такой же размер, как и для определения или больше, быстрее выполнять индексные типы тестов, а затем последовательно сортировать по двум отсортированным спискам вместе, сохраняя результаты, а затем выводить сохраненные результаты в следующий проход.

Редактировать: Я вижу ответ от Csaba Balint, который дает более подробную информацию о том, что я подразумевал под «последовательностью через два отсортированных списка вместе».

Изменить: Основные методы обсуждаются являются:
1) Сортировка оба списка, а затем процесс линейно вместе, время NlogN + MlogM
2) Сортировка только один список и двоичный поиск, время (N + M) logM
3) Сортируйте только другой список и раздел, время, которое я не выяснил, но в случае с N и M схожу, он должен быть больше, чем метод 1 или 2, а в случае N достаточно крошечный имеет быть меньше, чем методы 1 или 2.

Answer 2

Существует линейный алгоритм для вашей проблемы (линейный логарифмический график в обоих размерах). Вам нужно отсортировать оба вектора, а затем пройти через два итератора (itDistr, itTest). Есть три варианта:

1. * itDistr < * itTest

Здесь, у вас нет ничего, за исключением приращения itDistr.

2. * itDistr> = * itTest

Это тот случай, когда вы нашли тестовый случай, когда * itTest является элементом интервала [ *(itDistr-1), *itDistr). Таким образом, вы должны сделать интерполяцию, которую вы использовали (линейный), а затем увеличиваете itTest.

Третья возможность заключается в том, что любой из них достигает конца своего вектор-контейнера. Вы также должны определить, что происходит в начале и в и, и зависит от того, как вы определяете распределение из серии ваших чисел.

Существуют ли существующие библиотеки, которые могут вычислять процентили, как показано выше (или аналогичные)?

Возможно, но его легко реализовать, и вы можете иметь точный контроль над методом интерполяции.

Answer 3

Этот ответ относится к случаю, когда input изначально случайный (не отсортированный) и test.size() меньше, чем input.size(), что является наиболее распространенной ситуацией.

Предположим, что существует только одно тестовое значение. Затем вам нужно только разбить input на это значение и получить верхнюю (нижнюю) границу нижнего (верхнего) пассажа для вычисления соответствующего процентиля. Это намного быстрее, чем полная сортировка на входе (что quicksort реализует как рекурсию разделов).

Если test.size()>1, то сортировать test (в идеале, test уже отсортирован, и вы можете пропустить этот шаг), а затем приступить к тестированию элементов в возрастающем порядке, каждый раз, когда только разбивая верхнюю часть из предыдущего раздела. Так как мы также отслеживаем нижнюю границу верхнего раздела (а также верхнюю границу нижнего раздела), мы можем определить, нет ли входных данных между последовательными тестовыми элементами и избежать разделения.

Этот алгоритм должен быть почти оптимальным, так как никакой ненужной информации не генерируется (как это было бы с полным видом input).

Если последующее разбиение разбивает вход примерно на половину, алгоритм будет оптимальным. Это может быть аппроксимирована исходя не в порядке возрастания test, а последующее двукратное сокращение test, то есть начиная с медианой тестового элемента, то первый & третий квартиль и т.д ..

Answer 4

Я хотел бы сделать что-то вроде

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 сортируется и сделать бинарный поиск вместо (с использованием lOWER_BOUND).