lisp - cdrの時間分析

Question

の時間計算量分析が見つかりませんcdr。一定時間または線形時間で実行されますか? 答えが Lisp の実装に依存する場合、Racket を使用しているとします。

Answer 1

C の観点から考えると、Lisp ペアは単純structに 2 つのフィールド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)

もちろん、Racketcdr関数は、この C マクロよりも少し多くの作業を行います。たとえば、pair?.