Time Complexity of ELT Function in Common Lisp for Various Sequence Types

Question

I am trying to get an understanding of how the ELT function works when it comes to different sequence types.

It seems obvious that when a list is passed to it, then the performance is of order O(n). Is it true to say that getting an element from a VECTORP sequence is of order O(1)? What about a string?

This does not seem to be specified on HyperSpec or Common Lisp The Language.

Choral

Answer 1

Generally speaking, the ANSI CL standard does not specify implementation details - including performance issues such as this one. Another example is tail call elimination, mandated by Scheme but not CL. This does not mean, of course, that the authors of the standard were oblivious to performance (cf. "performance impact" section in every issue writeup).

That said, you can safely assume that elt is O(1) on vectors (including strings).

I don't think elt is used very often though - mostly because one usually knows whether a vector or a list is actually used. Using aref/char/nth serves as extra code documentation.

PS. The rationale for this dramatic difference between CL and Scheme is that Scheme's origin is in teaching: its users are new students who should learn computer programming as a methodology of expressing ideas about algorithms, thus they should have a relatively simple tool with clearly defined behavior. ANSI CL's history shows that the standard was a result of an effort of several existing vendors to come up with some common ground for better portability - to make competition more fair, so to speak. The audience are seasoned programmers who know the trade and can understand performance trade offs.

Elison

Do you mean I can make a CL that is fully compliment and that stores arrays and strings as lists? – Project

@Sylwester: yes, absolutely. No one will use it thought ;-) – Elison