clojure - 作为数据容器，vector和list的主要区别是什么

Question

假设我们需要一个数字列表，有两个定义：

(def vector1 [1 2 3])
(def list2 '(1 2 3))

那么主要的区别是什么？

Answer 1

是[1 2 3]一个向量，而是'(1 2 3)一个列表。这两种数据结构有不同的性能特征。

向量提供对其元素的快速、索引随机访问，并在索引处及时(v 34)返回向量的元素。另一方面，修改向量通常更昂贵。v34O(1)

列表很容易在头部和/或尾部修改（取决于实现），但提供对元素的线性访问：(nth (list 1 2 3 4 5) 3)需要对列表进行顺序扫描。

有关性能权衡的更多信息，您可以谷歌“向量与列表性能”或类似的东西。

[跟进]

好的，让我们更详细地介绍一下。首先，向量和列表不是 Clojure 特有的概念。与地图、队列等一起，它们是数据集合的抽象类型。对数据进行操作的算法是根据这些抽象定义的。向量和列表是由我在上面简要描述的行为定义的（即，如果某个东西有大小，那么它就是一个向量，您可以通过常数时间的索引来访问它的元素等）。

Clojure 与任何其他语言一样，希望在提供以这种方式调用的数据结构时满足这些期望。如果你看一下 in 的基本实现nthvector，你会看到一个arrayFor复杂度为O(log ₃₂ N)的方法调用和一个在 Java 数组中查找O(1)的方法。

为什么我们可以说这(v 34)实际上是O(1)？因为Java的log ₃₂最大值int约为7。这意味着对向量的随机访问实际上是常数时间。

vectors总而言之，和lists真的主要区别在于性能特征。此外，正如 Jeremy Heiler 所指出的，在 Clojure 中，行为存在逻辑上的差异，即关于使用conj.

Answer 2

列表和向量之间有两个主要区别。

1. 列表在逻辑上在头部增长，而向量在逻辑上在尾部增长。您可以在使用该conj功能时看到这一点。它将根据给它的集合类型来增长集合。虽然您可以在任一侧增加集合，但以这种方式这样做是高效的。

2. 为了检索列表中的第 n 个项目，需要从头开始遍历列表。另一方面，向量不会被遍历并返回 O(1) 中的第 n 个项目。（它确实是 O(log32n) 但这是由于集合是如何作为持久集合实现的。）

Answer 3

• 向量将所有数据项保存在内存的相邻区域中，与列表相比，使整个向量的传输变得容易，并且插入或删除项的成本很高。

• 列表保存项目是不相交的内存区域，使得整个列表的传输成本很高，但单个项目的插入和删除相对便宜。

• 经典向量的大小也是固定的，并且仅限于 N 个项目，而列表可以动态增长和收缩。

• 向量还提供对元素项的索引访问。列表没有。经典向量的前身是一个数组。
• 向量的现代实现通常旨在提供类似的特征，但底层数据结构实际上可能是列表或散列，并且这些向量通常支持动态调整大小。

Answer 4

矢量评估时间不是 O(1) 它是 log32N

向量 (IPersistentVector) 向量是由连续整数索引的值的集合。向量支持按 log32N 跃点中的索引访问项目。计数为 O(1)。conj 将项目放在向量的末尾。向量还支持 rseq，它以相反的顺序返回项目。对于一个参数的invoke()，向量实现IFn，它们假定它是一个索引，并在自身中查找，就好像第n个一样，即向量是它们索引的函数。