4 ms·

Actually, in CL a list is always a linked list. It's made of a "cons" which is a two celled part of memory for holding the head (usually data but can be anythi

Actually, in CL a list is always a linked list. It's made of a "cons" which is a two celled part of memory for holding the head (usually data but can be anything) and the tail. A hash is also known to have hash behavior as opposed to, say, an rb tree. A vector is always what C++ would call an array though what CL calls an array might depend on convention (afaik it's often just a normal vector with the access calls changed to go to the correct location).

betterunix 14y ago
That does not really answer the question. Consider, for example, this question: how efficient is append i.e. for two lists of N elements, how much work will append do? It is easy to assume this will be linear work in N since append will make a copy; but does CLTL2 actually say that append cannot do work in quadratic time, or cubic time, or even exponential time? It's a valid complaint, in my opinion, and I say this as the person who promotes Lisp as an alternative to C++. I would put it in the category of "things missing from the Common Lisp standard," lumping it together with undefined behavior. In practice, this issue rarely comes up; it is generally safe to assume that no Lisp implementation will have an asymptotically worse version of a standard function than the simplest version of that function. So, for example, although the standard is silent on the matter you can safely assume that no Lisp implementation would have an nconc that is asymptotically worse than the simple linear time implementation, and you should not rely on an implementation giving you something better than that. In the C++ standard, there are definitions of running times. So, for example, the stable_sort function is guaranteed to be no worse than O(N log(n) log(n)), and no better than O(n log(n)). That is one thing that is nice about C++, so I can concede that point, though with the note that the C++ standard has its own glaring omissions that are much more disturbing than the running times of algorithms.
- flyinRyan 14y ago
  Fair point, conceded.

betterunix 14y ago

That does not really answer the question. Consider, for example, this question: how efficient is append i.e. for two lists of N elements, how much work will append do? It is easy to assume this will be linear work in N since append will make a copy; but does CLTL2 actually say that append cannot do work in quadratic time, or cubic time, or even exponential time? It's a valid complaint, in my opinion, and I say this as the person who promotes Lisp as an alternative to C++. I would put it in the category of "things missing from the Common Lisp standard," lumping it together with undefined behavior. In practice, this issue rarely comes up; it is generally safe to assume that no Lisp implementation will have an asymptotically worse version of a standard function than the simplest version of that function. So, for example, although the standard is silent on the matter you can safely assume that no Lisp implementation would have an nconc that is asymptotically worse than the simple linear time implementation, and you should not rely on an implementation giving you something better than that. In the C++ standard, there are definitions of running times. So, for example, the stable_sort function is guaranteed to be no worse than O(N log(n) log(n)), and no better than O(n log(n)). That is one thing that is nice about C++, so I can concede that point, though with the note that the C++ standard has its own glaring omissions that are much more disturbing than the running times of algorithms.

flyinRyan 14y ago
Fair point, conceded.