Persistent and Transient Data Structures in Clojure

比眉伴天荒 2022-04-17 06:27 240阅读 0赞

此文已由作者张佃鹏授权网易云社区发布。

欢迎访问[网易云社区][Link 1]，了解更多网易技术产品运营经验。

最近在项目中用到了Transient数据结构，使用该数据结构对程序执行效率会有一定的提高。刚刚接触Transient Data Stuctures，下面将自己关于对其的了解总结如下：

**1.clojure的不可变数据特性及存储方式：**

clojure中的数据结构具有不可变特性（Persistent），也就是对一个数据结构添加元素、删除元素、更改元素，返回的是一个新的数据结构，而原来的数据结构不会变：

;;;定义一个向量
    (def data [1 2 3 4 5])
    ;;=> #'user/data;;更改向量中的元素，返回新的向量，而原有向量不变
    (update data 3 str)
    ;;=> [1 2 3 "4" 5]
    data
    ;;=> [1 2 3 4 5]
    
    ;;给向量增加一个元素，返回新的向量，原有向量的数据结构不变
    (assoc data 5 6)
    ;;=> [1 2 3 4 5 6]
    data
    ;;=> [1 2 3 4 5]

以上对data=\[1 2 3 4 5\]作增加和更改操作，data数据本身都没有变，而是生成了新的数据，这样的数据不可变性非常有利于数据的安全性，不会出现更改对象带来的副作用。这样的特性必然对数据的存储方式有很高的要求，clojure中的数据结构采取idea hash trees（[http://lampwww.epfl.ch/papers/idealhashtrees.pdf）进行存储：][http_lampwww.epfl.ch_papers_idealhashtrees.pdf]

vector中的所有元素都放在Leaf node中，而Internal node不存放元素，只是存放指向儿子节点的指针，用于寻找叶子节点，其中有个Head指针指向树的根节点，该Head指针存放着数据为该vector的大小，根据vector的size，我们便可以沿着Internal node找到存放在任何序号的元素。   clojure中的vector数据结构具有不可变性，所以为了减少复制的成本，clojure对其存储采取高效的共享模式：

;;
    (def brown [0 1 2 3 4 5 6 7 8])
    (def blue (assoc brown 5 'beef))

上面定义了一个brown的向量，然后更改brown的第6个元素生成新的向量blue，brown和blue之间的存储结构如下：

如上图所示，在brown数据结构上更改元素后，原有的brown数据结构从其head指针开始完全没有改变，每一个vector都有自己的head指针，因此blue必须构造自己的head指针，在构造的过程中，尽量共享brown已有的数据结构，只是新增加了一个被更改的叶子节点，减少了没必要的存储空间的浪费。   这样理想的存储方式非常有利于不可变数据结构增删改操作，时间复杂度是O(log2 n)，实际存储中，clojure采取不是2个子节点的存储方式，而是32个子节点的存储方式，相应的时间复杂度是 O(log32 n)。我们知道对于n非常大的情况下，O(log32 n)和O(log n)的复杂度是一样的，但是对于相对较小的数据来说，O(log32 n)可以近似O(1)，这也是为什么clojure为什么说自己对于vector的增删改操作接近常数时间的原因。

**2.为什么要有Transient Data Structures：**

尽管vector数据结构的存储方式效率已经很高了，但是它依然需要频繁的分配存储空间和对存储空间进行垃圾回收，比如我们执行以下操作：

;;以此将0到9加入到一个vector中
        (reduce conj [] (range 10))
        ;;=> [0 1 2 3 4 5 6 7 8 9]

在将这10个数依次加入到数组中，每加入一个数便生产一个带有head指针的新的vector，又因为前面一个vector已经不会再被用到，系统需要对其空间进行垃圾回收，虽然前后数据结构中的存储空间有一定的共享，但是这样的操作还是会有一定时间的浪费，对于效率要求比较高的代码难以接受。   因此为了提高效率，clojure增加了一种Transient数据类型，transient使clojure的数据结构可以改变，transient不仅可以使用在vector中，还可以在set和map中使用，但是不能用于list中。下面通过更新一个vector中的元素操作来对比transient与persistent数据类型的区别，将\[1 2 3 4 5 6\]更新为\[1 2 F 4 5 6\],两种不同数据类型之间的变化过程如下：

persistent更新操作后，具有两个head指针，也就两个不同的vector，而transient更新操作后，只是在原有数据结构的基础上，更改了一个叶子节点，head指针不变，原有的vector中存放的内容发生了改变，所以transient在一定程度上减少了存储空间的浪费，提高了代码执行效率。

**3.Transient Data Structures的相关操作函数：**

对于只读操作，因为不会改变数据内容，transient data和persistent data共享一套只读操作函数，比如：nth, get, count等函数，但是对于更改数据的函数，会有另外一套操作函数，下面是关于transient data structures数据结构相关操作函数的详解：

*  transient函数：

该函数是将一个persistent数据格式转换为transient的数据格式，该操作的时间复杂度接近于O(1)，如果我们对转换后的做更改操作，不会影响原有数据内容，原有数据依然是persistent。

*  persistent!函数：

该函数恰好与transient函数相反，将一个transient的数据格式转换为persistent格式，不同的是：转换后会影响原有的transient数据，使原有的transient数据变为不可用:

(def a [1 2 3])
        ;;=> #'insight.main/a
        ;;用transient函数生成transient格式的数据
        (def a' (transient a))
        ;;=> #'insight.main/a'
        ;;获取其中的函数
        (nth a' 2)
        ;;=> 3
        ;;增加数据
        (conj! a' 4)
        ;;用persistent！函数返回不可变数据格式内容
        (persistent! a')
        ;=> [1 2 3 4]
        ;;这个时候原有的a'数据将变为不可用数据，对其读写都会抛出异常
        (nth a' 2)
        IllegalAccessError Transient used after persistent! call  clojure.lang.PersistentVector$TransientVector.ensureEditable (PersistentVector.java:548)
        (conj! a' 4)
        IllegalAccessError Transient used after persistent! call  clojure.lang.PersistentVector$TransientVector.ensureEditable (PersistentVector.java:548)

*  相关“写”操作函数：

对于transient相关“写”操作函数有：assoc!/conj!/disassoc!/pop!/disj!，这些写操作函数只是在对于persistent相关函数后加上“！”，他们的函数参数格式与去掉“！”后的函数一模一样，下面列举了相关操作代码：

;;将0到9以此加入到一个transient类的vector中,每次加入一个元素时，不会建立新的vector，
        (loop [i 0 v (transient [])]
          (if (< i 10)
            (recur (inc i) (conj! v i))
            (persistent! v)))
        ;;=> [0 1 2 3 4 5 6 7 8 9]

*  特别需要注意的地方：

虽然在增加元素时，是在原有结构上增加元素，但是这也并不意味着原有数据结构的头指针(Head)一定不变，如果增加的元素特别多的情况下，需要从新调整数据层次结构，那么头指针就会发生改变，而原有数据结构的头指针与该数据结构的名字一一对应，所以对该transient数据进行操作时，一定要将操作后的数据赋值给原有数据的名字：

;;连续8次给t添加key-value对，返回结果是正确的
        (let [t (transient {})]
          (dotimes [i 8]
            (assoc! t i i))
          (persistent! t))
        ;;=> {0 0, 1 1, 2 2, 3 3, 4 4, 5 5, 6 6, 7 7}
        ;;当连续9次给t添加key-value对时，便返回错误的结果，因为当9次添加元素时，该map的头指针发生了变化，所以新的数据内容不是以前的t
        (let [t (transient {})]
          (dotimes [i 9]
            (assoc! t i i))
          (persistent! t))
        ;;=> {0 0, 1 1, 2 2, 3 3, 4 4, 5 5, 6 6, 7 7}

正确的使用添加方式应该如下：

;;可以使用reduce函数，每次添加元素是在assoc!函数的返回结果上进行添加，这样便会返回正确的内容
        (persistent!
          (reduce (fn [t i] (assoc! t i i))
                  (transient {})
                  (range 10)))
        ;;=>{0 0, 7 7, 1 1, 4 4, 6 6, 3 3, 2 2, 9 9, 5 5, 8 8}

**4.clojure.core库中使用transient data相关函数及其效率：**

在什么情况下会适用Transient Data Structurese呢？首先，我们只在乎更改后的数据，原始数据对我们来说不重要，也不会再被用到。其次，Transient Data Structures适用于单线程的程序，因为每个线程共享相同的数据时，同时更改会造成并发问题，这也是clojure为什么采用persistent数据结构的原因之一;最后，瞬态数据结构主要为了提高代码效率而设计，所以对于多次连续添加元素，可以考虑使用transient数据格式。   经过对clojure.core库中相关函数定义源码的搜索，找出了该中使用了transient data structure相关函数有：set函数/into函数/mapv函数/filterv函数/group-by函数/frequencies函数,我们可以发现这些函数的特点都是对一个序列进行更改操作，但是并不关心原始数据的内容，以下我们用criterium.core库中的quick-bench函数来测试代码运行时间，从而证明transient data的效率：

;;into函数的效率提高效果：
        ;;用concat函数合并两个一个vector和list，将合并结果转换为vector，平均消耗时间为：4.354145 µs
        (quick-bench (vec (concat [1 2 3] (range 100 200))))
        ;;Evaluation count : 154098 in 6 samples of 25683 calls.
        ;;Execution time mean : 4.354145 µs
    
        ;;直接使用into函数将一个list函数中的内容插入到vector中，平均消耗时间只需要1.549213 µs
        (quick-bench (into [1 2 3] (range 100 200)))
        ;;Evaluation count : 382944 in 6 samples of 63824 calls.
        ;;Execution time mean : 1.549213 µs
    
        ;;mapv函数的效率提高效果：
    
        ;;我们自己定义个mapv'函数与mapv函数操作效果一样
        (defn mapv' [f coll]
          (loop [result [] r coll]
            (if (nil? (seq r))
              result
              (recur (conj result (f (first r))) (rest r))
              )))
    
        ;;使用我们自己定义的函数，平均消耗时间为794.484682 µs
        (quick-bench (mapv' inc (range 10000)))
        ;;Evaluation count : 780 in 6 samples of 130 calls.
        ;;Execution time mean : 794.484682 µs
    
        ;;使用系统的mapv函数，平均消耗时间为197.386935 µs
        (quick-bench (mapv inc (range 10000)))
        ;;Evaluation count : 3090 in 6 samples of 515 calls.
        ;;Execution time mean : 197.386935 µs
    
        ;;使用map和vec操作函数，平均消耗时间为418.949804 µs
        (quick-bench (vec (map inc (range 10000))))
        ;;Evaluation count : 1482 in 6 samples of 247 calls.
        ;;Execution time mean : 418.949804 µs

通过以上对函数的对比，我们发现，transient函数在操作大数据的情况下，确实会给我们节省很多时间，所以在平时写代码时一定要养成好的习惯：为了提高代码效率，尽量使用以上提过的函数。

**5.总结：**

今天主要对刚刚学习的transient data structures进行了归纳总结，瞬态数据结构对于代码效率的提高有很大的作用，该数据类型可以应用到map，vector，map上，如果我们对原始数据毫不关心，则关心改变后的数据，尤其是连续多次的进行这样的操作，那么我们就可以考虑使用瞬态数据结构，clojure.core中有些函数用到了瞬态数据结构，所以我们尽量在编码时使用这些函数来提高代码效率。

[免费体验云安全(易盾)内容安全、验证码等服务][Link 2]

更多网易技术、产品、运营经验分享请[点击][Link 1]。

相关文章：  
【推荐】 [【专家坐堂】四种并发编程模型简介][Link 3]  
【推荐】 [编写一个供浏览器端使用的NPM包][NPM]

[Link 1]: https://sq.163yun.com/blog?tag=M_tg_618_72
[http_lampwww.epfl.ch_papers_idealhashtrees.pdf]: http://lampwww.epfl.ch/papers/idealhashtrees.pdf%EF%BC%89%E8%BF%9B%E8%A1%8C%E5%AD%98%E5%82%A8%EF%BC%9A
[Link 2]: https://www.163yun.com/free?tag=M_tg_618_72
[Link 3]: https://www.jianshu.com/p/d3e60d9e7c4f
[NPM]: https://www.jianshu.com/p/523504026fd3