Quelles sont les utilisations pratiques de la «sum partielle» de STL?

Je l’ai utilisé pour réduire l’utilisation de la mémoire d’un simple ramasse-miettes dans mon interpréteur de lambda calcul.

Le pool de CPG est un tableau d’objects de taille identique. L’objective est d’éliminer les objects qui ne sont pas liés à d’autres objects et de condenser les objects restants au début du tableau. Comme les objects sont déplacés en mémoire, chaque lien doit être mis à jour. Cela nécessite une table de remappage d’objects.

partial_sum permet à la table d’être stockée au format compressé (aussi peu qu’un bit par object) jusqu’à ce que le balayage soit terminé et que la mémoire soit libérée. Les objects étant petits, l’utilisation de la mémoire est considérablement réduite.

1. Marque récursivement les objects utilisés et remplit le tableau booléen.
2. Utilisez remove_if pour condenser les objects marqués au début du pool.
3. Utilisez partial_sum sur les valeurs booléennes pour générer une table de pointeurs / index dans le nouveau pool.
   • Cela fonctionne parce que le Nème object marqué a N précédant 1 dans le tableau et acquiert l’index de pool N.
4. Balayez à nouveau le pool et remplacez chaque lien à l’aide du tableau de remappage.

Il est particulièrement intéressant pour le cache de données de placer la table de reconfiguration dans la mémoire libérée, donc toujours chaude.

Une chose à noter à propos de la sum partielle est que c’est l’opération qui annule la différence adjacente, à l’instar de – undoes +. Ou mieux encore si vous vous souvenez du calcul de la manière dont la différenciation annule l’intégration. Mieux, car la différence adjacente est essentiellement une différenciation et la sum partielle, une intégration.

Supposons que vous simuliez une voiture et que vous ayez à connaître à chaque pas la position, la vitesse et l’accélération. Il vous suffit de stocker une de ces valeurs pour pouvoir calculer les deux autres. Supposons que vous stockiez la position à chaque pas de temps, vous pouvez prendre la différence adjacente de la position pour donner la vitesse et la différence adjacente de la vitesse pour donner l’accélération. Alternativement, si vous enregistrez l’accélération, vous pouvez utiliser la sum partielle pour donner la vitesse et la sum partielle de la vitesse pour indiquer la position.

La sum partielle fait partie de ces fonctions qui n’apparaissent pas trop souvent pour la plupart des gens, mais qui sont extrêmement utiles lorsque vous trouvez la bonne situation. Un peu comme le calcul.

La dernière fois que je l’aurais (utilisé) c’est lors de la conversion d’une dissortingbution de probabilité discrète (un tableau de p (X = k)) en une dissortingbution cumulative (un tableau de p (X <= k)). Pour sélectionner une fois dans la distribution, vous pouvez choisir un nombre de [0-1) au hasard, puis effectuer une recherche binaire dans la distribution cumulative.

Ce code n’était cependant pas en C ++, alors j’ai fait la sum partielle moi-même.

Vous pouvez l’utiliser pour générer une suite de nombres de plus en plus monotone. Par exemple, ce qui suit génère un vector contenant les nombres 1 à 42:

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

Est-ce un cas d’usage quotidien? Probablement pas, même si je l’ai trouvé utile à plusieurs resockets.

Vous pouvez également utiliser std::partial_sum pour générer une liste de factorielles. (Ceci est encore moins utile, cependant, car le nombre de factorielles pouvant être représentées par un type de données entier typique est assez limité. C’est amusant, cependant :-D)

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

Cas d’utilisation personnelle: Roulette-Wheel-Selection

J’utilise partial_sum dans un algorithme de sélection de roue de roulette ( texte du lien ). Cet algorithme choisit aléatoirement des éléments d’un conteneur avec une probabilité qui est linéaire à une valeur donnée à l’avance.

Parce que tous mes éléments à choisir apportent une valeur non nécessairement normalisée, j’utilise l’algorithme partial_sum pour construire quelque chose comme une “roulette”, car je résume tous les éléments. Ensuite, j’ai choisi une variable aléatoire dans cette plage (le dernier partial_sum est la sum de tous) et j’utilise stl::lower_bound pour rechercher “la roue” où ma recherche aléatoire a atterri. L’élément renvoyé par l’algorithme lower_bound est celui qui a été choisi.

Outre l’avantage d’un code clair et expressif avec l’utilisation de partial_sum , je pourrais également gagner en rapidité lorsque je teste le mode parallèle GCC qui apporte des versions parallélisées pour certains algorithmes, dont l’un est le partial_sum ( lien texte ).

Une autre utilisation que je connaisse: L’une des primitives algorithmiques les plus importantes du traitement en parallèle (mais peut-être un peu éloignée de STL)

Si vous êtes intéressé par les algorithmes optimisés lourds qui utilisent partial_sum (dans ce cas, peut-être plus de résultats sous les synonymes “scan” ou “prefix_sum”), plutôt que d’aller à la communauté des algorithmes parallèles. Ils en ont besoin tout le temps. Vous ne trouverez pas d’algorithme de sorting parallèle basé sur quicksort ou mergesort sans l’utiliser. Cette opération est l’une des primitives parallèles les plus importantes utilisées. Je pense qu’il est le plus couramment utilisé pour calculer les décalages dans les algorithmes dynamics. Pensez à une étape de partition dans quicksort, qui est divisée et transmise aux threads parallèles. Vous ne connaissez pas le nombre d’éléments dans chaque emplacement de la partition avant de le calculer. Vous avez donc besoin de compensations pour tous les threads pour un access ultérieur.

Vous trouverez peut-être plus d’informations dans le sujet d’actualité du traitement des GPU . Vous trouverez au chapitre 39 un court article sur CUDA de Nvidia et la primitive de scan, avec quelques exemples d’application . Somme de préfixes parallèles (Scan) avec CUDA .

Vous pouvez construire une “sum mobile” (précurseur d’une moyenne mobile):

 template  void moving_sum (const vector& in, int num, vector& 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]; } } 

Et puis appelez-le avec:

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

Vous savez, j’ai effectivement utilisé partial_sum () une fois … C’est ce petit problème intéressant qui m’a été demandé lors d’un entretien d’embauche. Je l’ai tellement apprécié que je suis rentré chez moi et que j’ai codé le résultat.

Le problème était le suivant: à partir d’une séquence séquentielle d’entiers, trouver la sous-séquence la plus courte avec la valeur la plus élevée. Par exemple:

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

Nous trouverions la sous-séquence [1,4]

Maintenant, la solution évidente consiste à exécuter avec 3 boucles for , en effectuant une itération sur tous les débuts et fins possibles, et en additionnant la valeur de chaque sous-séquence possible. Inefficace, mais rapide à coder et difficile à commettre des erreurs. (Surtout quand la troisième boucle for est juste accumulée (début, fin, 0) .)

La solution correcte implique une approche diviser pour mieux régner / de bas en haut. Par exemple, divisez l’espace du problème en deux et calculez pour chaque moitié la plus grande sous-séquence de cette section, la plus grande sous-séquence incluant le numéro de départ, la plus grande sous-séquence comprenant le dernier nombre et la sous-séquence de la totalité de la section. Armés de ces données, nous pouvons alors combiner les deux moitiés sans aucune évaluation supplémentaire de l’une ou l’autre. Il est évident que les données pour chaque moitié peuvent être calculées en divisant chaque moitié en moitiés (quarts), chaque sortingmestre en moitiés (huitièmes), et ainsi de suite jusqu’à ce que nous ayons des cas simples de singleton. C’est tout à fait efficace.

Mais tout cela mis à part, il y a une troisième option (un peu moins efficace) que je voulais explorer. Cela ressemble au cas 3-pour-boucle , seulement nous ajoutons les nombres adjacents pour éviter autant de travail. L’idée est qu’il n’y a pas besoin d’append a + b, a + b + c et a + b + c + d lorsque nous pouvons append t1 = a + b, t2 = t1 + c et t3 = t2 + d. C’est un compromis entre espace et calcul. Cela fonctionne en transformant la séquence:

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

Nous donnant ainsi toutes les sous-chaînes possibles commençant à index = 0 et finissant à index = 0,1,2,3,4.

Ensuite, nous parcourons cet ensemble en soustrayant les points de “départ” possibles successifs …

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

Nous donnant ainsi les valeurs (sums) de toutes les sous-séquences possibles.

Nous pouvons trouver la valeur maximale de chaque itération via max_element () .

La première étape est facilement réalisée via partial_sum () .

Les étapes restantes via une boucle for et une transformation (données + i, données + taille, données + i, bind2nd (moins (), données [i-1])) .

Clairement O (N ^ 2). Mais toujours intéressant et amusant …

Les sums partielles sont souvent utiles dans les algorithmes parallèles. Considérons le code

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

Si vous voulez paralléliser ce code, vous devez connaître les sums partielles. J’utilise la version parallèle de partial_sum de GNU pour quelque chose de très similaire.

J’utilise souvent la sum partielle, non pas pour résumer, mais pour calculer la valeur actuelle dans la séquence en fonction de la précédente.

Par exemple, si vous intégrez une fonction. Chaque nouvelle étape est une étape précédente, vt += dvdt ou vt = integrate_step(dvdt, t_prev, t_prev+dt); .

Cas d’utilisation personnel: étape intermédiaire du sorting du sorting du 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 

Dans les méthodes bayésiennes non paramésortingques, il existe une étape Metropolis-Hastings (par observation) qui détermine l’échantillonnage d’un cluster nouveau ou existant. Si un cluster existant doit être échantillonné, cela doit être fait avec des poids différents. Ces vraisemblances pondérées sont simulées dans l’exemple de code suivant.

 #include  #include  #include  int main() { std::default_random_engine generator(std::random_device{}()); std::uniform_real_dissortingbution dissortingbution(0.0,1.0); int K = 8; std::vector 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 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 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; } 

Notez que ce n'est pas différent de la réponse de https://stackoverflow.com/users/13005/steve-jessop . Il est ajouté pour donner un peu plus de contexte à une situation particulière (méthodes méthodiques bayésiennes non paramésortingques, par exemple les algorithmes de Neal utilisant le processus de Dirichlet comme auparavant) et le code qui utilise partial_sum en combinaison avec lower_bound .