[clisp-list] Re: Lisp question

[Pascal J.B. <pj...@in...>]

John K. Hinsdale writes:
> 
>   >> I wrote a replacement for EXT:STRING-CONCAT that speeds things up a
>   >> lot for my appl.  It works by working with a growable string array
>   >> and pre-allocating space as it gets bigger.
> 
>  > the return value is not a simple string.
> 
> not sure why this matters to me?  My application works the same either way...
> 
>  > (defun concat-strings (strings)
>  > ...
>  > this is pretty much the same as (apply #'string-concat strings).
> 
> This is at least 100 times faster than my function (!) Can you give me a
> hint as to why?  And thanks!


For: (dotimes (i 2000) (push "xxxxxxxxxx" l))
you'll end up with a string of 20000 characters.

Your function  will have  to allocate (ceiling  (/ (log  (/ total-size
100)) (log 2))) [= 8 for 20000 characters] strings of increasing sizes
[O(log(n)], with copying the intermediary concatenations [O(n*log(n))]
while the other function will  allocate one string [O(1)] and copy the
bytes once [O(n)].  [Note that for strings, (length s) is O(1)].


-- 
__Pascal_Bourguignon__                              .  *   * . * .* .
http://www.informatimago.com/                        .   *   .   .*
There is no worse tyranny than to force             * .  . /\  (   . *
a man to pay for what he does not                    . .  / .\   . * .
want merely because you think it                    .*.  / *  \  . .
would be good for him. -- Robert Heinlein             . /*   o \     .
http://www.theadvocates.org/                        *   '''||'''   .
SCO Spam-magnet: pos...@sc...                 ******************