On 9/17/07, Fabrizio Caruso <caruso at dm.unipi.it> wrote:
>
> I have implemented longssubst which does what ssubst does and works on
> strings
> larger than 5 kilobytes.
>
> Unfortanately my code is much slower.
>
> Could someone tell me why?
>
Because you are creating lots of strings as intermediate results.
substring(...) and concat(...) create a new string every time you call them.
What's worse, Maxima currently doesn't garbage collect Maxima strings....
Even when that is fixed, though, this algorithm will be very inefficient.
When there are *no* substitutions made, you are still copying every
character O(n^2) times: longssubst("a","b","xxxx") calls concat 4 times
with results x, xx, xxx, xxxx; and also calls substring 8 times.
For efficient string manipulations, you should use a more efficient
algorithm and probably write it in Lisp.
By the way, the code is buggy: longssubst("ab","cd","cd") => "abd".
-s