3

Clojure 真的引起了我的兴趣，我开始阅读它的教程：http: //java.ociweb.com/mark/clojure/article.html

考虑“设置”下提到的这两行：

(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/etc 这样的面向对象的语言。一次增长或缩小一个或几个元素，同时也可以快速完成。

保证（或只是承诺？）不变性的 [功能] 语言将无法快速增长集合。是否有另一种可以使用的成语以某种方式帮助避免这样做？

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

如果问题不清楚，请告诉我。

4

2 回答 2

8

对我来说，核心的不可变数据结构也是该语言最迷人的部分之一。他们很想回答这个问题，Rich 在这段视频中做得非常好：

http://blip.tv/file/707974

核心数据结构：

  • 实际上是完全不可变的
  • 旧副本也是不可变的
  • 旧副本的性能不会降低
  • 访问是常量（实际上是有界<=一个常量）
  • 都支持高效的附加、连接（列表和序列除外）和斩波

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

  • 秘密：引擎盖下几乎都是树（实际上是特里）。

但是，如果我真的想就地编辑东西怎么办？

  • 您可以使用 clojure 的瞬态来编辑结构，然后在准备好共享它时生成一个不可变版本（在恒定时间内）。

作为一个小背景：Trie是一棵树，其中键的所有公共元素都被提升到树的顶部。clojure 中的集合和映射使用 trie，其中索引是您要查找的键的哈希值。然后它将散列分解成小块，并将每个块用作一级散列树的键。这允许共享新旧地图的公共部分，并且访问时间是有限的，因为只能有固定数量的分支，因为在输入中使用的散列具有固定大小。

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

我真的推荐（相对较短）_书：Purely Functional Data Structures 在其中他涵盖了许多非常有趣的结构和概念，例如“消除摊销”以允许对队列进行真正的恒定时间访问。以及诸如惰性持久队列之类的东西。作者甚至在此处提供了 pdf 格式的免费副本

于 2010-09-09T22:31:08.660 回答
3

Clojure 的数据结构是持久的，这意味着它们是不可变的，但使用结构共享来支持有效的“修改”。请参阅 Clojure 文档中关于不可变数据结构的部分以获得更全面的解释。特别是，它指出

具体来说，这意味着无法使用完整副本创建新版本，因为这需要线性时间。不可避免地，持久性集合是使用链接数据结构实现的，因此新版本可以与先前版本共享结构。

这些 帖子，以及Rich Hickey 的一些演讲，很好地概述了持久数据结构的实现。

于 2010-09-09T22:30:01.017 回答