假设我们需要一个数字列表,有两个定义:
(def vector1 [1 2 3])
(def list2 '(1 2 3))
那么主要的区别是什么？
Paw*_*ski 33
这[1 2 3]是一个向量,而是'(1 2 3)一个列表.这两种数据结构有不同的性能特征.
载体提供快速的,其元素索引随机访问(v 34)返回向量的元素v在索引34中O(1)的时间.另一方面,修改载体通常更昂贵.
列表易于在头部和/或尾部进行修改(取决于实现),但提供对元素的线性访问:(nth (list 1 2 3 4 5) 3)需要对列表进行顺序扫描.
有关性能权衡的更多信息,您可以谷歌"矢量与列表性能"或类似的东西.
[跟进]
好的,让我们进一步了解一些细节.首先,向量和列表是不特定于Clojure的概念.与地图,队列等一起,它们是数据集合的抽象类型.对数据进行操作的算法是根据这些抽象来定义的.矢量和列表被定义由我上面简要描述的行为(即东西是一个矢量,如果它具有的大小,可以通过访问它的元素和在恒定的时间索引等).
与任何其他语言一样,Clojure在提供以这种方式调用的数据结构时希望满足这些期望.如果你看一下in的基本实现nthvector,你会看到一个arrayFor方法的调用,它具有O(log 32 N)的复杂性和Java数组中的查找,即O(1).
为什么我们可以说(v 34)实际上是O(1)？因为Java 的log 32的最大值int大约为7.这意味着对矢量的随机访问是事实上的恒定时间.
总之,主要区别vectors和lists真正的是性能特征.此外,正如Jeremy Heiler指出的那样,在Clojure中,行为存在逻辑上的差异,即在增长收集方面conj.
列表和向量之间有两个主要区别.
列表在逻辑上增长在头部,而矢量逻辑上在尾部增长.使用该conj功能时,您可以看到这一点.它将根据给定的集合类型增加集合.虽然您可以在任何一方增加集合,但以这种方式执行此操作是有效的.
为了检索列表中的第n个项目,需要从头部遍历列表.另一方面,向量不会遍历并返回O(1)中的第n个项目.(它确实是O(log32n),但这是由于集合如何实现为持久集合.)