Common Lisp 中各种序列类型的 ELT 函数的时间复杂度
Time Complexity of ELT Function in Common Lisp for Various Sequence Types
我试图了解 ELT 函数在涉及不同序列类型时的工作原理。
很明显，当一个列表被传递给它时，性能是有序的O(n)。
从VECTORP序列中获取一个元素是有序的O(1)是真的吗？
字符串呢？
这似乎没有在 HyperSpec 或 Common Lisp The Language 中指定。
一般来说，ANSI CL标准并没有规定实现
详细信息 - 包括诸如此类的性能问题。另一个例子
是尾调用消除，由 Scheme 而非 CL 强制执行。
当然，这并不意味着该标准的作者是
忽略性能（参见每个中的 "performance impact" 部分
issue 写了）。
也就是说，您可以安全地假设 elt 是 O(1)
vectors (including strings).
我不认为 elt 经常被使用——主要是因为一个
通常知道是否实际使用了 vector or a list。
使用
aref/char/nth
作为额外的代码文档。
PS。 CL 和 Scheme 之间这种巨大差异的基本原理是，Scheme 的起源是 教学 ：它的用户是新学生，他们应该学习计算机编程作为一种表达算法思想的方法，因此他们应该有一个相对简单的工具，具有明确定义的行为。
ANSI CL 的 history 表明该标准是几家现有供应商为更好的可移植性提出一些共同点而努力的结果 - 可以这么说，使竞争更加公平。观众是经验丰富的程序员，他们了解交易并且可以理解性能权衡。
我试图了解 ELT 函数在涉及不同序列类型时的工作原理。
很明显，当一个列表被传递给它时，性能是有序的O(n)。
从VECTORP序列中获取一个元素是有序的O(1)是真的吗？
字符串呢？
这似乎没有在 HyperSpec 或 Common Lisp The Language 中指定。
一般来说，ANSI CL标准并没有规定实现 详细信息 - 包括诸如此类的性能问题。另一个例子 是尾调用消除，由 Scheme 而非 CL 强制执行。 当然，这并不意味着该标准的作者是 忽略性能（参见每个中的 "performance impact" 部分 issue 写了）。
也就是说，您可以安全地假设 elt 是 O(1)
vectors (including strings).
我不认为 elt 经常被使用——主要是因为一个
通常知道是否实际使用了 vector or a list。
使用
aref/char/nth
作为额外的代码文档。
PS。 CL 和 Scheme 之间这种巨大差异的基本原理是，Scheme 的起源是 教学 ：它的用户是新学生，他们应该学习计算机编程作为一种表达算法思想的方法，因此他们应该有一个相对简单的工具，具有明确定义的行为。 ANSI CL 的 history 表明该标准是几家现有供应商为更好的可移植性提出一些共同点而努力的结果 - 可以这么说，使竞争更加公平。观众是经验丰富的程序员，他们了解交易并且可以理解性能权衡。