帮助我理解如何在Clojure中处理不变性和运行时间之间的冲突

Question

Clojure真正引起了我的兴趣,我开始学习它的教程:http: //java.ociweb.com/mark/clojure/article.html

考虑"Set"下提到的这两行:

(def stooges (hash-set "Moe" "Larry" "Curly")) ; not sorted
(def more-stooges (conj stooges "Shemp")) ; -> #{"Moe" "Larry" "Curly" "Shemp"}

我的第一个念头是第二次操作应该花费不间断的时间来完成; 否则,功能语言可能对面向对象的语言没什么好处.人们很容易想象需要从[几乎]空集开始,并在我们继续时填充它并缩小它.因此,我们可以将其重新分配给自己,而不是将新结果分配给更多的傀儡.

现在,通过功能语言的奇妙承诺,副作用无需关注.因此,设置stooges并且more-stooges不应该在彼此之上工作.因此,要么创建more-stooges是一个线性操作,要么它们共享一个公共缓冲区(如Java StringBuffer),这似乎是一个非常糟糕的想法,并且与不变性相冲突(随后stooges可以逐个删除元素).

我可能在这里重新发明一个轮子.当你从最大数量的元素开始然后一次删除一个元素时,它似乎hash-set会更有效率,clojure直到空集与反对以空集开始并逐渐增长它为止.

上面的例子可能看起来不太实际,或者有解决方法,但是面向对象的语言,如Java/C#/ Python /等.既可以一次增长也可以缩小一个或几个元素,同时快速完成它也没有问题.

保证(或只承诺？)不变性的[功能]语言无法快速增长.是否还有另一个可以使用的成语,它可以帮助避免这样做？

对于熟悉的人Python,我会提到集合理解与等效循环方法.两者的运行时间略有不同,但这与解释器的相对速度有关C,Python而不是复杂性.我看到的问题是,设置理解通常是一种更好的方法,但并不总是最好的方法,因为可读性可能会受到很大影响.

如果问题不明确,请告诉我.

Answer 1

核心不可变数据结构对我来说也是该语言最迷人的部分之一.他们回答这个问题很重要,Rich在这段视频中做得非常出色:

http://blip.tv/file/707974

核心数据结构:

• 实际上是完全不可变的
• 旧的副本也是不可变的
• 旧副本的性能不会降低
• 访问是不变的(实际上有界<=常数)
• 所有都支持有效的附加,连接(除了列表和seqs)和砍伐

他们如何做到这一点？？？

• 秘密:它几乎都是引擎盖下的树木(实际上是一个特里).

但是,如果我真的想编辑某些东西呢？

• 您可以使用clojure的瞬态编辑结构,然后在准备好共享时生成不可变的版本(在恒定时间内).

作为一个小背景:Trie是一棵树,钥匙的所有共同元素都悬挂在树的顶部.clojure中的集合和映射使用trie,其中索引是您要查找的键的哈希值.然后它将散列分成小块,并使用每个块作为hash-trie的一个级别的键.这允许共享新旧映射的公共部分,并且访问时间是有限的,因为只有固定数量的分支,因为在输入中使用的散列具有固定大小.

使用这些散列尝试还有助于防止在许多其他持久性数据结构使用的重新平衡期间出现大幅减速.所以你实际上会得到相当稳定的挂钟访问时间.

我真的推荐(相对简短)_书:纯功能数据结构 在其中,他涵盖了许多非常有趣的结构和概念,如"去除摊销",以允许对队列进行真正的恒定时间访问.和惰性持久队列之类的东西.作者甚至在这里提供pdf的免费副本