hi,
I know that `length' is expensive on lists. How about on arrays?
(setq a (vector 1 2 ,..., 10000))
(length a)
how efficient is the above function call to `length'? I am hoping
that it's usually gonna be O(1).
thanks,
dave
David Bakhash wrote:
> I know that `length' is expensive on lists. How about on arrays?
It's O(1) in every implementation I've seen.
-- Scott
* * * * *
To use the email address, remove all occurrences of the letter "q".
"Scott L. Burson" <·····@zeta-sqoft.com> writes:
> David Bakhash wrote:
> > I know that `length' is expensive on lists. How about on arrays?
>
> It's O(1) in every implementation I've seen.
I suppose in principle it's possible for a conforming implementation
to count, making it O(n) for length n. But it's expected that the
commercial marketplace will sort such dialects to the bottom by poor
benchmarks.
I once tried to get people excited about specifying the algorithmic
complexity of some or all functions, which I think is as important as
the functional correctness. But it was considered to be something
that was both not done in other standards and it was also considered
"hard". We certainly did have enough on our plate, so I couldn't
blame people. Confusion over how to "test conformance" and over the
matter of "speed for small cases" vs "asymptotic speed" were
unexplored minefields. (Just consider the GETHASH problem to see the
issue--usually it's fast, but if the hash table is dirty and a rehash
has to be done... it's awful. Then again, it's to avoid surprise over
that GETHASH lag that made me think it needed to be specified in the
first place.)