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"}
我的第一个想法是第二个操作应该需要恒定的时间才能完成；否则，函数式语言可能比面向对象的语言没有什么好处。人们很容易想象需要从[几乎]空的集合开始，然后填充它并随着我们的进展缩小它。因此，我们可以将新结果重新分配给自己，而不是将新结果分配给 more-stooges。
现在，由于函数式语言的奇妙 promise ，副作用不再需要担心。所以，设置 stooges和more-stooges不应该在彼此之上工作。因此，要么创建 more-stooges是一个线性操作，或者它们共享一个公共(public)缓冲区(如 Java 的 StringBuffer )，这看起来是一个非常糟糕的主意，并且与不变性冲突(随后 stooges 可以逐一删除元素)。
我可能在这里重新发明了一个轮子。看起来像 hash-set clojure 中的性能会更高当您从最大数量的元素开始，然后一次删除一个元素直到空集，而不是从一个空集开始并一次增加一个。
上面的例子可能看起来不太实用，或者有解决方法，但是像 Java/C#/Python/等面向对象的语言。一次增加或缩小一组元素或几个元素都没有问题，同时速度也很快。
保证(或只是 promise ？)不变性的[函数式]语言将无法快速增长集合。是否还有另一种习惯用法可以帮助避免这样做？
对于熟悉 Python 的人，我会提到集合理解与等效循环方法。两者的运行时间略有不同，但这与 C 的相对速度有关。 , Python ，解释器而不是 Root 于复杂性。我看到的问题是，集合理解通常是一种更好的方法，但并不总是最好的方法，因为可读性可能会受到很大影响。
如果问题不清楚，请告诉我。
最佳答案
核心不可变数据结构对我来说也是该语言最迷人的部分之一。他们对回答这个问题有很多内容，Rich 在这段视频中做得非常出色:
核心数据结构:
- 实际上是完全不可变的
- 旧副本也是不可变的
- 旧副本的性能不会降低
- 访问是恒定的(实际上有界 <= 恒定)
- 都支持高效的附加、连接(列表和序列除外)和剪切
他们是怎么做到的？？？
- secret :引擎盖下几乎所有树(实际上是一个特里树)。
但是如果我真的想就地编辑某些内容怎么办？
- 您可以使用 clojure 的 transients就地编辑结构，然后在准备好共享时生成不可变版本(在恒定时间内)。
作为一个小背景:a Trie是一棵树，其中键的所有公共(public)元素都被提升到树的顶部。 clojure 中的集合和映射使用 trie，其中索引是您要查找的键的哈希值。然后，它将散列分解成小块，并使用每个 block 作为散列特里树的一级的 key 。这允许共享新旧映射的公共(public)部分，并且访问时间受到限制，因为输入中使用的散列具有固定大小，因此只能有固定数量的分支。
使用这些哈希尝试还有助于防止许多其他持久数据结构使用的重新平衡过程中出现大幅减速。所以你实际上会得到相当恒定的挂钟访问时间。
我真的推荐这本书(相对较短):Purely Functional Data Structures 在其中，他涵盖了许多非常有趣的结构和概念，例如“消除摊销”以允许队列真正的恒定时间访问。以及惰性持久队列之类的东西。作者甚至在 pdf here 中提供免费副本
关于clojure - 帮助我了解 Clojure 中如何处理不变性和运行时间之间的冲突，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/3680934/