Scans and reduction functions

未關閉
  • 哪裡不對？
#3,340 1 則留言 2 個 reaction 已指派 0 人 在 GitHub 檢視

維護者通常 1 天內回覆

還沒有人認領這個 Issue。

評估

難度
5/5
預估耗時
一週以上
新手友好度
35/100
Issue 類型
功能
描述清晰度
需要釐清
活躍度
冷清
技術堆疊
cpp
領域
backend

研究方向

從相關 issue #3339 開始，然後檢視針對 fold_left、fold_right、reduce 和 scan 提出的語意，以及關於平行演算法的連結參考資料。在實作之前，釐清 Stan 應支援哪些函式及其 API 和求值要求；當範圍達成共識且所選函式已一致地實作時，即視為完成。

由索引模型根據 Issue 內容生成。

描述

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)

主要語言
C++
星號
845
分支
225
平均合併
4 天 21 小時
30 天內合併 PR
13

環境準備

從這裡開始

  1. 先讀完整個 Issue，再讀專案的貢獻指南。
  2. 在 Issue 下留言說明你要接手 —— 這能避免兩個人做同樣的事。
  3. Fork 儲存庫，在一個分支上完成修改。
  4. 送出 Pull Request，並在描述裡引用這個 Issue 編號。

stan-dev/math 的其他 Issue

查看 stan-dev/math 的全部 Issue

相似的 Issue

更多 C++ Issue

把新 issue 寄到你的電子郵件信箱

精選適合新手參與的 GitHub issue 摘要。