前言 原文地址：http://hypirion.com/musings/understanding-persistent-vector-pt-3 为什么翻译这系列博客？一直觉着翻译是学习的笨功夫，阅读一遍可能理解了概要，但是其实还是有很多细节遗漏了，翻译这个过程可以查缺补漏，更重要的是，我想重新写博客了 :D。 正文 关于 Clojure Persistent vectors 这个系列博客的 [Part 1](http://blog.fnil.net/blog/c9ce36719a8e37188fc51d27ca482504/ 翻译:深入理解 Clojure Persistent Vectors 实现 Part 1)和 [Part 2](http://blog.fnil.net/blog/3a2ce94a8eecdeffec608b6a6ed6f190/ 翻译：深入理解 Clojure Persistent Vectors 实现 Part 2) 应该可以让你对 persistent vector 的工作原理的有个大概的了解，但是，其实这里仍然有许多不同的方法可以消减（算法）的常数因子（的影响）。可能最容易理解的部分是尾部（tail），我们将在这篇博客里介绍。 尾部的基本原理 回想下 (conj [1 2 3 4] 5) 这个操作的可视化展示，没有任何尾部实现时：如果在最右叶子节点有空间，我们仅需要拷贝向下到达该叶子节点的路径，并将最后这个新元素插入到拷贝中。 有尾部的时候会有什么不同呢？让我们瞧下： 不再是在树里面保存最右叶子节点，取而代之，我们在 vector 的头部(header)就持有一个它的直接引用：这是上篇博客后加入 vector 头部的最后部分。指向最右叶子节点的引用称为尾部。 对于 conj 操作，我们以检测尾部有没有足够空间而告终。因为这里刚好是这种情况 —— 我们拷贝了尾部，并将新元素插入其中。请注意这是常量时间，不是_近乎_常量时间。所以，每次在尾部有空余空间的时候，我们 conj 新元素到 vector 的时候，我们都是在做常量时间的操作。 这使得批量操作变得特别快。如果你接连做大量的 conj 操作，结果是每个操作的耗时平均起来更少。对于一个分支因子是 2 的 vector， 1/2（50%） 的 conj 操作（平均起来）是常量时间。如果将分支因子替换成 32， 31/32 的所有 conj 操作都将实际上是常量时间。只有 3.

#前言 原文地址： http://hypirion.com/musings/understanding-persistent-vector-pt-2 上一篇： 翻译:深入理解 Clojure Persistent Vectors 实现 Part 1 #正文 在前一篇关于 Clojure Persistent Vectors 的博客里（如果你还没有读过，请点击阅读），我们大致理解了 vector 里元素的插入、更新和出队操作是如何工作的。我们还没有真正了解到是如何定位到正确的元素，在这篇博客我将介绍查找元素是如何实现的。 为了理解我们是如何在树的节点里面选择正确的分支，我想最好是先给这些结构一个合适的名称，并解释_为什么_这样命名。通过一个数据结构的名称来解释分支选择似乎听起来很奇怪，但是如果考虑到这个名称可能描述了它的工作原理的话，这还是有意义的。 名称 Clojure persistent vector 数据结构的一个更正式的名称是 持久的按位分区的矢量前缀树(persistent bit-partitioned vector trie)[1]。我在前篇博客介绍的其实是持久的按数字分区的前缀树(persistent digit-partitioned vector tries)是如何运行的，但是不用担心，一个按位分区前缀树只是一个按数字分区的前缀树的优化，对于上篇博客的内容来说，两者并没有区别。在本篇博客，会介绍一点两者在性能上的小区别。否则它们其实没有根本上的差异。 我猜测你可能并不了解上面段落提到的这些术语，所以我将在下文一一解释。 持久性 在上一篇博客，我使用了术语持久性（persistent）。我说我们想要数据结构是持久的，但是并没有真正解释到底持久性本身意味着什么。 一个称为持久的数据结构并不修改它自己本身：严格来讲，他们并不一定要在内部是不可变的，只是需要被（外界）认为是不可变的。无论何时你在一个持久的数据结构上执行了更新、插入或者删除操作，一个新的数据结构将返回给你。老的版本仍然是一致的，并且无论什么时候你给它一个输入，它总是返回同样的输出（译者注：也就是没有副作用，side effects）。 当我们谈论一个 完全 持久的数据结构的时候，这个数据结构的任何版本都是可以修改的，意思是作用在某个版本上的所有可能的操作，都可以作用在另一个版本上。在早期的『函数式数据结构』时代，更常见的方式是和数据结构一起『欺骗』，通过修改内部结构让老的版本随着时间逐渐『腐朽』，同时跟最新版本相比是越来越慢。虽然如此，Rich Hickey（译者注：Clojure 作者）决定让 Clojure 持久数据结构的所有版本都有一样的性能承诺，无论你正在使用的是数据结构的哪个版本。 矢量(Vector) 一个矢量就是一个一维的可增长的数组。例如 C++ 的 std::vector 或者 Java 的 java.util.ArrayList 就是可变矢量的实现。实际上也没有比这个更多的解释了。一个矢量前缀树是指一棵用来表示矢量的前缀树(trie)。它并不一定必须是持久的，但是在我们这里介绍的是持久的。 前缀树（Trie) 前缀树是特殊的一种树，我想最好先解释更多的常见的树来展示前缀树的实际不同之处。 在红黑树和其他类型的二叉树里，映射或者元素存在于内部的节点上。选择正确的分支是通过比较元素/关键字(key)和当前节点来确定的：如果元素比当前节点的元素小，那么我们选择左分支，如果更大，我们就走到右分支。叶子节点通常都是空指针或者 nil，不包含任何东西。 “Example red-black tree” by Cburnett, CC-BY-SA 3.0 上面图中的红黑树是从维基百科的文章里摘录过来的。我并不想详细介绍它是如何运作的的，但是我们选择一个小小的例子，看看我们是如何判断 22 是否在这棵红黑树里： 我们从根节点 13 开始，和 22 对比下。因为 13 < 22，所以我们进入右分支。 新节点包含了 17，和 22 对比。因为 17 < 22，我们仍然进入右分支。 下一个我们进入的节点是 25。因为 25 > 22，我们进入左分支。 下一个节点是 22，因此我们知道 22 包含在这棵树里。 如果你想知道关于红黑树的更好的解释，我推荐你阅读 Julienne Walker 的 红黑树教程。

前言 原文地址：http://hypirion.com/musings/understanding-persistent-vector-pt-1 这系列博客对理解 clojure vector 实现很有帮助。尝试翻译下，许久没有做这样的工作，很可能有谬误的地方，欢迎指正。 正文 你可能或多或少听说过 Clojure 的 Perisistent Vectors。它是由 Clojure 的作者 Rich Hickey 发明的（受到 Phil Bagwell 论文 Ideal Hash Trees 的影响），能做到增、改、查和 subvec （截取片段）操作近乎 O(1) 的时间复杂度，并且每个修改操作都创建一个新的 vector，而不是修改原来的。 那么，它们是如何做到这一点的呢？我将尝试通过一系列博客来解析整个实现，每篇博客关注一部分。这将是一次深入细节的解析，包括围绕在实现层面上的一些不同的、看起来略显怪异的东西。 今天，我们将学习一些基础的知识，包括更新(update)、添加(append)和出队(pop)。Clojure 的 PersistentVector 使用这些基础操作作为核心，并且采用了一些优化性能的技巧，例如 transient vector 和 tail （vector 末尾）引用。我们将在后续的博客里解析这些技巧。 基本理念 可变（mutable）的 vector 或者 ArrayList 都只是数组，根据需求自动增长或者缩小。当你接受可变性(mutability)的时候，这没有问题，一切工作的很好，但是当你想要持久性（persistence）的时候，这将是个大问题。你的修改操作将变得非常缓慢，并且耗费大量的内存，因为每次修改你都不得不总是去拷贝整个数组。如果有什么办法能够在不损失查找、更新操作性能的前提下，避免数据的重复拷贝，一切将变得非常美好。而这就是 clojure persistent vector 所实现的，在平衡有序树（balanced, ordered trees)的基础上实现。 基本的思路就是实现一个类似二叉树的数据结构。唯一的区别是它的内部节点最多只有两个子节点，并且不包含元素自身。元素是有序的，也就是最左叶子节点的元素就是第一个元素，而最后一个元素就在最右叶子节点上。暂时地，我们要求所有的叶子节点都在同一个深度上（注释1）。作为例子，我们看看下面这棵树：它包括 0 -8 范围的整数，0 在第一个位置，8 在最后面。数字 9 表示 vector 的大小： 如果我们想添加一个新的元素到 vector 末尾，并且假设 vector 还是可变的(mutable)，我们将 9 插入到最右的叶子节点，如图： 但是问题在这里：如果我们希望 vector 是不可变的，也就是持久（persistent）的时候，这显然行不通，因为我们想做的是去更新一个元素！我们必须拷贝整个数据结构，或者至少是部分。