Lisp gethash复杂性

ANSI CL 标准 不指定 图书馆的职能是它不是它的工作。本标准描述了 ,然后离开 演出

回答你的具体问题, gethash O(1) 在所有实现中。

通常期望GETHASH的Lisp实现在 O(1) .

复制垃圾收集器 (某些gc是)可能会复制内存中的哈希表。这可能会触发表的重新刷新。

标准没有也不应该告诉你函数的复杂性,比如 gethash . 想象一下,如果它这样做了:这将限制语言的实现使用符合标准复杂性的函数的实现。如果有人提出了更好的哈希函数,那么实现就不能使用它。

好吧,你可以说,这很愚蠢:标准只需要具体说明 上界

有些情况下,从标准来看,事物的复杂性是显而易见的:很明显,事物的时间复杂性 length 在列表长度上是线性的(除非列表是循环的,否则它可能不会终止)。但事实并非如此:没有任何东西可以阻止实现在某个地方维护一个长度值,这将使 在某些情况下保持时间不变。这显然是一个英雄式的(我认为在实现上是不可信的)和无用的优化,但它不是标准中排除它的地方。

例如一种语言(不是CL的实现)像这样的事情会不会考虑到这个关于球拍的描述 list? 谓语:

退换商品 #t 如果 v 是一个列表:要么是空列表,要么是第二个元素是列表的对。由于内部缓存的原因,此过程有效地占用了固定的时间(因此,对的任何必要遍历原则上都可以算作分配对的额外成本)。