From: Josef Eschgfaeller
Subject: Re: length
Date: 
Message-ID: <Pine.LNX.4.04.9906201434480.403-100000@arbzi.zuhause.fe>
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

From: Christopher R. Barry
Subject: Re: length
Date: 
Message-ID: <87pv2qu515.fsf@2xtreme.net>
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
From: Marco Antoniotti
Subject: Re: length
Date: 
Message-ID: <lwhfo11lj5.fsf@copernico.parades.rm.cnr.it>
······@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