Clojure

归约器

归约器提供了一种使用 序列 操作标准 Clojure 集合的替代方法。序列函数通常以延迟、顺序方式应用,创建中间结果,并且在单个线程中执行。但是,许多序列函数(如 map 和 filter)在概念上可以并行应用,从而生成随着机器内核增加而自动变得更快的代码。有关归约器原理的更多详细信息,请参阅原始的 博客 帖子

归约器可归约集合(知道如何归约自身的集合)与 归约函数(“配方”,用于在归约期间需要执行的操作)的组合。标准的序列操作被替换为新的版本,这些版本不会执行操作,而只是转换归约函数。操作的执行将推迟到执行最终归约为止。这去除了序列中看到的中间结果和延迟求值。

此外,某些集合(持久向量和映射)是 可折叠的。归约器上的 fold 操作通过以下方式并行执行归约:

  1. 以指定粒度(默认值为 512 个元素)对可归约集合进行分区

  2. 对每个分区应用 reduce

  3. 使用 Java 的 fork/join 框架递归地组合每个分区。

如果集合不支持折叠,它将回退到非并行 reduce。

reduce 和 fold

clojure.core.reducers 命名空间(在此别名为 r)提供了一个备用 r/reduce 函数。

(r/reduce f coll)
(r/reduce f init coll)

归约器版本有所不同,因为

  • 映射集合将使用 reduce-kv 进行归约

  • 当不提供 init 时,f 将在没有参数的情况下被调用以生成一个标识值

    • 注意:f 可能会多次被调用以提供标识值

一般来说,大多数用户不会直接调用 r/reduce,而是应该优先使用 r/fold,它实现了并行 reduce 和 combine。但是,使用较少中间结果来执行渴望的 reduce 可能会很有用。

(r/fold reducef coll)
(r/fold combinef reducef coll)
(r/fold n combinef reducef coll)

r/fold 接受一个可归约集合,并将其划分为大约 n(默认值为 512)个元素的组。每个组都使用 reducef 函数进行归约。reducef 函数将在没有参数的情况下被调用以生成一个标识值(在每个分区中)。然后使用 combinef(默认为 reducef)函数对这些归约的结果进行归约。当没有参数调用时,(combinef) 必须生成其标识元素 - 这将被多次调用。操作可能会并行执行。结果将保留顺序。

以下函数(类似于序列版本)从可归约或可折叠集合创建归约器: r/map r/mapcat r/filter r/remove r/flatten r/take-while r/taker/drop。这些函数都不会真正转换源集合。要生成累积的结果,必须使用 r/reduce 或 r/fold。要生成输出集合,请使用 clojure.core/into 来选择集合类型,或者使用提供的 r/foldcat 来生成一个可归约、可折叠、可序列化的和可计数的集合。

使用归约器

使用 fold 用 + 求和

(require '[clojure.core.reducers :as r])
(r/fold + (r/filter even? (r/map inc [1 1 1 2])))
;=> 6

使用 into 生成最终集合

(into [] (r/filter even? (r/map inc (range 100000))))

r/foldcat

(r/foldcat (r/filter even? (r/map inc (range 100000))))

用 fold 指定归约函数和组合函数

(defn count-words
  ([] {})
  ([freqs word]
    (assoc freqs word (inc (get freqs word 0)))))

(defn merge-counts
  ([] {})
  ([& m] (apply merge-with + m)))

(defn word-frequency [text]
  (r/fold merge-counts count-words (clojure.string/split text #"\s+")))

何时使用

对于以下情况,请使用这些操作的归约器形式:

  • 有效地渴望地应用多步转换

  • 避免悬挂 I/O 资源问题(如延迟序列中所见)

当以下情况时使用 fold

  • 可以生成源数据并将其保存在内存中

  • 要执行的工作是计算(不是 I/O 或阻塞)

  • 数据项数量或要完成的工作量“很大”