Scheme向量的复杂性

Question

Scheme R5RS标准中的6.3.6 Vectors部分说明了以下关于向量的内容:

向量是异构结构,其元素由整数索引.向量通常比相同长度的列表占用更少的空间,并且访问随机选择的元素所需的平均时间通常小于向量而不是列表.

矢量的这种描述有点分散.

我想知道这是什么真正意味着条款vector-ref和list-ref操作及其复杂性.两个过程都返回向量的第k个元素和列表.向量运算是O(1)并且是列表运算O(n)吗？矢量与列表有何不同？我在哪里可以找到更多相关信息？

现在我正在使用关联列表作为存储键/值对的数据结构,以便于查找.如果键是整数,那么使用向量来存储值可能会更好.

Answer 1

vector-ref和的非常具体的细节list-ref取决于实现，这意味着：每个Scheme解释器都可以实现它认为合适的规范，因此您的问题的答案不能推广到所有符合R5RS的解释器，这取决于您的实际解释器重新使用。

但是，是的，在任何像样的实现中，可以安全地假设操作vector-ref是 O(1)，并且操作list-ref可能是 O(n)。为什么？因为向量在底层应该使用实现语言本机的数据结构来实现，这允许 O(1) 访问给定索引的元素（例如，原始数组） - 因此使实现变得简单vector-ref。而 Lisp 中的列表是通过链接创建的cons单元格创建的，在任何给定索引处查找元素都需要遍历列表中该元素之前的所有元素 - 因此复杂度为 O(n)。

作为旁注 - 是的，使用向量将比使用键/值对的关联列表更快，只要键是整数并且要索引的元素数量事先已知（Scheme 向量不能增长其值）创建后的大小）。对于一般情况（整数以外的键、可变大小），请检查您的解释器是否支持哈希表，或使用提供它们的外部库（例如SRFI 69）。