Common Lisp中ELT函数针对不同序列类型的时间复杂度

Great question! While the HyperSpec and Common Lisp the Language don't explicitly spell out the time complexity for elt on vectors or strings, we can infer it confidently from how these sequence types are defined and how conforming implementations behave.

Vectors (vectorp sequences) #

Vectors are one-dimensional arrays in Common Lisp—they're a specialized subtype of the array type. The core defining feature of arrays in Common Lisp is that they support random access, meaning accessing any element by its index takes constant time (O(1)).

When you call elt on a vector, it's essentially a wrapper around the array-specific aref function. Since aref is universally implemented as O(1) for all arrays (including vectors) in conforming Common Lisp systems, elt on vectors will also have an O(1) time complexity. Every major implementation (SBCL, Clozure CL, Allegro CL, etc.) follows this behavior because it's fundamental to how arrays work in the language.

Strings #

Strings in Common Lisp are character vectors—they're instances of (vector character), which means stringp implies vectorp. Because of this, strings inherit all the random-access properties of vectors.

Calling elt on a string (e.g., (elt "common lisp" 4)) works exactly like calling it on any other vector: it directly accesses the character at the specified index without traversing from the start. So elt on strings is also O(1).

Why the standards don't explicitly state this #

The Common Lisp standards prioritize semantics (what functions are supposed to do) over strict performance guarantees. However, they do define arrays (and by extension vectors/strings) as supporting random access. Conforming implementations have no reason to implement these operations as anything other than O(1)—it's the natural and efficient way to handle array-based sequences.

To contrast, lists are linked lists, so elt has to traverse from the head of the list to the nth element, resulting in O(n) time complexity. This is a fundamental difference in the underlying data structures, not just an implementation choice.

内容的提问来源于stack exchange，提问作者MadPhysicist