在前面有简易说到不可变性是咋回事,这里要稍微理性一些认识不可变性中结构化共享的概念。结构化共享可以使数据结构少占内存,clojure还提供了更节省内存的方法—惰性。
Clojure的任何值都是不可变的,引用可以任意赋值。即只有可变引用,没有可变对象。
1 2
| (def a '(1 2 3 4)) (def a (conj 1 a))
|
数据的不可变性给多线程场景下的数据共享带来不少福利,因为数据是持久永恒不变的,所以线程间不必担心彼此修改了数据而导致程序不确定性。如果对象是可变的,那么就会像java,需要一堆工具和大部分精力去保证数据对每个线程来说都是正确的,极其不便。
数据是不可变的,那我要是需要修改数据,怎么办?之前说了,对不可变数据做任何修改,数据都会重新“拷贝”出一份,赋给新的引用。这里说的“拷贝”不是真的把数据复制一份,而是开头说的结构化共享。
1 2 3 4 5 6 7 8 9 10
| (def a '(1 2 3 4)) (def b (conj a 5)) (identical? a (next b))
|
列表的结构化共享并不复杂,很容易理解。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)) (def tree1 (xconj tree1 3)) (def tree1 (xconj tree1 2)) (def tree2 (xconj tree1 7)) (identical? (:L tree1) (:L tree2))
|
上面的简易二叉树例子,可以发现:
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)] [])) (rec-step [0 1 2 3 4 5 6 7 8 9]) (rec-step (range 20000))
|
所以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))) (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) (def lzy-lst (lazy-simple-lst 0 2000)) (def lst (simple-lst 0 2000)) (time (count lzy-lst)) (time (count lst))
|
lazy-seq的next和rest操作结果也是有区别的。每取一次seq时,rest都会完全按照我们的本意,一个一个实例化出来;next则不然,它为了确保下一次seq是否为nil,会额外实例化至少一个元素,即next返回的序列,至少惰性延迟一个元素。当我们需要尽可能的惰性序列时,则用rest。在一般情况下,用next还是比较保险的,但如果每实例化一个元素都很费劲的话,显然rest实现完全惰性是不二选择!
虽然惰性序列能保证大数据量不会被必须一次性完全实例化而导致内存爆,但数据被逐个调用后,如果不放弃头部,迟早还是会奔溃。
1 2 3 4
| (let [r (lazy-simple-lst 0 1e8)] (list (first r) (last r))) (let [r (lazy-simple-lst 0 1e8)] (list (last r) (first r)))
|
惰性是个好东西!
- ###
分块序列
clojure有个很值得一提的技术,夹在一次性完全实例化和逐一实例化的惰性之间,就是分块序列,意思是每一次实例化一定宽度的元素(称“分块窗口”)。分块序列在某些时候,其综合性能要比惰性序列要高,毕竟惰性的“一次一个”实例化的消耗还是不容小视的。
1 2 3 4 5 6 7
| (def gimme #(do (print \. %))) (take 1 (map gimme (range 32))) (take 1 (map gimme (range 65))) (take 1 (drop 32 (map gimme (range 65))))
|