Каковы практические применения для STL 'частичный_сум'?

Question

Что / где практическое использование алгоритма partial_sum в STL ?

Какие еще есть интересные / нетривиальные примеры или варианты использования?

Answer 1

Я использовал его, чтобы уменьшить использование памяти простым сборщиком мусора в моем игрушечном интерпретаторе лямбда-исчисления.

Пул GC - это массив объектов одинакового размера. Цель состоит в том, чтобы исключить объекты, которые не связаны с другими объектами, и объединить оставшиеся объекты в начало массива. Поскольку объекты перемещаются в памяти, каждая ссылка должна быть обновлена. Это требует таблицы переназначения объекта.

partial_sum позволяет хранить таблицу в сжатом формате (всего один бит на объект) до тех пор, пока развертка не будет завершена и память не будет освобождена. Поскольку объекты маленькие, это значительно уменьшает использование памяти.

1. Рекурсивно пометить использованные объекты и заполнить логический массив.
2. Используйте remove_if, чтобы сжать отмеченные объекты в начале пула.
3. Используйте partial_sum поверх логических значений, чтобы сгенерировать таблицу указателей / индексов в новом пуле.
   • Это работает, потому что N-й помеченный объект имеет N предшествующих 1 в массиве и получает индекс пула N.
4. Снова пролистайте пул и замените каждую ссылку с помощью таблицы переназначения.

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

Answer 2

Следует обратить внимание на частичную сумму в том, что эта операция отменяет смежную разницу так же, как - отменяет +.Или еще лучше, если вы помните исчисление, как дифференциация отменяет интеграцию.Лучше, потому что смежная разница - это, по сути, дифференциация, а частичная сумма - интеграция.

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

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

Answer 3

В последний раз, когда я (использовал бы), использовал его при преобразовании дискретного распределения вероятностей (массив p (X = k)) в кумулятивное распределение (массив p (X <= k)).Чтобы выбрать один раз из распределения, вы можете выбрать число из [0-1) случайным образом, а затем выполнить двоичный поиск в накопительном распределении. </p>

Однако этого кода не было в C ++, поэтому я сделал частичную суммуя.

Answer 4

Вы можете использовать его для генерации монотонно возрастающей последовательности чисел.Например, следующее генерирует vector, содержащее числа от 1 до 42:

std::vector<int> v(42, 1);
std::partial_sum(v.begin(), v.end(), v.begin());

Это случай повседневного использования?Наверное, нет, хотя я нашел это полезным в нескольких случаях.

Вы также можете использовать std::partial_sum для создания списка факториалов.(Это даже менее полезно, так как число факториалов, которые могут быть представлены типичным целочисленным типом данных, довольно ограничено. Хотя это забавно:

Answer 5

Индивидуальный вариант использования: Выбор колеса рулетки

Я использую partial_sum в алгоритме выбора колеса рулетки ( текст ссылки ). Этот алгоритм случайным образом выбирает элементы из контейнера с вероятностью, которая линейна некоторому значению, данному до него.

Поскольку все мои элементы на выбор приносят необязательно нормализованное значение, я использую алгоритм partial_sum для создания чего-то вроде "колеса рулетки", потому что я суммирую все элементы. Затем я выбрал случайную переменную в этом диапазоне (последняя partial_sum - сумма всех) и использую stl::lower_bound для поиска «колеса», где мой случайный поиск приземлился. Элемент, возвращаемый алгоритмом lower_bound, является выбранным.

Помимо преимущества ясного и выразительного кода с использованием partial_sum, я мог бы также получить некоторую скорость, экспериментируя с параллельным режимом GCC , который приносит распараллеленные версии для некоторых алгоритмов, и один из них - part_sum ( текст ссылки ).

Другое известное мне использование: один из наиболее важных алгоритмических примитивов в параллельной обработке (но, возможно, немного в стороне от STL)

Если вас интересуют сильно оптимизированные алгоритмы, использующие partial_sum (в этом случае может быть больше результатов под синонимами "scan" или "prefix_sum"), чем переходить к сообществу параллельных алгоритмов. Им это нужно постоянно. Вы не найдете алгоритм параллельной сортировки, основанный на быстрой сортировке или mergesort без его использования. Эта операция является одним из наиболее важных используемых параллельных примитивов. Я думаю, что это чаще всего используется для расчета смещений в динамических алгоритмах. Подумайте о шаге разделения в быстрой сортировке, который разделяется и подается в параллельные потоки. Вы не знаете количество элементов в каждом слоте раздела до его вычисления. Таким образом, вам понадобятся некоторые смещения для всех потоков для последующего доступа.

Возможно, вы найдете больше информации в актуальной теме обработки GPU . Одна короткая статья о Nvidia CUDA и о примитиве сканирования с несколькими примерами приложений, которые вы найдете в Глава 39. Параллельная сумма префикса (сканирование) с помощью CUDA .

Answer 6

В непараметрических байесовских методах есть шаг Метрополиса-Гастингса (для каждого наблюдения), который определяет выборку нового или существующего кластера.Если необходимо выбрать существующий кластер, это нужно сделать с разными весами.Эти взвешенные вероятности моделируются в следующем примере кода.

#include <random>                                                                                                       
#include <iostream>                                                                                                     
#include <algorithm>                                                                                                    

int main() {                                                                                                            

    std::default_random_engine generator(std::random_device{}());                                                       
    std::uniform_real_distribution<double> distribution(0.0,1.0);                                                       

    int K = 8;                                                                                                          

    std::vector<double> weighted_likelihood(K);                                                                         
    for (int i = 0; i < K; ++i) {                                                                                       
        weighted_likelihood[i] = i*10;                                                                                  
    }                                                                                                                   
    std::cout << "Weighted likelihood: ";                                                                               
    for (auto i: weighted_likelihood) std::cout << i << ' ';                                                            
    std::cout << std::endl;                                                                                             

    std::vector<double> cumsum_likelihood(K);                                                                           
    std::partial_sum(weighted_likelihood.begin(), weighted_likelihood.end(), cumsum_likelihood.begin());                

    std::cout << "Cumulative sum of weighted likelihood: ";                                                             
    for (auto i: cumsum_likelihood) std::cout << i << ' ';                                                              
    std::cout << std::endl;                                                                                             

    std::vector<int> frequency(K);                                                                                      

    int N = 280000;                                                                                                     
    for (int i = 0; i < N; ++i) {                                                                                       
        double pick = distribution(generator) * cumsum_likelihood.back();                                               

        auto lower = std::lower_bound(cumsum_likelihood.begin(), cumsum_likelihood.end(), pick);                        
        int index = std::distance(cumsum_likelihood.begin(), lower);                                                    
        frequency[index]++;                                                                                             
    }                                                                                                                   

    std::cout << "Frequencies: ";                                                                                       
    for (auto i: frequency) std::cout << i << ' ';                                                                      
    std::cout << std::endl;                                                                                             

}

Обратите внимание, что это не отличается от ответа https://stackoverflow.com/users/13005/steve-jessop. Это добавлено, чтобы дать немного больше контекста о конкретной ситуации (непараметрические байесовские методы, например, алгоритмы Нила с использованием Дирихлекак прежде) и фактический код, который использует partial_sum в сочетании с lower_bound.

Answer 7

Персональный вариант использования: промежуточный шаг в подсчете сортировки из CLRS:

COUNTING_SORT (A, B, k)

for i ← 1 to k do
    c[i] ← 0
for j ← 1 to n do
    c[A[j]] ← c[A[j]] + 1
//c[i] now contains the number of elements equal to i


// std::partial_sum here
for i ← 2 to k do
    c[i] ← c[i] + c[i-1]


// c[i] now contains the number of elements ≤ i
for j ← n downto 1 do
    B[c[A[i]]] ← A[j]
    c[A[i]] ← c[A[j]] - 1

Answer 8

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

Например, если вы интегрируете функцию. Каждый новый шаг - это предыдущий шаг, vt += dvdt или vt = integrate_step(dvdt, t_prev, t_prev+dt);.

Answer 9

Частичные суммы часто полезны в параллельных алгоритмах. Рассмотрим код

for (int i=0; N>i; ++i) {
  sum += x[i];
  do_something(sum);
}

Если вы хотите распараллелить этот код, вам нужно знать частичные суммы. Я использую параллельную версию GNU part_sum для чего-то очень похожего.

Answer 10

Знаете, я действительно однажды использовал partal_sum () ... Это была небольшая интересная проблема, которую мне задали на собеседовании.Мне это очень понравилось, я пошел домой и закодировал его.

Проблема заключалась в следующем: учитывая последовательную последовательность целых чисел, найдите самую короткую подпоследовательность с наибольшим значением.Например:

Value: -1  2  3 -1  4 -2 -4  5
Index:  0  1  2  3  4  5  6  7

Мы нашли бы подпоследовательность [1,4]

Теперь очевидное решение состоит в том, чтобы запустить с 3 для циклов, повторяя все возможныеначинается и заканчивается, и суммирует значение каждой возможной подпоследовательности по очереди.Неэффективно, но быстро кодируется и сложно ошибиться.(Особенно, когда третий для цикла просто накапливается (начало, конец, 0) .)

Правильное решение включает в себя разделяй и властвуй / снизу вверхподход.Например, разделите проблемное пространство пополам, и для каждой половины вычислите самую большую подпоследовательность, содержащуюся в этом разделе, самую большую подпоследовательность, включающую начальный номер, самую большую подпоследовательность, включающую конечный номер, и подпоследовательность всего раздела.Вооружившись этими данными, мы можем затем объединить две половины без какой-либо дальнейшей оценки одной из них.Очевидно, что данные для каждой половины могут быть вычислены путем дальнейшего разбиения каждой половины на половины (четверти), каждой четверти на половины (восьмые) и так далее, пока у нас не появятся тривиальные единичные случаи.Все это довольно эффективно.

Но, кроме этого, есть третий (несколько менее эффективный) вариант, который я хотел изучить.Это похоже на случай 3-for-loop , только мы добавляем соседние числа, чтобы избежать такой большой работы.Идея состоит в том, что нет необходимости добавлять a + b, a + b + c и a + b + c + d, когда мы можем добавить t1 = a + b, t2 = t1 + c и t3 = t2 + d.Это компромисс между пространством и вычислениями.Он работает путем преобразования последовательности:

Index: 0 1 2  3  4
FROM:  1 2 3  4  5
  TO:  1 3 6 10 15

Таким образом, давая нам все возможные подстроки, начиная с индекса = 0 и заканчивая индексами = 0,1,2,3,4.

Затем мыитерируйте по этому набору, вычитая возможные возможные «начальные» точки ...

FROM:  1 3 6 10 15
  TO:  - 2 5  9 14
  TO:  - - 3  7 12
  TO:  - - -  4  9
  TO:  - - -  -  5

, тем самым давая нам значения (суммы) всех возможных подпоследовательностей.

Мы можем найти максимальное значениекаждая итерация с помощью max_element () .

Первый шаг легче всего выполнить с помощью part_sum () .

Остальные шаги с помощью для цикла и преобразования (data + i, data + size, data + i, bind2nd (минус (), data [i-1])) * .

Ясно O (N ^ 2).Но все равно интересно и весело ...