Scheme R5RS 标准中的6.3.6 向量部分说明了以下有关向量的内容：
向量是异构结构，其元素由整数索引。向量通常比相同长度的列表占用更少的空间，并且访问随机选择的元素所需的平均时间对于向量通常比列表少。
这种对向量的描述有点分散。
我想知道这在and操作及其复杂性方面实际上意味着什么。两个过程都返回向量和列表的第 k 个元素。向量运算是 O(1) 还是列表运算 O(n)？向量与列表有何不同？我在哪里可以找到有关此的更多信息？vector-reflist-ref
现在我使用关联列表作为存储键/值对的数据结构，以便于查找。如果键是整数，那么使用向量来存储值可能会更好。
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）。
列表由单元格cons构成。从R 5 RS 列表部分：
列表的连续对的汽车字段中的对象是列表的元素。例如，双元素列表是一个对，其 car 是第一个元素，其 cdr 是一个对，其 car 是第二个元素，其 cdr 是空列表。列表的长度是元素的数量，与对的数量相同。
例如，该列表(a b c)等效于以下一系列对：(a . (b . (c . ())))
并且可以通过以下“节点”在内存中表示：
[p] --> [p] --> [p] --> null
| | |
|==> a |==> b |==> c
每个节点都[]包含一个指向p值的指针 (it's car)，以及另一个指向下一个元素的指针 (it's cdr)。
这允许列表增长到无限长度，但需要一个ref操作从列表的前面开始并遍历k元素以找到请求的元素。正如你所说，这是O（n）。
相比之下，向量基本上是一个值数组，可以在内部表示为指针数组。例如，向量#(a b c)可能表示为：
[p p p]
| | |
| | |==> c
| |
| |==> b
|
|==> a
其中数组[]包含一系列三个指针，每个指针都分配给向量中的一个值。v所以在内部你可以使用符号引用向量的第三个元素v[3]。由于您不需要遍历前面的元素，vector-ref因此是 O(1) 操作。
主要缺点是向量的大小是固定的，因此如果您需要添加的元素多于向量可以容纳的数量，则必须分配一个新向量并将旧元素复制到这个新向量中。如果您的应用程序定期执行此操作，这可能是一项昂贵的操作。
网上有很多资源——这篇关于Scheme 数据结构的文章更详细地介绍并提供了一些示例，尽管它更侧重于列表。
综上所述，如果您的键是（或可以成为）整数，并且您具有固定数量的元素，或者可以通过合理数量的向量重新分配来管理 - 例如，您在启动时加载向量，然后主要执行读取 - 一个向量可能是关联列表的一个有吸引力的替代方案。