Что/где - практическое использование алгоритма partial_sum в STL?
Какие еще интересные/нетривиальные примеры или варианты использования?
Что такое практическое использование для STL 'partial_sum'?
Ответ 1
Я использовал его, чтобы уменьшить использование памяти простейшего сборщика мусора с меткой в моем интерпретаторе калькулятора лямбда-игрушки.
Пул GC представляет собой массив объектов одинакового размера. Цель состоит в том, чтобы исключить объекты, которые не связаны с другими объектами, и сконденсировать оставшиеся объекты в начале массива. Поскольку объекты перемещаются в памяти, каждая ссылка должна быть обновлена. Это требует таблицы переназначения объекта.
partial_sum позволяет хранить таблицу в сжатом формате (всего лишь один бит на объект) до тех пор, пока развертка не будет завершена и память не будет освобождена. Поскольку объекты небольшие, это значительно сокращает использование памяти.
- Рекурсивно маркировать используемые объекты и заполнять Boolean массив.
- Используйте
remove_ifдля уплотнения помеченных объектов в начале пула. - Используйте
partial_sumнад булевыми значениями, чтобы создать таблицу указателей/индексов в новый пул.- Это работает, потому что N-й отмеченный объект имеет N предшествующих 1 в массиве и получает индекс пула N.
- Снова разверните пул и замените каждую ссылку, используя таблицу переназначения.
Это особенно удобно для кэша данных, чтобы поместить таблицу переназначения в только что освобожденную, тем не менее горячую память.
Ответ 2
Одно замечание о частичной сумме состоит в том, что это операция, которая так же отменяет смежную разницу - отменяет+. Или еще лучше, если вы помните исчисление, как дифференциация отменяет интеграцию. Лучше, потому что смежное различие существенно дифференцируется, а частичная сумма - это интеграция.
Скажем, у вас есть симуляция автомобиля, и на каждом шаге вам нужно знать положение, скорость и ускорение. Вам нужно сохранить только одно из этих значений, так как вы можете вычислить два других. Скажем, вы сохраняете позицию на каждом временном шаге, вы можете принять смежную разницу положения, чтобы дать скорость и смежную разницу скорости, чтобы дать ускорение. В качестве альтернативы, если вы сохраняете ускорение, вы можете взять частичную сумму, чтобы дать скорость, а частичная сумма скорости дает положение.
Частичная сумма является одной из тех функций, которая не возникает слишком часто для большинства людей, но чрезвычайно полезна, когда вы находите правильную ситуацию. Очень похоже на исчисление.
Ответ 3
В прошлый раз, когда я использовал (использовал бы) это преобразование дискретного распределения вероятности (массив p (X = k)) в кумулятивное распределение (массив p (X <= k)). Чтобы выбрать один раз из дистрибутива, вы можете выбрать номер из [0-1) случайным образом, а затем двоичный поиск в кумулятивное распределение.
Этот код не был на С++, поэтому я сам сделал частичную сумму.
Ответ 4
Вы можете использовать его для генерации монотонно возрастающей последовательности чисел. Например, следующее генерирует символ 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>());
Ответ 5
Личный пример использования: выбор колеса рулетки
Я использую partial_sum в алгоритме выбора рулевого колеса (текст ссылки). Этот алгоритм произвольно удаляет элементы из контейнера с вероятностью, которая является линейной до некоторого значения, заданного перед удалением.
Поскольку все мои элементы выбирают из необходимости не обязательно нормализованного значения, я использую алгоритм partial_sum для построения чего-то вроде "рулетки-рулетки", потому что я суммирую все элементы. Затем я выбрал случайную переменную в этом диапазоне (последняя partial_sum - это сумма всех) и используйте stl::lower_bound для поиска "колеса", где приземлился мой случайный поиск. Элемент, возвращаемый алгоритмом lower_bound, является выбранным.
Помимо преимущества четкого и выразительного кода с использованием partial_sum, я мог бы также получить некоторую скорость при экспериментировании с GCC параллельно режим, который привносит параллельные версии для некоторых алгоритмов, а один из них - текст ссылки partial_sum ().
Другое использование, которое я знаю: один из наиболее важных алгоритмических примитивов в параллельной обработке (но, возможно, немного от STL)
Если вас интересуют тяжелые оптимизированные алгоритмы, которые используют partial_sum (в этом случае может быть больше результатов под синонимами "scan" или "prefix_sum" ), чем перейти к сообществу параллельных алгоритмов. Они нуждаются в нем все время. Вы не найдете алгоритм параллельной сортировки, основанный на quicksort или mergesort без использования. Эта операция является одним из наиболее важных используемых параллельных примитивов. Я думаю, что он наиболее часто используется для вычисления смещений в динамических алгоритмах. Подумайте о шаге раздела в quicksort, который разбивается и подается на параллельные потоки. Вы не знаете количество элементов в каждом слоте раздела перед его вычислением. Поэтому вам нужны смещения для всех потоков для последующего доступа.
Возможно, вы найдете больше информации в актуальной теме GPU. Одна короткая статья о Nvidia CUDA и примитиве сканирования с несколькими примерами приложений вы найдете в Глава 39. Сумма параллельного префикса (сканирование) с CUDA.
Ответ 6
Вы можете создать "движущуюся сумму" (предшественник скользящей средней):
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);
Ответ 7
Знаешь, я действительно использовал partial_sum() один раз... Это была интересная небольшая проблема, которую меня попросили на собеседовании. Мне это очень понравилось, я пошел домой и закодировал его.
Проблема заключалась в следующем: учитывая последовательную последовательность целых чисел, найдите кратчайшую подпоследовательность с наивысшим значением. Например. Дано:
Value: -1 2 3 -1 4 -2 -4 5
Index: 0 1 2 3 4 5 6 7
Мы найдем подпоследовательность [1,4]
Теперь очевидное решение состоит в том, чтобы запустить с 3 для циклов, итерации по всем возможным запускам и концам, и в свою очередь добавить значение каждой возможной подпоследовательности. Неэффективен, но быстро компилируется и трудно совершать ошибки. (Особенно, когда третья для цикла просто накапливается (начало, конец, 0).)
Правильное решение включает подход "разделяй и властвуй". Например. Разделите пространство проблем пополам и для каждой половины вычислите самую большую подпоследовательность, содержащуюся в этом разделе, самую большую подпоследовательность, включающую начальное число, самую большую подпоследовательность, включая конечное число, и всю подпоследовательность раздела. Вооружившись этими данными, мы можем затем объединить две половинки вместе без какой-либо дополнительной оценки. Очевидно, что данные для каждой половины могут быть вычислены путем дальнейшего разбиения каждой половины на половинки (четверти), каждую четверть на половину (восьмые) и т.д., Пока у нас не будет тривиальных случаев синглтона. Все это довольно эффективно.
Но все это в стороне, есть третий (несколько менее эффективный) вариант, который я хотел исследовать. Он похож на случай с 3-мя петлями, только добавляем смежные числа, чтобы избежать такой работы. Идея состоит в том, что нет необходимости добавлять 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().
Первый шаг легче всего выполнить с помощью partial_sum().
Остальные шаги через цикл for и преобразование (данные + i, данные + размер, данные + i, bind2nd (минус <TYPE> (), данные [i-1])).
Ясно, что O (N ^ 2). Но все же интересно и весело...
Ответ 8
Частичные суммы часто полезны в параллельных алгоритмах. Рассмотрим код
for (int i=0; N>i; ++i) {
sum += x[i];
do_something(sum);
}
Если вы хотите распараллелить этот код, вам нужно знать частичные суммы. Я использую параллельную версию part_sum для GNU для чего-то очень похожего.
Ответ 9
Я часто использую частичную сумму, чтобы не суммировать, а вычислять текущее значение в последовательности в зависимости от предыдущего.
Например, если вы интегрируете функцию. Каждый новый шаг - это предыдущий шаг, vt += dvdt или vt = integrate_step(dvdt, t_prev, t_prev+dt);.
Ответ 10
Личный пример использования: промежуточный шаг в сортировке count из 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
Ответ 11
В непараметрических байесовских методах существует шаг Metropolis-Hastings (за наблюдение), который определяет образец нового или существующего кластера. Если необходимо отбирать существующий кластер, это нужно делать с разными весами. Эти взвешенные правдоподобия моделируются в следующем примере кода.
#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.