wro*_*ame 4 lisp list vector common-lisp
似乎lisp中的列表可以用来push向它添加另一个元素,而数组可以vector-push-extend用来做同样的事情(如果你使用:adjustable t,除了在结尾添加一个元素.同样,pop删除列表中的第一个项目,同时vector-pop删除矢量中的最后一项.
那么lisp中列表和向量之间的区别是什么？
Rai*_*wig 13
列表由cons细胞和零组成.必须按顺序移动列表才能访问元素.在前面添加和删除元素非常便宜.其他名单位置的操作成本更高.列表可能具有空间开销,因为每个元素都存储在cons单元格中.
向量是一定长度的一维数组.如果数组是可调整的,则可能会更改其大小,但可能必须复制元素.当必须调整阵列时,添加元素是昂贵的.可调节阵列具有空间开销,因为阵列通常不以1的增量进行调整.可以通过索引直接访问所有元素.
向量是有形的东西,但是你想到的列表是一种查看几个松散连接但是分开的东西的名称.
矢量就像一个鸡蛋盒 - 它是一个带有一些固定数量的槽的盒子,每个槽都可能有或没有一个东西.相比之下,你对列表的看法更像是穿一双单独的鞋子并将他们的鞋带绑在一起."列表"实际上是一个cons小区的视图,它在蛋盒中保存了一个类似于槽的值,并且指向另一个cons小区,该小区还保存一个值并指向另一个cons小区,其中包含一个值并且可能指向其他任何东西,使其成为列表的末尾.你认为列表并不是真正的一件事,而是它是几个不同的利弊细胞之间的关系.
你是正确的,你可以在两种结构上执行一些操作,但它们的时间复杂性是不同的.对于列表,将项目推到前面并不会实际修改有关现有列表的任何内容; 相反,它意味着制作一个新的cons单元格来表示列表的新头部,并将该cons单元格指向现有列表作为新尾部.这是O(1)操作; 列表的长度并不重要,因为在它前面放置一个新单元格总是花费相同的时间.同样,弹出列表前面的项目不会更改现有列表; 它只是意味着将你的视图从当前头部转移到一个单元格以查看第二个项目是什么作为新头部.
相比之下,使用矢量,将新项目推到前面需要首先将所有现有项目移动一个空间以在开头留下空白空间 - 假设矢量中有足够的空间来容纳所有现有项目和另外一个.这种转换具有时间复杂度O(n),这意味着向量中的项目越多,将它们移动并为新项目腾出空间所需的时间就越长.类似地,从向量的前面弹出需要移动所有现有的项目,但是第一个向下移动到前面,这样第二个成为第一个,第三个成为第二个,依此类推.再次,这是时间复杂度O(n).
有时候可以在矢量中摆弄簿记,这样从前面弹出一个项目就不需要将所有现有物品移过来了; 相反,只需更改哪个项目的记录为第一个.您可以想象这样做有很多挑战:需要调整用于访问项目的索引,向量的容量不再易于解释,并且为向量重新分配空间以容纳新项目现在需要考虑在哪里留下新项目将现有数据复制到新存储后可用的空白空间.在"双端队列"的结构解决了这些问题.
在列表和向量之间进行选择需要考虑您打算如何处理它,以及您对事物的性质和大小提前了解多少.他们每个人都在不同的场景中唱歌,尽管他们的目的明显重叠.
当我写上面的答案时,问题是询问从向量和列表的前面推送和弹出元素.在向量的末尾操作as vector-push和vector-popdo更类似于操纵列表的头部而不是上面的比较中的区别.根据向量的容量是否可以容纳另一个元素而不重新分配,在向量的末尾推送和弹出元素需要恒定(O(1))时间.