CODEWITHSUNDEEP
time-complexitycommon-lispsequenceelement
MadPhysicist
MadPhysicist

Reputation: 5831

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

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.

Upvotes: 6

Views: 600

Answers (1)

sds
sds

Reputation: 60054

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.

Upvotes: 9

Related Questions