Каково практическое использование "partial_sum" в STL?

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

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

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

1. Рекурсивно пометьте используемые объекты и заполните логический массив.
2. Используйте remove_if, чтобы уплотнить отмеченные объекты до начала пула.
3. Use partial_sum over the Boolean values to generate a table of pointers/indexes into the new pool.
   • This works because the Nth marked object has N preceding 1's in the array and acquires pool index N.
4. Снова проведите по пулу и замените каждую ссылку, используя таблицу переназначения.

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

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

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

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

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

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

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

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

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

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

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

Пример использования в личных целях: выбор колеса рулетки

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

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

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

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

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

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

Личный вариант использования: промежуточный этап подсчета сортировки из 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

Вы можете построить «скользящую сумму» (предшественницу скользящей средней):

template <class T>
void moving_sum (const vector<T>& in, int num, vector<T>& out)
{
    // cummulative sum
    partial_sum (in.begin(), in.end(), out.begin());

    // shift and subtract
    int j;
    for (int i = out.size() - 1; i >= 0; i--) {
        j = i - num;
        if (j >= 0)
            out[i] -= out[j];
    }    
}

А затем вызовите его с помощью:

vector<double> v(10);
// fill in v
vector<double> v2 (v.size());
moving_sum (v, 3, v2);

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

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

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

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

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

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

Но помимо всего этого, есть третий (несколько менее эффективный) вариант, который я хотел изучить. Это похоже на случай трех циклов, только мы добавляем соседние числа, чтобы избежать такой большой работы. Идея состоит в том, что нет необходимости добавлять 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

Таким образом, мы получаем все возможные подстроки, начиная с index = 0 и заканчивая indexes = 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 ().

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

Остальные шаги через цикл for и преобразование (data + i, data + size, data + i, bind2nd (минус ‹TYPE› (), data [i-1])) < / em>.