Re: Make many insertions in long string

Your performance problem comes from string concatenation (s1 ^ s2): because
it is linear in the sum of the sizes, applying it repeatedly gives
quadratic complexity.

In general when you want to concatenate lots of strings, a good solution is
to build a list of strings instead, and concatenate them all at the end
using String.concat. However, this seems to be fairly difficult to do in
your particular problem, because the offsets of the next strings to infer
are given in terms of the post-insertion string (the behaviour of further
insertion depends on past insertions; accumulating stuff in lists is not
enough, as it does not easily allow to reason on the intermediary results).

You should maybe consider adopting one of the more efficient
data-structures designed for efficient concatenations (and subsequence
extraction) of text fragments. One of them is the Rope data structure,
which is implemented in particular in the BatText module of the Batteries
library (
http://ocaml-batteries-team.github.io/batteries-included/hdoc2/BatText.html
). Given the additional bookkeeping of the more advanced data structures,
ropes have larger constant factors so they aren't worth it for small
strings or simple operations, but I think they would be a good fit for your
needs.

On Sun, Nov 29, 2015 at 4:19 PM, [email protected] [ocaml_beginners]
<[email protected]> wrote:

>
>
>  I have a string of  716954 characters, and I need to make
> 10998 insertions of short strings at different places in it.
> My naive try (see below)
> makes my Mac crash (everything stalls and I'm forced to restart
> my computer). Any ideas on how to handle this "massive" computation ?
>
> Perhaps I should take advantage of the fact that I already know
> the length of the final answer string.
>
> let beginning k s=
>    if k<1 then "" else
>    let n=String.length(s) in
>    if (k>n)
>    then failwith("Beginning failure : string too short")
>    else String.sub s 0 k;;
>
>  let ending k s=
>    if k<1 then "" else
>    let n=String.length(s) in
>    if (k>n)
>    then failwith("Ending failure : string too short")
>    else String.sub s (n-k) k;;
>
>  let cobeginning k s=ending (String.length(s)-k) s;;
>
> let insert_at_point s (j,t)=
>      let temp1=beginning j s
>      and temp2=cobeginning j s in
>      temp1^t^temp2;;
>
> let insert_at_points s l=List.fold_left insert_at_point s (List.rev l);;
>
>
>
>
>
>
> 
>