Re: Is there a way to convert a keyboard macro to a string?

[John Mastro <john.b.mastro@gmail.com>]

Emanuel Berg <moasen@zoho.com> wrote:
> Yes, constant access time instead of linear.
> Different data structures.
>
> Temporal complexity... or perhaps spacial?
> I don't remember.
>
> But *how* does this happen?

This is off course simplified and just for illustration, but think of
the respective structures like this:

struct vector {
    Lisp_Value *elts;
};

struct cons {
    Lisp_Value car, cdr;
};

A call like (nth n seq) then boils down to something like:

/* Vector - a single array access by index */
return vector->elts[n];

/* Cons */
while (n-- > 0) /* This loop is what makes it O(N) */
    cons = cdr(cons);
return car(cons);

That's how it happens :)

        John