Scans and reduction functions

Ouverte
  • Quelque chose ne va pas ?
#3,340 1 commentaire 2 réactions 0 personnes assignées Voir sur GitHub

Les mainteneurs répondent en général sous 1 jour

Personne n'a encore pris cette issue.

Évaluation

Difficulté
5/5
Temps estimé
Plus d'une semaine
Accessibilité débutants
35/100
Type d'issue
Fonctionnalité
Clarté
À clarifier
Activité
Calme
Stack technique
cpp
Domaine
backend

Piste de recherche

Commencez par l’issue connexe #3339, puis examinez la sémantique proposée pour fold_left, fold_right, reduce et scan, ainsi que les références liées sur les algorithmes parallèles. Avant l’implémentation, clarifiez quelles fonctions Stan doit prendre en charge ainsi que leurs exigences d’API et d’évaluation ; le travail est considéré comme terminé lorsque le périmètre est convenu et que les fonctions sélectionnées sont implémentées de manière cohérente.

Rédigé par le modèle d'indexation à partir du texte de l'issue.

Description

feature new function

Related to #3339, there are also common higher-order functions that return a different type than their input.

Some common options are:

  • fold_left(F, T, ...) => f(f(f(f(T[0], T[1]), T[2]), ...), T[3]) (sometimes, rather than starting at T[0], an extra 'init' argument is passed)
  • fold_right, which is the same idea but with the opposite association f(T[0], f(T[1], ...f(T[N], init)))
  • reduce, which is defined such that it is equivalent to the above when the f is associative but does not explicitly state an order of evaluation. The cool thing about reduce is it can be parallelized, c.f. foldl and foldr Considered Slightly Harmful, and More Fun with Moniods
  • scan, which returns a cumulative evaluation scan(f, T, ...) => [T[1], f(T[1], T[2]), f(f(T[1], T[2]), T3), ...]. Note that scan can also be parallelized when f is associative, c.f. Prefix Sums and their Applications. (Note: even though reduce(f, T, ...) == scan(f, T, ...)[N], the ideal parallelization algorithms actually differ)

There are other functions of questionable value to Stan in this family, like folding_map which returns both a carry and a mapped container (this is, confusingly, what JAX calls scan. Scans a-la Blelloch as described above are called associative_scan in JAX)

Langage dominant
C++
Étoiles
845
Forks
225
Merge moyen
4 j 21 h
PR mergées (30 j)
13

Préparer son environnement

Par où commencer

  1. Lisez l'issue en entier, puis le guide de contribution du projet.
  2. Signalez en commentaire que vous la prenez — cela évite que deux personnes fassent le même travail.
  3. Forkez le dépôt et travaillez sur une branche.
  4. Ouvrez une pull request qui référence le numéro de l'issue.

Autres issues de stan-dev/math

Toutes les issues de stan-dev/math

Issues similaires

Plus d'issues C++

Recevez les nouvelles issues par e-mail

Un résumé court des issues GitHub adaptées aux débutants.