并行的 fold

原文：Folding in Parallel
作者：Oleg Kiselyov

本文描述了一种有趣的方法，用 map 和幺半群 reduce 来表述顺序执行的 fold。这样一来，某些看似有顺序的算法不仅可以并行运行，甚至还拥有美妙的并行性质：我们可以将输入序列任意分割给工作单元（如有必要，甚至可以递归地分割出子部分），并让工作单元并行运行——没有竞态条件、数据依赖，甚至不会有内存 bank 冲突。这种美妙的并行性质是多核、GPU 或分布式计算的理想选择。

这种方法的内在原理早已人尽皆知，但同样众所周知的是：将原理应用到具体案例需要独创性。

导言：fold vs. 幺半群 reduce

Guy Style 在二〇〇九年的 ICFP 会议上发表了一篇题为 «foldl and foldr considered slightly harmful» 的主题演讲¹。在演讲中，他提倡用 (map)reduce 取代 fold。

回想一下，序列上的 fold 本质上是一种带状态的按顺序累加；为具体起见，我们在列表上定义

fold_left  : ('z -> 'a -> 'z) -> 'z -> 'a list -> 'z
fold_right : ('a -> 'z -> 'z) -> 'a list -> 'z -> 'z

有一说一，现在我们有两种 fold：左 fold 与右 fold。下面的例子应该可以清楚地看出它们对应的语义

fold_left (+) 0 [1;2;3;4] ≡ (((0 + 1) + 2) + 3) + 4
fold_right (+) [1;2;3;4] 0 ≡ 1 + (2 + (3 + (4 + 0)))

这里用于 fold 的函数是加法函数，这种情况下两种 fold 得出的结果完全一致：它们都计算了列表中所有元素的和。而一般来说，左 fold 和右 fold 会产生不同的结果——譬如用减法函数来 fold。

列表中元素的类型 'a 与累加值的类型 'z 也不需要一样，我们可以用

fold_left (fun z _ -> z + 1) 0 l

来计算任意列表的长度；也可以用

fold_left (fun z x -> x :: z) [] l

翻转列表；甚至可以用

fold_right (fun x z -> if p x then x::z else z) l []

过滤掉那些对谓词函数 p 返回 false 的元素。许多列表上的操作（事实上，是所有操作）都可以通过 fold 表达。fold 实质上就是「对序列的进行有状态的串行处理」的一般模式。

fold 也有其他定义：有时候人们会交换 fold-right 的后两个参数。交换后，左 fold 和右 fold 具有相同的类型签名，但它们的行为和结合模式仍有不同。Olivier Danvy 回顾了列表 fold 和其参数顺序的历史（见下）。

为了具体起见，我们用列表演示 fold。但是数组、流、文件、树、字典以及其他任意集合都存在类似的操作。

在本文中所谓的 reduce 总是指幺半群［monoid］上的 reduce。幺半群是一个集合，这个集合有一个带有满足结合律的二元运算，以及一个单位元［unit element］（也称 zero²）。具体来说，在 OCaml 中有

type 'a monoid = {zero: 'a; op: 'a -> 'a -> 'a }

'a 是幺半群元素的类型，op 必须满足结合律，且对于幺半群上的所有元素 x 都应满足

op zero x = op x zero = x

在 Google 的 MapReduce 中，运算 op 还需满足交换律，本文没有这样的要求。

序列上的 reduce 就是（以列表为例）

reduce : 'a monoid -> 'a list -> 'a

其行为可以描述如下

reduce monoid []  ≡ monoid.zero
reduce monoid [x] ≡ x             (* 对于任意 x 和 monoid 都成立 *)

reduce {zero=0;op=(+)} [1;2;3;4] ≡ 1 + 2 + 3 + 4

有人可能会把 reduce 的操作形容成「将幺半群的运算『楔入』序列的相邻元素中间」。鉴于 op 满足结合律，括号并不重要，因此只有一个 reduce，没有左 fold 与右 fold 那样的区别。

我们常常看到 reduce 和 map 被预先组合在一起，这两个操作也可以融合成

map_reduce : ('a -> 'z) -> 'z monoid -> 'a list -> 'z

不过，为了展示清楚，本文还是把 map 和 reduce 分开来写，并假设实际中的执行使用融合过的高效操作。

鉴于 fold 的执行过程依赖于累加值数据，它必须按顺序求值。事实上，左 fold 只是 for 循环的另一种表示（为了使我们的示例不那么单调无味，这里使用数组切片作为序列）：

type 'a array_slice = {arr:'a array; from:int; upto:int} 
let fold_left_arr : ('z -> 'a -> 'z) -> 'z -> 'a array_slice -> 'z = 
  fun f z {arr;from;upto} ->
  let acc = ref z in
  for i=from to upto do
    acc := f !acc arr.(i)
  done;
  !acc

而另一方面，reduce 有多种实现方式。可以按顺序执行：

let seqreduce_arr (m: 'a monoid) (arrsl: 'a array_slice) : 'a =
  fold_left_arr m.op m.zero arrsl

也可以并行执行

let rec parreduce_arr (m: 'a monoid) {arr;from;upto} : 'a =
  match upto+1-from with
  | 0 -> m.zero
  | 1 -> arr.(from)
  | 2 -> m.op arr.(from) arr.(from+1)
  | 3 -> m.op (m.op arr.(from) arr.(from+1)) arr.(from+2)
  | n -> let n' = n / 2 in
         (* 这里的两个 parreduce_arr 可以并行执行！ *)
         m.op 
           (parreduce_arr m {arr;from;upto=from+n'-1})
           (parreduce_arr m {arr;from=from+n';upto})

代码中的两个对 parreduce_arr 的递归调用可以并行运行——它们甚至具有美妙的并行性质，互相不存在竟态条件，甚至没有读冲突。诚然，「是否应该并行执行」则另当别论，需要实事求是的分析。例如，如果数组切片很短，那么最好让两个 parreduce_arr 调用按顺序执行（因为并行计算确实存在一些开销）。如果被分解的切片本身又被再次分解了并行执行的两半，就得到了一种层次分解：二叉树式的处理。

我们不必递归分解切片，我们可以将输入数组任意切割成一系列不重叠的切片，然后将这些切片分给可用的计算核。这些计算核可以按自己的方式来完成为分配的任务，不需要和其他核进行同步。最后我们利用幺半群运算合并这些结果。

由于（左或右）fold 强制我们进行顺序求值，Guy Steele 称其「slightly harmful」（略微有害）。他呼吁人们尽可能使用 reduce：reduce 很灵活，它分离了算法本身和执行策略，具体执行策略（顺序、并行、分布式）和如何分割数据可以稍后再根据具体情况和可用资源进行选择。

因此，主要问题是：我们能否将 fold 转换为 reduce？本文的剩余部分将回答这个问题。

引用文献

• Guy Steele: Organizing Functional Code for Parallel execution or, foldl and foldr considered slightly harmful

ICFP 2009 主题演讲，二〇〇九年八月。

• Olivier Danvy: ``Folding left and right matters: direct style, accumulators, and continuations''

根据 Danvy 的说法，第一个对 fold_left 和 fold_right 的研究是 Christopher Strachey 在 1961 年进行的（!）。Reduce 也是 APL 语言（Iversion, 1962）的一部分，它在 APL 中被称为 /：因此对数组 x 求和就是 +/x。T 系统［System T］中的哥德尔递归子 R 是 fold 的一个推广版本（现在也称 para-fold）。丘奇数［Church numeral］也是一种 fold。

• monoid_reduce.ml

本文使用的完整代码

• How to zip folds

一个完整的，用 fold 表示列表的库，展示了所有列表处理操作都可以用 fold 表示。

• Accumulating tree traversals, a better tree fold

在 XML 解析上的应用。

用 map-reduce 表达 fold：平凡解

主要问题在于如何用 reduce 表达 fold_left 和 fold_right，本节将展示两个平凡解。事实上，我们可以发现：fold 总是可以用 reduce 表示，但这种表示方式既无用也无趣。

如果 fold 用函数（即 fold 的第一个参数）满足结合律（这也意味着序列元素的类型与累加值/计算结果的类型相同），且该函数具有单位元。那么 fold 自然就是 reduce 的一个实例，我们已经看过这个例子：对于任意列表 l 有

fold_left (+) 0 l ≡ fold_right (+) l 0 ≡ reduce {op=(+);zero=0} l

第二个平凡解是：fold 总可以无条件地表示为幺半群上的 reduce，即对任意具有适当类型的 f、z、l 有

let compose_monoid = {op=(fun g h -> fun x -> g (h x)); zero=Fun.id}
fold_right f l z ≡ List.map f l |> reduce compose_monoid |> (|>) z

对于左 fold 也有一个类似的表达式（留作读者练习）。关键思想在于「函数组合」运算满足结合律。

不幸的是，这个平凡解几乎没有实际用途。设有 f:'a -> 'z -> 'z，map f l 会创建一个类型为 'z -> 'z 的闭包构成的列表，然后 reduce 将这些闭包组合成一个（大的）'z -> 'z 闭包，最后再将这个闭包应用于 z 上。若列表 l 的大小为 N，那么 reduce 的结果是 N 个闭包的函数组合，其大小与 N 成正比（这个比例常数难以忽略，因为一个闭包可能会占用数个机器字大小的堆空间）——实际上，我们构建了一个无界限大小的中间数据结构。而尽管组合闭包可以并行执行，但只有程序将组合后的大闭包应用于初始累加值时，程序才会开始执行实际工作——此时程序是按顺序逐步应用函数 f，和原始 fold_right f l z 中的完全一致。这种平凡解只是在浪费时间和空间。

因此，问题不仅在于如何用 reduce 表示 fold，还在于如何高效地，不产生不必要和无界限的开销下做到这一点。只有这样，我们才能有效地并行进行 fold。

用 map-reduce 表示 fold：更有趣的解

我们的问题是如何高效地用 reduce 表示 fold，不能产生无限制大小的中间数据，也不能消耗过多的时间。换言之，如果 fold 能在恒定的时间和（工作）空间下处理单个序列元素，那么 reduce 也应该有这样的良好性质。

有时候这个问题可以简单地解决，之前已经展示过这样的例子：如果用于 fold 的函数满足结合律，且具有单位元，左 fold 和右 fold 就是 reduce 的实例。一个更有趣的情况是：对于任意序列元素 x 和累加值 z，用于 fold 的函数 f 都可以分解为 g 和 op 两个其他函数。如下所示：

f z x = op z (g x)

这里的 op 是一种满足结合律且具有单位元的运算。试举一例，回顾上文中「计算列表长度」的函数，它可以用 fold 表示如下

List.fold_left (fun z _ -> z + 1) 0 l

这个 fold 用函数显然可以分解为

z + 1 = z + (Fun.const 1 x)

因此，计算长度的函数可以重新写成

map (Fun.const 1) l |> reduce {op=(+);zero=0}

或者写成 map_reduce 形式，因此，列表长度可以并行计算。

这种分解不过是一个普遍原则的具体案例，Guy Steele 在他的演讲中将这种原则称之为共轭变换［conjugative transform］——该原则要求我们将 fold 表示为

fold_left (f:'z->'a->'a) (z:'z) l = map g l |> reduce m |> h

右 fold 也类似。这里的 m:'u monoid 是一个关于类型 'u 的幺半群，g:'a->'u 和 h:'u->'z 是一些函数，这些函数通常会依赖 f 和 z。非形式地说，这一原则建议我们寻找一种更大的，能嵌入 'a 和 'z，以及一个恰当的「满足结合律且有单位元的运算」元素。

正如上一节中所示，这样的方法总是可以用于表示 fold：只需选择 compose_monoid 为 m，并将 'z->'z 作为类型 'u。

「共轭变换」是一种原则或者模板。它本身不能告诉我们如何实际找出高效的幺半群，也不能揭示这样的幺半群是否存在。事实上，要找到高效的幺半群并不简单，需要创造力。譬如，考虑之前提到的减法 fold：减法不满足结合律，因此 fold_left (-) 不是 reduce 的实例。然而，稍加思考就能发现

fold_left (-) z l = z - fold_left (+) 0 l = z - reduce {op=(+);zero=0} l

将其表述为共轭变换的话：g 是取负数的函数，h 则是 (+) z 函数。

第二个思考时刻是：fold_right (-) 似乎并不能这么简单地用 reduce 实现（或许根本并不能？）。实际上，减法右 fold 也可以通过幺半群 reduce 高效地并行计算。这里鼓励读者自己寻找这个幺半群——从而欣赏其难度和精妙。

推广 Horner 法则

Horner 法则［Horner rule］，或称 Horner 模式³，是一种广泛使用的顺序算法，用于高效对多项式求值。类似的累加模式在解析中也常常出现。尽管该算法本质上是顺序执行的，但是似乎也可以用幺半群 reduce 来表示。我们的幺半群 reduce 方法比其他已知的 Horner 法则并行算法要更灵活，也更具有推广性。

作为示例，我们将一串十进制数字组成的列表（大端在前）转换为对应的整数——这是一个简单的解析操作，它也是一个带有累加值的顺序操作，可以写成 fold：

let digits_to_num =
  List.fold_left (fun z x -> 10*z + (Char.code x - Char.code '0')) 0

digits_to_num ['1'; '7'; '5'] 应返回 175。

易将该操作分解为 map 和 List.fold_left (fun z x -> 10*z + x) 0 的组合。这本质上就是 Horner 法则的应用：令 $b=10$，求 $\sum{}d_{i} b^{i}$。然而这里的 fold 用函数 fun z x -> 10*z + x 却不满足结合律。

所幸，仍有一种方法可以构造出幺半群。它一种是带有下述运算的幺半群

let op (x,b1) (y,b2) = (x*b2+y, b1*b2)

显然满足结合律（但是不满足交换律）

((x,b1) `op` (y,b2)) `op` (z,b3)
= (x*b2+y, b1*b2) `op` (z,b3)
= (x*b2*b3+y*b3+z, b1*b2*b3)
= (x,b1) `op` (y*b3+z,b2*b3)
= (x,b1) `op` ((y,b2) `op` (z,b3))

其单位元为 (0,1)：

(x,b) `op` (0,1) = (0,1) `op` (x,b) = (x,b)

digits_to_num 现在可以写成

let digits_to_num = 
    List.map (fun x -> (Char.code x - Char.code '0')) >>
    List.map (fun x -> (x,10)) >>
    reduce {op;zero=(0,1)} >> fst

>> 表示从左到右的函数组合，我们的构造也是一种共轭变换：g 是 fun x -> (x,10)，h 是 fst。因此可见，Horner 法则可以用 map-reduce 表示，并非常简单地并行求值。

我们的构造可以推广到任意满足下列性质的 fold 用函数 f : 'z -> 'a -> 'z

f z x = m.op (h z) x

m.op 应满足结合律且具有单位元（即它应为某个幺半群 m 上的运算）。这种分解看起来非常类似于上一节的展示，但无论幺半群之间有着多么微小的差异，都会使寻找它变得更困难。最终我们发现这一幺半群确实存在：

let hmonoid (m:'a monoid) : ('a * ('a->'a)) monoid = 
  {op = (fun (x,h1) (y,h2) -> (m.op (h2 x) y, h1 >> h2));
   zero = (m.zero, Fun.id)}

其载体集合为幺半群 m 元素和元素上的函数的对子 (x,h) 构成的集合。暂且假设组合 >> 可以高效表示——比如当 h 是乘某个常数的函数时，我们就可以用那个常数来表示 h，并通过对应常量的积来表示这种组合。

Horner 法则问题可能会令人想起并行前缀问题⁴和 Guy Blelloch 著名的并行 scan 问题（PPoPP 2009）⁵。不过，Horner 法则并不要求算法汇报中间计算结果。我们的幺半群 reduce 法不同于 Blelloch 的奇偶交错法，也不同于 Guy Steele ICFP09 主题演讲中提出的幺半群缓存树法——我们不需要任何特殊数据结构，只需使用普通数组，然后将其划分到可用的计算核即可。

由于 Horner 法则在求值多项式中非常普遍，已经有了一些将其并行化的方法。最常见的是按多项式系数的奇偶性进行分割，虽然这种方法非常适合 SIMD 处理，但奇偶分割对多核来说并不好，它会造成读竞争（bank 冲突）并浪费缓存空间。我们的幺半群 reduce 法可以把不同的内存 bank 分配给不同的核，让这些核独占地无冲突访问。

此外，Estrin 方法也可以看作我们构造的幺半群的一个特定用法（二分组）。我们的幺半群 reduce 法支持任意分组，如有必要，还可以进行层次分组，分组大小也不一定要等同。

Boyer-Moore 多数票决算法

Boyer-Moore 多数票决算法是一种寻找序列中多数元素的算法——所谓多数元素，指的是在序列中出现次数超过一半的元素。该算法需要遍历一次序列，消耗恒定的工作空间。必须记住的一点是：只有存在多数元素时，算法的返回值才是多数元素。该算法一般情况下无法判定序列中是否存在多数元素：如果不存在就返回任意元素，不一定返回出现频率最高的元素。我们通常需要对序列进行二次遍历以计算返回元素的出现次数，从而确定返回元素确实是多数元素。在某些特定情况下可以避免这种二次遍历。

普遍认为，Boyer-Moore 算法是一种典型的流式算法，具有顺序执行的本质。但是我们发现该算法竟然可以用幺半群 reduce 法来表示，从而高效地并行执行。这一点可能会令人感到惊讶——事实上，其并行程度可能会超乎想象。幺半群 reduce 法的实现本身很简单，但是要让我们相信「这个算法在任何情况下都正确」就复杂得多。

Boyer-Moore 算法从序列中逐元素地接受输入，并以一种状态机的方式处理之。因此可以用 fold 实现（假设输入为非空列表）：

let bm : 'a list -> 'a = function h::t -> 
  let fsm (c,m) x =
      if c = 0 then (1,x)
      else if m = x then (c+1,m)
      else (c-1,m)
  in List.fold_left fsm (1,h) t >> snd

算法的中间状态由计数器 c 和多数票候选 m 组成。当算法扫描过整个序列后，m 就是序列中的多数元素（如果序列中存在多数元素的话）。此时，若计数器 c 超过了序列长度的一半，就说明序列中确实存在多数元素，且这个元素就是 m；否则，必须再遍历一次序列以验证 m 确实为多数元素。而如果我们事先就知道一定存在多数元素，或者我们能接受「若不存在多数元素，返回任意元素」的行为，可以略过验证过程。

虽然这一算法看起来本质上是顺序算法，但实际上可以用幺半群 reduce 法执行：而且这个幺半群既简单又高效：

let bm_monoid (z:'a) : (int * 'a) monoid = 
  {zero = (0,z);
   op = fun (c1,m1) (c2,m2) ->
     if c1 = 0 then (c2,m2) else
     if c2 = 0 then (c1,m1) else
     if m1 = m2 then (c1+c2,m1) else
     if c1 > c2 then (c1-c2, m1) else
     (c2-c1, m2)}

这一幺半群的元素（载体）是由自然数 c 和序列元素 m 组成的对子，且当 c 为零时，m 可以是任意元素。在上述代码中，我们用 z 来表示这个任意元素；我们也可以把幺半群的载体定义成一个更复杂的数据结构，从而避免手动指定 z；或者就用 'a option。但是这样会把下面的推理过程变复杂，为了清楚起见，还是暂且保留上述定义。

不难看出 op 满足交换律，而且 zero 是 op 的单位元。然而，op 满足结合律吗？bm_monoid 真的是一个幺半群吗？要检查这点很简单

let m1 = (2,10) and m2 = (3,9) and m3 = (2,8)
op (op m1 m2) m3  ⇝ (1, 8) 
op m1 (op m2 m3)  ⇝ (1, 10)

不幸的是，bm_monoid 不是幺半群。

不卖关子了，bm_monoid 「理论上」是一种幺半群，用它来进行 reduce 在任何情况下都能得到正确的结果。然而，证明这一点不太简单。

为了证明，我们将 bm_monoid 扩展为：

let bm_monoid_ext (z:'a) : (int * 'a * ('a*'a) list) monoid = 
  {zero = (0,z,[]);
   op = fun (c1,m1,l1) (c2,m2,l2) ->
     if c1 = 0 then (c2,m2,l1@l2) else
     if c2 = 0 then (c1,m1,l1@l2) else
     if m1 = m2 then (c1+c2,m1,l1@l2) else
     if c1 > c2 then (c1-c2, m1, repeat c2 (m1,m2) @ l1 @ l2) else
     (c2-c1, m2, repeat c1 (m1,m2) @ l1 @ l2)}

这里的中缀运算符 @ 是列表连接，repeat (n:int) (x:'a) : 'a list 生成一个长度为 n 且元素都是 x 的列表。

bm_monoid_ext 的载体元素是三元组：由自然数 c、序列元素 m 以及「由两个不相等成分组成的对子」的列表（即对子的 fst 不等同于其 snd）。注意到 op 维持了「l 中所有对子的两个成分都不相等」的不变性质。

让我们在该载体集合上引入关系 ≈，其定义如下

定义. 若 flatten x 和 flatten y 在不考虑顺序的情况下相等，那么 x ≈ y，其中

let flatten : (int * 'a * ('a*'a) list) -> 'a list = fun (c,m,l) ->
  repeat c m @ List.map fst l @ List.map snd l

也就是说，flatten x 会将 x 中涉及到的所有元素收集到一个多数集［multiset］中。当且仅当 x 涉及的元素构成的多数集等同于 y 涉及的元素构成的多数集时，x ≈ y。不难看出关系 ≈ 满足自反律、交换律和结合律，它也是一种等价关系，还具有以下对我们有用的性质。

命题. bm_monoid_ext 是一个 ≈ 等价关系上的幺半群，即有

op (0,z,[]) (c,m,l) ≈ op (c,m,l) (0,z,[]) ≈ (c,m,l)
op (c1,m1,l1) (op (c2,m2,l2) (c3,m3,l3)) ≈ op (op (c1,m1,l1) (c2,m2,l2)) (c3,m3,l3)

结合律源于「op 运算保留了 (c,m,l) 中出现的元素，包括元素的数量」这一点（并且多重集的相等关系满足结合律）。

此外，≈ 完全能满足寻找多数元素这一工作

命题（充分）. 若 (c1,m1,l1) ≈ (c2,m2,l2) 且多重集 flatten (c1,m1,l1) 存在多数元素，那么有 c1>0 和 c2>0 以及 m1=m2。

非形式化地说：≈ 保留了已发现的多数元素（如果存在的话）。这一命题由「序列重排序不会影响多数元素」这一不变性质和下面的表示引理共同推导而出。

引理（表示）. 若序列（多重集）flatten (c,m,l) 中存在多数元素，那么 c>0，且 m 是多数元素。

证明. 为证明这一点，我们注意到：若互异对子列表 l 中有 n 个对子，那么它总共就有 2*n 个值。虽然并非所有值都互相不同，但是没有一个值的出现次数会超过 n 次——否则按照抽屉原理，l 中的某些对子会出现相同的成分。因此，在 (c,m,l) 中出现的任何不等于 m 的值都不能成为多数元素（如果 c>0）。如果有多数元素，那么必定是 m，且一定有 c>0。 $\blacksquare{}$

我们的证明受到了 Boyer 和 Moore 原始证明的启发，不过他们使用了数学归纳法，我们则相反——使用等式推理和抽屉原理，没有使用归纳。说句题外话：计算机科学中似乎只使用归纳法这一种证明方法——许多广泛使用的教科书都只介绍归纳证明法；在我看来，归纳证明有点被滥用了——数学中还有许多其他证明方法⁶。

最后，我们观察到 bm_monoid_ext 中我们真正关心的部分——元素 m 和计数器 c，可以在不考虑列表 l 的情况下计算。这个列表可以说算是一个「幽灵」列表，只有在证明算法正确性时才需要，计算多数元素时无必要。那么我们就可以省略这一元素，从而恢复到 bm_monoid。

综上，多数票决算法可以通过 map-reduce 执行：只需用 (fun x -> (1,x)) 函数来 map，然后在幺半群 bm_monoid 上 reduce 即可。它与最初的 Boyer-Moore 算法一样高效，只消耗较小常数的工作空间，也只需对序列遍历一次。不过，我们可以把输入序列任意分割给可用工作单元，让这些单元并行启动，单元之间不会存在干扰或依赖。多数票决法可以以超乎想象地程度并行执行。

结论

Guy Steele 在 ICFP'09 的主题演讲中告诫人们：尽可能使用 reduce（或 map_reduce）取代 fold。reduce 和 fold 不同，它不会强制使用某种特定的求值策略。它可以被顺序执行，也可以以超乎想象的程度并行执行，甚至可以以一种树形层次的风格执行——这有点类似于数学中的 $\sum{}$ 记号：它只是指定了应该对什么求和，但是没有指定求和的具体顺序。

Guy Steele 的结论也适用于本文。尤其是他最终的思考：

• 结合律算子非常重要。

• 发现（并证明）新的结合律算子非常，非常重要。

参考