Scans and reduction functions

Aperta
  • Qualcosa non va?
#3,340 1 commento 2 reazioni 0 assegnatari Vedi su GitHub

I maintainer di solito rispondono entro 1 giorno

Nessuno ha ancora preso questa issue.

Valutazione

Difficoltà
5/5
Tempo stimato
Più di una settimana
Idoneità per principianti
35/100
Tipo di issue
Funzionalità
Chiarezza
Da chiarire
Stato di attività
Tranquilla
Stack tecnologico
cpp
Ambito
backend

Direzione di ricerca

Inizia con la issue correlata #3339, quindi esamina la semantica proposta per fold_left, fold_right, reduce e scan e i riferimenti collegati sugli algoritmi paralleli. Prima dell’implementazione, chiarisci quali funzioni Stan dovrebbe supportare e quali sono i relativi requisiti di API e valutazione; il lavoro è completato quando l’ambito è concordato e le funzioni selezionate sono implementate in modo coerente.

Scritto dal modello di indicizzazione a partire dal testo della issue.

Descrizione

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)

Lingua principale
C++
Stelle
845
Fork
225
Merge medio
3g 9h
PR unite (30g)
12

Preparare l'ambiente

Come iniziare

  1. Leggi tutta la issue e poi la guida ai contributi del progetto.
  2. Commenta sulla issue per dire che te ne occupi tu — evita che due persone facciano lo stesso lavoro.
  3. Fai un fork del repository e lavora su un branch.
  4. Apri una pull request che faccia riferimento al numero della issue.

Altre issue di stan-dev/math

Tutte le issue di stan-dev/math

Issue simili

Altre issue su C++

Ricevi le nuove issue nella tua casella

Un breve riepilogo di issue GitHub adatte ai principianti.