cdr的时间分析

Question

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

Answer 1

cdr可以预期在任何Lisp中都需要花费一些时间.它只是查找cons单元格中的第二个成员.

Answer 2

根据C来思考,lisp对只是一个struct有两个字段,car和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)

当然,Racket cdr函数将比这个C宏做更多的工作,例如检查它是否被赋予了pair?.