lisp - cdr时间分析

Question

我无法找到时间复杂度分析cdr。它以恒定时间还是线性时间运行？如果答案取决于 lisp 的实现，假设我使用的是 Racket。

Answer 1

cdr可以预期在任何 Lisp 中都需要恒定的时间。这只是查找cons单元格中的第二个成员。

Answer 2

就 C 而言，lisp 对只是一个struct具有两个字段的 acar和cdr。lisp 的功能car和cdr数量只需 C 访问每个字段。

以下是Racket 的部分内容scheme.h：

typedef struct Scheme_Simple_Object
{
  Scheme_Inclhash_Object iso;

  union
    {
      struct { mzchar *string_val; intptr_t tag_val; } char_str_val;
      struct { char *string_val; intptr_t tag_val; } byte_str_val;
      struct { void *ptr1, *ptr2; } two_ptr_val;
      struct { int int1; int int2; } two_int_val;
      struct { void *ptr; int pint; } ptr_int_val;
      struct { void *ptr; intptr_t pint; } ptr_long_val;
      struct { struct Scheme_Object *car, *cdr; } pair_val;
      struct { mzshort len; mzshort *vec; } svector_val;
      struct { void *val; Scheme_Object *type; } cptr_val;
    } u;
} Scheme_Simple_Object;

注意这部分union：

      struct { struct Scheme_Object *car, *cdr; } pair_val;

后来scheme.h你发现：

#define SCHEME_CAR(obj)      (((Scheme_Simple_Object *)(obj))->u.pair_val.car)
#define SCHEME_CDR(obj)      (((Scheme_Simple_Object *)(obj))->u.pair_val.cdr)

当然，Racketcdr函数会比这个 C 宏做更多的工作，比如检查它是否被赋予了pair?.

Answer 3

一对的球拍定义谈论car和cdr作为对访问器，因此间接地将其指定为 O(1)。要使其成为 O(n)，cdr您必须将其反转，这butlast不符合球拍文档。

Rackets 母语 Scheme 有一个R6RS 规范，其中car和cdr是 a 中字段的访问者pair，也间接 O(1)。

在Common Lisp中，Scheme 的一种美食，有类似的描述，唯一的区别是他们使用名称cons而不是pair在他们的规范中。（你标记了 lisp）

不过这并不奇怪，因为cons/是由John McCarthy 的 LISPpairs定义的基本数据类型，它是所有 LISP 之母，并且它的第一个实现具有汇编指令，该指令从内存位置检索称为地址和减量的东西以及字母 a 和 d /来自该术语。carcdr