Scans and reduction functions

Offen
  • Stimmt etwas nicht?
#3,340 1 Kommentar 2 Reaktionen 0 zugewiesene Personen Auf GitHub ansehen

Maintainer antworten meist innerhalb von 1 Tag

Dieses Issue hat noch niemand übernommen.

Bewertung

Schwierigkeit
5/5
Geschätzter Aufwand
Über eine Woche
Anfängerfreundlichkeit
35/100
Issue-Typ
Feature
Klarheit
Muss geklärt werden
Aktivitätsstatus
Ruhig
Tech-Stack
cpp
Bereich
backend

Rechercherichtung

Beginne mit dem verwandten Issue #3339, überprüfe dann die vorgeschlagene Semantik für fold_left, fold_right, reduce und scan sowie die verlinkten Referenzen zu parallelen Algorithmen. Kläre vor der Implementierung, welche Funktionen Stan unterstützen sollte und wie deren API und Auswertungsanforderungen aussehen; abgeschlossen ist die Arbeit, wenn der Umfang vereinbart und die ausgewählten Funktionen konsistent implementiert sind.

Vom Indexierungsmodell aus dem Issue-Text verfasst.

Beschreibung

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)

Vorherrschende Sprache
C++
Sterne
845
Forks
225
Ø Merge
4 T. 21 Std.
Gemergte PRs (30 T.)
13

Entwicklungsumgebung

Erste Schritte

  1. Lesen Sie das ganze Issue und danach den Beitragsleitfaden des Projekts.
  2. Schreiben Sie ins Issue, dass Sie es übernehmen — das erspart doppelte Arbeit.
  3. Forken Sie das Repository und arbeiten Sie in einem Branch.
  4. Öffnen Sie einen Pull Request, der die Issue-Nummer nennt.

Mehr aus stan-dev/math

Alle Issues in stan-dev/math

Ähnliche Issues

Weitere Issues zu C++

Neue Issues direkt in Ihr Postfach

Eine kurze Übersicht über anfängerfreundliche GitHub-Issues.