Lisp gethash 复杂度
Lisp gethash complexity
gethash函数的时间复杂度是多少？
例如，在 c++ 中，map 的搜索采用 O(log(n))，而 unordered_map 的搜索采用 O(1)。这两件事都写在描述中，但我在 Lisp.
中找不到 gethash 的任何此类参考
实际上，这扩展到所有标准库函数。我在哪里可以找到它们的复杂性，或者我可以？谈论 sbcl，如果这很重要的话。
ANSI CL 标准 没有指定算法复杂度的原因
库函数是它不是它的工作。该标准描述了 行为 ，并将 性能 留给特定于实现的文档。
假定所有实现都将提供最好的理论性能（否则没有人会使用它）。
为了回答您的具体问题，gethash 在所有实现中都是 O(1)。
通常的期望是 GETHASH 的 Lisp 实现在 O(1).
内运行
但它可能有惊人的隐性成本。 复制垃圾收集器（某些 GC 是）可能会在内存中复制哈希-table。这可能会触发 table.
的重新散列
标准没有也不应该告诉你像 gethash 这样的函数的复杂性。想象一下，如果它确实这样做了：这将限制语言的实现，以使用符合标准复杂性的函数实现。如果有人想出了一个更好的散列函数，那么实现就无法使用它。
好吧，您可能会争辩说，这很愚蠢：标准只需要指定 上限 复杂性。这将允许实现使用它喜欢的任何更好的函数，对吗？但这也不是答案：可能存在（并且在许多情况下）算法具有糟糕的最坏情况性能但预期性能要好得多。要在标准中处理这个问题要么是不可能的（我认为），要么会导致它完全被复杂的描述所覆盖，这些描述可以接受什么复杂性以及什么时候和什么时候不可以接受。
提供复杂性上限也会排除那些想要在（比如）实现的复杂性和规模以及在某些情况下它的性能如何之间进行权衡的实现：应该允许一个实现具有哈希表，这些哈希表是， inside, alists，例如：对于少量的键，它们通常非常快，但是对于大量的键，它们的性能会下降。应该允许这样的实现。
在某些情况下，事物的复杂性在标准中是显而易见的：似乎很明显 length 的时间复杂度与列表的长度呈线性关系（除了它可能如果列表是循环的，则不会终止）。但事实并非如此：在某些情况下，没有什么可以阻止实现在某处维护长度值，这会使 length 成为恒定时间。这显然是一个英雄（我认为在实现上难以置信）和无用的优化，但这不是排除它的标准的地方。
作为语言（不是 CL 的实现！）执行类似操作的示例，请考虑对 Racket 的 list? 谓词的描述：
Returns #t if v is a list: either the empty list, or a pair whose second element is a list. This procedure effectively takes constant time due to internal caching (so that any necessary traversals of pairs can in principle count as an extra cost of allocating the pairs).
我不完全理解这一点，但我认为 Racket 在其 cons 对象中必须在实现上有一个标志，告诉你它的 cdr 是一个正确的列表，然后依靠不变性来知道这是真的它永远是真的。如果 CL 有这样的功能，那么在常数时间内运行就更难了。
gethash函数的时间复杂度是多少？
例如，在 c++ 中，map 的搜索采用 O(log(n))，而 unordered_map 的搜索采用 O(1)。这两件事都写在描述中，但我在 Lisp.
gethash 的任何此类参考
实际上，这扩展到所有标准库函数。我在哪里可以找到它们的复杂性，或者我可以？谈论 sbcl，如果这很重要的话。
ANSI CL 标准 没有指定算法复杂度的原因 库函数是它不是它的工作。该标准描述了 行为 ，并将 性能 留给特定于实现的文档。 假定所有实现都将提供最好的理论性能（否则没有人会使用它）。
为了回答您的具体问题，gethash 在所有实现中都是 O(1)。
通常的期望是 GETHASH 的 Lisp 实现在 O(1).
内运行但它可能有惊人的隐性成本。 复制垃圾收集器（某些 GC 是）可能会在内存中复制哈希-table。这可能会触发 table.
的重新散列标准没有也不应该告诉你像 gethash 这样的函数的复杂性。想象一下，如果它确实这样做了：这将限制语言的实现，以使用符合标准复杂性的函数实现。如果有人想出了一个更好的散列函数，那么实现就无法使用它。
好吧，您可能会争辩说，这很愚蠢：标准只需要指定 上限 复杂性。这将允许实现使用它喜欢的任何更好的函数，对吗？但这也不是答案：可能存在（并且在许多情况下）算法具有糟糕的最坏情况性能但预期性能要好得多。要在标准中处理这个问题要么是不可能的（我认为），要么会导致它完全被复杂的描述所覆盖，这些描述可以接受什么复杂性以及什么时候和什么时候不可以接受。
提供复杂性上限也会排除那些想要在（比如）实现的复杂性和规模以及在某些情况下它的性能如何之间进行权衡的实现：应该允许一个实现具有哈希表，这些哈希表是， inside, alists，例如：对于少量的键，它们通常非常快，但是对于大量的键，它们的性能会下降。应该允许这样的实现。
在某些情况下，事物的复杂性在标准中是显而易见的：似乎很明显 length 的时间复杂度与列表的长度呈线性关系（除了它可能如果列表是循环的，则不会终止）。但事实并非如此：在某些情况下，没有什么可以阻止实现在某处维护长度值，这会使 length 成为恒定时间。这显然是一个英雄（我认为在实现上难以置信）和无用的优化，但这不是排除它的标准的地方。
作为语言（不是 CL 的实现！）执行类似操作的示例，请考虑对 Racket 的 list? 谓词的描述：
Returns
#tif v is a list: either the empty list, or a pair whose second element is a list. This procedure effectively takes constant time due to internal caching (so that any necessary traversals of pairs can in principle count as an extra cost of allocating the pairs).
我不完全理解这一点，但我认为 Racket 在其 cons 对象中必须在实现上有一个标志，告诉你它的 cdr 是一个正确的列表，然后依靠不变性来知道这是真的它永远是真的。如果 CL 有这样的功能，那么在常数时间内运行就更难了。