在前面有简易说到不可变性是咋回事，这里要稍微理性一些认识不可变性中结构化共享的概念。结构化共享可以使数据结构少占内存，clojure还提供了更节省内存的方法—惰性。

  • 数据也有“版本树”？

Clojure的任何值都是不可变的，引用可以任意赋值。即只有可变引用，没有可变对象。

1
2
(def a '(1 2 3 4))
(def a (conj 1 a));=(5 1 2 3 4)

数据的不可变性给多线程场景下的数据共享带来不少福利，因为数据是持久永恒不变的，所以线程间不必担心彼此修改了数据而导致程序不确定性。如果对象是可变的，那么就会像java，需要一堆工具和大部分精力去保证数据对每个线程来说都是正确的，极其不便。

数据是不可变的，那我要是需要修改数据，怎么办？之前说了，对不可变数据做任何修改，数据都会重新“拷贝”出一份，赋给新的引用。这里说的“拷贝”不是真的把数据复制一份，而是开头说的结构化共享。

1
2
3
4
5
6
7
8
9
10
;继续上面的list
;好比a和b共享'(1 2 3 4)部分
(def a '(1 2 3 4))
(def b (conj a 5));=(5 1 2 3 4)
;做一下校验
(identical? a (next b));=true
;在这个简单例子的视图可见，5确实添加在链表，但指向5的指针是b，指针a没有任何偏移。
; b    a
; |    |
;[5]--[1]--[2]--[3]--[4]

列表的结构化共享并不复杂，很容易理解。map则会复杂很多，sorted-map由红黑树实现，array-map、hash-map等由Trie树实现。

搞个二叉树来简单说明一下map的结构化。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
(defn xconj [t v]
  (cond
    (nil? t) {:val v :L nil :R nil}
    (< v (:val t)) {:val (:val t)
                    :L (xconj (:L t) v)
                    :R (:R t)}
    :else          {:val (:val t)
                   :L (:L t)
                   :R (xconj (:R t) v)}))
(def tree1 (xconj nil 5));={:val 5, :L nil, :R nil}
(def tree1 (xconj tree1 3));={:val 5, :L {:val 3, :L nil, :R nil}, :R nil}
(def tree1 (xconj tree1 2));={:val 5, :L {:val 3, :L {:val 2, :L nil, :R nil}, :R nil}, :R nil}
(def tree2 (xconj tree1 7));={:val 5, :L {:val 3, :L {:val 2, :L nil, :R nil}, :R nil}, :R {:val 7, :L nil, :R nil}}
;{:val 5, :L {:val 3, :L {:val 2, :L {:val 1, :L nil, :R nil}, :R nil}, :R nil}, :R {:val 7, :L nil, :R nil}}
;{:val 5, :L {:val 3, :L {:val 2, :L {:val 1, :L {:val 0, :L nil, :R nil}, :R nil}, :R nil}, :R nil}, :R {:val 7, :L nil, :R nil}}
;{:val 5, :L {:val 3, :L {:val 2, :L {:val 1, :L {:val 0, :L nil, :R nil}, :R nil}, :R nil}, :R {:val 4, :L nil, :R nil}}, :R {:val 7, :L nil, :R nil}}
;两棵树的形状大致如下：
;   tree1            tree2
;    [5]              [5]
;   |   |            |   |
;  [3]  nil         [3] [7]
; |                |   
;[2]              [2]  
;取tree1和tree2的左边比较，结果是相等的
(identical? (:L tree1) (:L tree2));=true
;   tree1
;    [5]
;   |     tree2
;  [3] --- [5]
; |          |   
;[2]        [7]

上面的简易二叉树例子，可以发现：

1、数据结果每做一次修改，至少新增一个节点；

2、未被修改的另一边分支不会被复杂(比如[2]-[3])，可应用整棵树及其分支；

3、整个过程是线程安全的，多线程同时改变tree1，tree1依然是那棵树；

不同引用与这个结构化共享的数据形成了“版本树”，每个引用各自对应一个版本的数据。结构化共享是支持不变量所必须的，不然一直复制数据迟早会把内存撑爆。

  • 让数据更懒惰～

上面说到的结构化共享，作用于修改不变量时节省内存。但在处理大数据量是，单凭结构化共享是远远不够，十万八千里都不止！例如声明一个长列表是很耗性能的，完全实例化需要的内存可能非常多，花费的时间可能相当长，如果实例化过程中使用递归，完全会导致栈溢出。

举个例子，把一个向量转为多个cons嵌套。

1
2
3
4
5
6
7
8
(defn rec-step [[x & rest]]
  (if x
    [x (rec-step rest)]
    []))
;长度只有10，很容易就实例化全部元素
(rec-step [0 1 2 3 4 5 6 7 8 9]);=[0 [1 [2 [3 [4 [5 [6 [7 [8 [9 []]]]]]]]]]]
;假如需要20000个元素，长度不仅很长，而且实例化函数并非尾递归，未完全实例化就栈溢出。
(rec-step (range 20000));StackOverflowError   clojure.lang.LongRange.next (LongRange.java:142)

所以clojure给我提供了lazy-seq宏，用于生成惰性序列。惰性序列是干吗用的呢？当声明一个惰性序列后，里面的元素只有被调用到时才会被实例化，这样内存不会被一时间的大量数据耗尽，程序也不会长时间阻塞在实例化列表元素。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
;好比这个生成区间列表的函数
(defn simple-lst [i limit]
  (cond (> limit i) (conj (simple-lst (inc i) limit) i)
        (< limit i) nil
        :else (list i)))
;理想结果是(0 1 2 3 .... 9999999 10000000)，然而并不是
;一不小心就 StackOverflowError   clojure.lang.Numbers$LongOps.lt (Numbers.java:521)
(simple-lst 0 10000000)
;来个惰性序列版的
(defn lazy-simple-lst [i limit]
  (lazy-seq
    (when (>= limit i)
      (cons i (lazy-simple-lst (inc i) limit)))))
(def a (lazy-simple-lst 0 10000000))
(class a);=clojure.lang.LazySeq
;由于惰性序列需要调用时才实例化元素，所以在类似获取序列长度就需要完全实例化，非常耗时！
(def lzy-lst (lazy-simple-lst 0 2000))
(def lst (simple-lst 0 2000))
(time (count lzy-lst));="Elapsed time: 20.47562 msecs"
(time (count lst));="Elapsed time: 0.274659 msecs"
lazy-seq的next和rest操作结果也是有区别的。每取一次seq时，rest都会完全按照我们的本意，一个一个实例化出来；next则不然，它为了确保下一次seq是否为nil，会额外实例化至少一个元素，即next返回的序列，至少惰性延迟一个元素。当我们需要尽可能的惰性序列时，则用rest。在一般情况下，用next还是比较保险的，但如果每实例化一个元素都很费劲的话，显然rest实现完全惰性是不二选择!


虽然惰性序列能保证大数据量不会被必须一次性完全实例化而导致内存爆，但数据被逐个调用后，如果不放弃头部，迟早还是会奔溃。

1
2
3
4
;编译器会自行推断lazy-seq是否需要保持头，如果不需要，会自动逐渐清理垃圾。
(let [r (lazy-simple-lst 0 1e8)] (list (first r) (last r)))
;否则，一直持有序列头部，会使被实例化的部分无法释放，占用内存，直到StackOverflowError或OutOfMemoryError。尽管编译器可能会优化值的运算顺序，但也是要保证在纯函数下，所以丢弃头是惯用法，最好是这样做！
(let [r (lazy-simple-lst 0 1e8)] (list (last r) (first r)));=OutOfMemoryError GC overhead limit exceeded  user/lazy-simple-lst


惰性是个好东西！


- ### 分块序列

clojure有个很值得一提的技术，夹在一次性完全实例化和逐一实例化的惰性之间，就是分块序列，意思是每一次实例化一定宽度的元素(称“分块窗口”)。分块序列在某些时候，其综合性能要比惰性序列要高，毕竟惰性的“一次一个”实例化的消耗还是不容小视的。

1
2
3
4
5
6
7
(def gimme #(do (print \. %)))
;现在只需要第一个元素，但可以看到依然实例化整个区间
(take 1 (map gimme (range 32)));=. 0. 1. 2. 3. 4. 5. 6. 7. 8 ... 24. 25. 26. 27. 28. 29. 30. 31
;同样只需要第一个元素，整个区间长度为65，但只实例化前32个元素
(take 1 (map gimme (range 65)));=. 0. 1. 2. 3. 4. 5. 6. 7. 8 ... 24. 25. 26. 27. 28. 29. 30. 31
;当我们想获取第33个元素时，实例化了两个分块窗口(0-31,32-63)，64未被求值
(take 1 (drop 32 (map gimme (range 65))));=. 0. 1. 2. 3. 4. 5. 6. 7. 8 ... 56. 57. 58. 59. 60. 61. 62. 63