length
Josef Eschgfaeller
How fast is length for strings (or vectors)? If I understand well,
when there is a fill pointer, the result should be immediate. But
for a normal string, does Lisp go through memory until a terminating
symbol is reached, or is there always a value associated to each
string, which gives the length? I suspect the first one is true.
J. Eschgfaeller
Nick Levine
Josef Eschgfaeller wrote in message ...
>
>How fast is length for strings (or vectors)? If I understand well,
>when there is a fill pointer, the result should be immediate. But
Indeed it ought.
>for a normal string, does Lisp go through memory until a terminating
>symbol is reached, or is there always a value associated to each
>string, which gives the length? I suspect the first one is true.
I guess it's up to the implementation, but I find it hard to imagine an
implementor not caching the length of the string in an easily accessible
location.
If you want to be paranoid, time length on strings of length 1000 , 10000,
100000, 1000000 etc on your implementation. Should take the same time (naff
all) in each case.
- n
Josef Eschgfaeller
Nick Levine wrote:
> I guess it's up to the implementation, but I find it hard to imagine an
> implementor not caching the length of the string in an easily accessible
> location.
> If you want to be paranoid, time length on strings of length 1000 , 10000,
> 100000, 1000000 etc on your implementation. Should take the same time (naff
> all) in each case.
No, it takes much longer for a long string. For a string of 2051 chars
it takes 4 sec (with Clisp), for a string of 5171609 characters it
takes 44 sec. Why is it not linear?
And a strange thing happens. My test was
(setf a "aaaaaaaaaaaaaaaaaaaaaaaaaaaa\
...")
(format t "~a~%" (length a))
If before the format I insert (dotimes (k 2500) (length a)),
time doesn't change. Does this mean that Lisp memorizes the
result of a function and remembers it on subsequent calls?
J. Eschgfaeller
Erik Naggum
| How fast is length for strings (or vectors)?
LENGTH is a simple accessor for any subtype of ARRAY.
| But for a normal string, does Lisp go through memory until a terminating
| symbol is reached, or is there always a value associated to each string,
| which gives the length? I suspect the first one is true.
why? Common Lisp is designed, unlike C. do yourself a favor and stop
thinking in C terms. and please note that very few languages other than
C use strings that cannot hold all possible characters.
#:Erik
--
@1999-07-22T00:37:33Z -- pi billion seconds since the turn of the century
Christopher R. Barry
> No, it takes much longer for a long string. For a string of 2051 chars
> it takes 4 sec (with Clisp), for a string of 5171609 characters it
> takes 44 sec. Why is it not linear?
Because you're not testing properly.
> And a strange thing happens. My test was
>
> (setf a "aaaaaaaaaaaaaaaaaaaaaaaaaaaa\
> ...")
> (format t "~a~%" (length a))
There is a function MAKE-STRING (LENGTH &KEY INITIAL-ELEMENT ...). Try
doing:
(make-string 10000 :initial-element #\a)
(time (length *))
(make-string 1000000 :initial-element #\a)
(time (length *))
...
This is instantaneous on my clisp (1999-01-08), and indeed all my
Lisps.
Christopher
Marco Antoniotti
Same for CMUCL. Accessing the string length seems a O(1) operation.
Try this with 'strlen' :)
Cheers
--
Marco Antoniotti ===========================================
PARADES, Via San Pantaleo 66, I-00186 Rome, ITALY
tel. +39 - 06 68 10 03 17, fax. +39 - 06 68 80 79 26
http://www.parades.rm.cnr.it/~marcoxa