Clojure

瞬时数据结构

基本原理

如果森林里有一棵树倒下,它会发出声音吗?
如果一个纯函数为了产生一个不可变的返回值而修改了一些局部数据,这可以接受吗?

这是一个有趣的问题。Clojure 数据结构在每次调用(例如 **assoc**)时都会使用变异,创建一到多个数组并对其进行变异,然后在之后返回它们以供不可变使用。原因是性能 - 您根本无法仅使用纯函数和不可变数据获得如此快的速度。然而,一旦构建并共享,不可变性和持久性对于健壮的程序至关重要。Clojure 在内部变异的对象是构成其数据结构内部节点的小型新分配的数组。没有人会看到这些数组。

当您希望使用多个步骤初始化或转换一个大型持久数据结构时,您会遇到类似的情况,这些步骤中的任何一个都不会被除构建/转换代码之外的任何代码看到。这里的挑战在于转换的来源将是一个现有的持久数据结构,并且函数的结果将被共享。复制到传统的可变数据结构并返回涉及 O(n) 的复制,并且内部代码是命令式的混乱,与您的 Clojure 代码的其余部分完全不同。此外,没有防止意外共享或为可变数据结构创建别名的保护,特别是如果您需要调用辅助函数来完成工作时。简而言之,如果您不得不离开 Clojure 的模型来加快此类代码的执行速度,那将是一件憾事。瞬时数据结构是解决此优化问题的一种解决方案,它与 Clojure 模型集成并提供您期望从 Clojure 获得的相同线程安全保证。

工作原理

瞬时数据结构总是从现有的持久 Clojure 数据结构创建。从 Clojure 1.1.0 开始,支持向量、哈希映射和哈希集。请注意,并非所有 Clojure 数据结构都支持此功能,但大多数都支持。列表不支持,因为这样做没有好处。

您可以通过调用 **transient** 获取数据结构的瞬时“副本”。这将创建一个新的瞬时数据结构,它是源的副本,并具有相同的性能特征。事实上,它大多源数据结构,并突出了瞬时数据结构的第一个特性 - 创建一个瞬时数据结构是 O(1) 操作。它与源共享结构,就像持久副本共享结构一样。

瞬时数据结构的第二个特性是创建它不会修改源,并且无法通过使用瞬时数据结构来修改源。您的源数据一如既往地保持不可变和持久。

瞬时数据结构支持源的只读接口,即您可以像使用持久向量一样调用 **nth**、**get**、**count** 并对瞬时向量进行函数调用。

瞬时数据结构不支持源数据结构的持久接口。**assoc**、**conj** 等都将抛出异常,因为瞬时数据结构不是持久的。因此,您无法意外地将瞬时数据结构泄漏到需要持久数据结构的上下文中。

瞬时数据结构支持一组并行的“更改”操作,这些操作具有类似的名称,后跟 **!** - **assoc!**、**conj!** 等。它们与相应的持久操作执行相同的功能,只是返回值本身是瞬时的。尤其要注意的是,瞬时数据结构并非设计为就地修改。您必须捕获并使用返回值在下一个调用中。这样,它们支持与它们替换的功能性持久代码相同的代码结构。如示例所示,这将允许您轻松地提高代码的性能,而无需进行结构更改。

完成构建结果后,您可以通过对瞬时数据结构调用 **persistent!** 来创建一个持久数据结构。此操作也是 O(1) 操作。在调用 **persistent!** 后,不应再使用瞬时数据结构,并且所有操作都将抛出异常。对于您可能创建的任何别名,这也将适用。

示例

这是一个非常典型的示例,一些构建向量以供返回的代码,所有“更改”都对函数局部。请注意,使用瞬时数据结构的版本具有完全相同的结构,只是

  • 对源向量调用 **transient**

  • 使用 **conj!** 而不是 **conj**

  • 在返回时调用 **persistent!**

(defn vrange [n]
  (loop [i 0 v []]
    (if (< i n)
      (recur (inc i) (conj v i))
      v)))

(defn vrange2 [n]
  (loop [i 0 v (transient [])]
    (if (< i n)
      (recur (inc i) (conj! v i))
      (persistent! v))))

;; benchmarked (Java 1.8, Clojure 1.7)
(def v (vrange 1000000))    ;; 73.7 ms
(def v2 (vrange2 1000000))  ;; 19.7 ms

哦,是的,瞬时数据结构很快!

并发使用

这就是使用瞬时数据结构的全部内容,但它们还有另一个重要的约束:**瞬时数据结构需要线程隔离。**因为瞬时操作的每个结果都与之前的操作共享(可变)结构,所以如果多个线程同时操作一个瞬时数据结构,则会出现错误。特定瞬时数据结构实例的使用应通过在单线程范围内使用它或在通过其他方式强制执行此约束的框架中使用它来控制。

在 Clojure 1.6 及更早版本中,瞬时数据结构会检测来自创建它们的线程以外的任何线程(读取或写入)的使用并抛出异常。此检查已在 1.7 中删除,以允许在像 core.async go 块这样的框架中更灵活地使用,这些框架通过其他方式强制执行单线程约束。

总结

瞬时数据结构为功能性数据结构构建代码提供了一种高性能优化,它与 Clojure 的数据结构一起工作并提供关键的安全保证。

  • 单路径使用

  • 从持久数据结构创建 O(1) 操作

  • 与持久源共享结构

  • 编辑会话完成后创建持久数据结构的 O(1) 操作

  • 与功能版本相同的代码结构

    • 捕获返回值,用于下一个调用

    • 不要就地修改

    • 不是持久的,因此您无法保留中间值或创建别名

  • 返回持久版本后无法使用

  • 快速

瞬时持久向量、哈希映射和哈希集在 Clojure 1.1 中添加。