time-complexity - Common Lisp 中各种序列类型的 ELT 函数的时间复杂度

Question

我试图了解 ELT函数适用于不同的序列类型。

很明显，当一个列表被传递给它时，性能是顺序 O(n) .
说从 VECTORP 中获取元素是真的吗？顺序是O(1) ?
一个字符串呢？

这似乎没有在 HyperSpec 上指定或 Common Lisp 语言。

Answer 1

一般来说，ANSI CL 标准没有规定实现
详细信息 - 包括诸如此类的性能问题。另一个例子
是尾调用消除，由 Scheme 而不是 CL 强制执行。
当然，这并不意味着标准的作者是
无视性能(参见每个
issue写上去)。

也就是说，您可以放心地假设 elt 是 O(1)在
vector s(包括 string s)。

我不认为 elt 虽然经常使用 - 主要是因为一个
通常知道是否是 vector 或 list 实际使用。
使用
aref / char / nth
作为额外的代码文档。

附注。 CL 和 Scheme 之间存在这种巨大差异的基本原理是，Scheme 起源于教学:它的用户是新学生，他们应该学习计算机编程作为表达算法思想的方法，因此他们应该拥有一个相对简单的工具，并具有明确定义的行为。
ANSI CL history表明该标准是几个现有供应商努力提出一些共同点以提高可移植性的结果 - 可以说是使竞争更加公平。听众是经验丰富的程序员，他们了解权衡并理解性能权衡。