cdr的时间分析

Question

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

Answer 1

从C的角度来看，lisp对只是一个struct，它有两个字段，car和cdr。lisp函数的car和cdr数量只是C访问每个字段。

下面是对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)

当然，cdr函数将比这个C宏做更多的工作，比如检查它是否得到了一个pair?。

Answer 2

在任何Lisp中，cdr都会占用恒定的时间。它只是查找cons单元中的第二个成员。

Answer 3

对的定义将car和cdr视为对访问器，因此间接地将它们指定为O(1)。要使O(n)用于cdr，您必须将其反转，使其成为butlast，这将不符合racket文档。

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

在普通Lisp中，一个方案的菜肴有类似的描述，唯一的区别是他们在规范中使用的是cons而不是pair。(你的标签是lisp)

但是，这并不重要，因为cons/pairs是所有LISP之母约翰·麦卡锡的口吻定义的一种基本数据类型，而且它的第一个实现有程序集指令来检索名为来自内存位置的地址和递减的东西，car/cdr中的字母a和d就是从这个术语中提取出来的。