PROSAGA码农传奇-lisp-Lisp gethash的复杂性

<div class =“post-text”itemprop =“text”>
  
    标准不会也不应该告诉你功能的复杂性
     <code>
 gethash
 </code>
    。想象一下，如果确实这样做了：这会限制语言的实现，以使用与标准中的复杂性一致的函数实现。如果有人提出了更好的散列函数，那么实现就无法使用它。
  
  
    嗯，你可以说，这很愚蠢：标准只需要指定
    
      上限
    
     复杂性。这将允许实现使用它喜欢的任何更好的功能，对吧？但这也不是一个答案：可能（并且在许多情况下）算法具有可怕的最坏情况性能但是预期性能要好得多。处理标准中的内容要么是不可能的（我认为），要么完全由复杂的描述来完全涵盖哪些复杂性是可接受的以及何时何时不可接受。
  
  
    提供上层复杂性限制也会排除想要在实现之间进行权衡的实现（例如）实现的复杂程度和性能以及在某些情况下性能如何：应该允许实现具有哈希表，其中包含内部的哈希表，实例：对于少量密钥，这些密钥通常非常快，但是对于大量密钥，它们的性能会下降。应该允许这样的实现。
  
  <HR />
  
    在某些情况下，事物的复杂性从标准中显而易见：似乎很明显时间的复杂性
     <code>
 length
 </code>
     在列表的长度上是线性的（除非如果列表是圆形的，它可能不会终止）。但事实并非如此：没有什么可以阻止实现在某个地方保持长度值
     <code>
 length
 </code>
     在某些情况下是恒定的时间。这显然是一个英雄（我认为在实现上难以理解）和无用的优化，但它不是标准的地方来排除它。
  
  
    作为一个语言（不是CL！的实现）做这样的事情的例子考虑这个Racket的描述
     <code>
 list?
 </code>
     谓语：
  
  <BLOCKQUOTE>
    
      返回
       <code>
 #t
 </code>
       如果
      
        v
      
       是一个列表：空列表，或第二个元素是列表的对。由于内部缓存，此过程有效地占用了恒定的时间（因此任何必要的对遍历原则上都算作分配对的额外成本）。
    
  </BLOCKQUOTE>
  
    我并不完全理解这一点，但我认为Racket必须在其cons对象中实现一个标志，它告诉你它的cdr是一个正确的列表，然后依靠不变性来知道这是永远的，它总是如此。如果CL具有这样的功能，那么使它在恒定时间内运行将非常困难。
  
</DIV>