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
Josef Eschgfaeller <···@felix.unife.it> writes:
> 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
······@2xtreme.net (Christopher R. Barry) writes:
> Josef Eschgfaeller <···@felix.unife.it> writes:
>
> > 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.
>
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