Mad*_*ist 5 element common-lisp sequence time-complexity
我试图了解ELT函数在不同序列类型时的工作原理.
很明显,当列表传递给它时,性能就是有序的O(n).是否可以说从VECTORP序列中获取元素是有序的O(1)？怎么样的字符串？
这似乎没有在HyperSpec或Common Lisp The Language 上指定.
一般来说,ANSI CL标准没有规定实现细节 - 包括诸如此类的性能问题.另一个例子是尾调用消除,由Scheme强制但不是CL.当然,这并不意味着该标准的作者没有注意到性能(参见每个问题的 "性能影响"部分 ).
这就是说,你可以安全地假设elt是O(1)对
vectorS(包括串 S).
我不认为elt经常使用 - 主要是因为人们通常知道a vector或a list是否实际使用过.使用
aref/ char/ nth
作为额外的代码文档.
PS.CL和Scheme之间这种巨大差异的基本原理是Scheme的起源是教学:它的用户是新生,应该学习计算机编程作为表达算法思想的方法,因此他们应该有一个相对简单的工具,具有明确定义的行为.ANSI CL的历史表明,该标准是几个现有供应商努力提出一些共同点以提高可移植性的结果 - 可以说竞争更加公平.观众是经验丰富的程序员,他们了解交易并且能够理解绩效权衡.