6
$\begingroup$

So, say I have a list of strings, representing lines in a file, like so:

Pillsy`testLines =
 {"foo",
  "bar\\",
  "baz\\",
  "quux",
  "wongle\\ bongle",
  "wingle",
  "pringle\\",
  "prongle",
  "blort"};

These use the (common?) convention that if a line ends with a backslash, it should be appended to the following line, giving a result like this:

Pillsy`testResult =
  {"foo", "barbazquux", "wongle\\ bongle", "wingle", "pringleprongle", "blort"};

Now, the naïve way to accomplish this is to use pattern matching, but the performance is likely to be really awful if you've got a lot of lines:

Pillsy`naiveCatenateContinuedLines[lines : {___String}] :=
 lines //.
  {before___, line1_, line2_, after___} /;
    StringMatchQ[line1, ___ ~~ "\\" ~~ EndOfString] :>
   {before, StringDrop[line1, -1] <> line2, after};

You've got two potential performance hits, one with repeated breaking of the list into BlankNullSequences, and the other with repeated StringJoins (I'm actually not 100% sure that the last is avoidable, but it's certainly possible that StringJoining many strings at once is efficient, and that would explain why StringJoin has the Flat attribute).

I ended up doing what any functional programmer does when confronted with a problem they don't know how to solve: I used Fold to accumulate a linked list. This solution works, and seems like it could be efficient (in part by exploiting the Flatness of StringJoin), but I haven't done actual performance testing. EDIT: Now I have a file to test with (linked below), and this solution runs in about 4 milliseconds. The naive solution takes about 25 milliseconds, and scales quadratically with length.

Pillsy`catenateContinuedLines[lines : {___String}] :=
 Module[{catenating},
  Attributes[catenating] = {HoldAllComplete};

  Flatten@Fold[
    Function[{acc, line},
     With[{
       (* This allows me to avoid repeating myself, but is a bit nuts. *)
       thunk =
        If[
         0 < StringLength@line && StringTake[line, -1] == "\\",
         With[{dropped = StringDrop[line, -1]},
          catenating@StringJoin[#, dropped] &],
         StringJoin[#, line] &]
       },
      acc /. {
        {init_, catenating[arg_]} :> {init, thunk[Unevaluated@arg]},
        _ -> {acc, thunk[""]}
        }]],
    {},
    lines]]

I checked briefly to see if there was an option for Import[file, {"Text", "Lines"}] that would allow you to specify a line continuation character, but nothing jumped out at me. I have a solution, but it seems needlessly convoluted.

EDIT to add: I have a semi-realistic test file that's long enough that I can do some timing, but unfortunately can't make it public.

EDIT again to add: OK, I munged any identifying information in the file beyond all recognition, so if you want something for test timings, you can find it here.

$\endgroup$

5 Answers 5

5
$\begingroup$

new one

This seems to be quite fast (didn't test with yours)

sc[{n_String}] := n;
sc[s_] := StringJoin[StringDrop[Most[s], -1]] <> Last[s]

sc /@ Split[testLines, StringMatchQ[#, "*\\"] &]

old one

StringJoin @@@ (
  Split[testLines, StringMatchQ[#, "*\\"] &] /. s : {Repeated[_String, {2, ∞}]} :> 
                                                     StringReplace[s, "\\" -> ""])
{"foo", "barbazquux", "wongle\\ bongle", "wingle", "pringleprongle", "blort"}

Notice that this is Split not SplitBy. Important difference because from adjacent elements we only test former one.

$\endgroup$
8
  • $\begingroup$ That is considerably faster than my Sow/Reap solution (I have a test file I'm working on that I unfortunately can't make public); I like the trick of using a one-argument predicate with Split. $\endgroup$
    – Pillsy
    Mar 25, 2014 at 19:21
  • 1
    $\begingroup$ @Pillsy I have to thank you, this will help me with the task I was thinking about today :P $\endgroup$
    – Kuba
    Mar 25, 2014 at 19:29
  • $\begingroup$ Using the munged test file above, your solution runs in about 0.5 milliseconds vs 1.5 milliseconds for my best attempt, Sow/Reap. $\endgroup$
    – Pillsy
    Mar 25, 2014 at 19:36
  • 1
    $\begingroup$ @Kuba: New one appears to get wrong result, e.g. I get "babaquux" instead of "barbazquux:... $\endgroup$
    – ciao
    Mar 25, 2014 at 22:08
  • $\begingroup$ @rasher o my, good catch. fixed. $\endgroup$
    – Kuba
    Mar 25, 2014 at 22:10
5
$\begingroup$

This solution requires that you know some character that does not occur in your string, in this example "|"

jacob[strList_] :=
 StringSplit[
  StringReplace[StringJoin[Riffle[strList, "|"]], "\\|" -> ""], "|"]

Maybe it will be fast because there are few function calls.

Modified definitions of other answers

sc[{n_String}] := n;
sc[s_] := StringJoin[StringDrop[Most[s], -1]] <> Last[s]

kuba[strList_] :=
 sc /@ Split[strList, StringMatchQ[#, "*\\"] &]

kubaOld[strList_] :=
 StringJoin @@@ (Split[strList, StringMatchQ[#, "*\\"] &] /. 
    s : {Repeated[_String, {2, \[Infinity]}]} :> 
     StringReplace[s, "\\" -> ""])

(*the solution by aky took more than 10 seconds*)
(*the solution in Pillsy's answer also took more than 10 seconds *)

Timing comparison

(jacobRes = jacob[words]) // Timing // First
(kubaRes = kuba[words]) // Timing // First
(kubaOldRes = kubaOld[words]) // Timing // First
(rmrfRes = joinWords[words]) // Timing // First
jacobRes === kubaRes === kubaOldRes == rmrfRes

gives

0.449849
1.694213
2.215579
4.350092
True

$\endgroup$
7
  • $\begingroup$ you can use "LONGMARKER", highly unlikely to interfere :P $\endgroup$
    – Kuba
    Mar 25, 2014 at 22:34
  • $\begingroup$ @Kuba haha yeah. I didn't realise the second argument of StringSpit could be a pattern as well. But yeah that would be slow :P $\endgroup$ Mar 25, 2014 at 22:36
  • $\begingroup$ @Kuba thank you :). Yeah your old answer seems similar, I see you used a short version of "LONGMARKER" ;) $\endgroup$ Mar 25, 2014 at 22:54
  • $\begingroup$ :p also, Riffle is my favorite function, I hate that you've used it with success not me ;P $\endgroup$
    – Kuba
    Mar 25, 2014 at 22:57
  • $\begingroup$ @Kuba ahh, yes gotta love Riffle :D! I used to love it because it felt nice to do Partition[Riffle[list1, list2],2] (or something?), but I think it couldn't compete with Transpose/Thread. $\endgroup$ Mar 25, 2014 at 23:00
3
$\begingroup$

This is similar to Kuba's solution, but uses the listability of ToCharacterCode/FromCharacterCode instead of string patterns. Sometimes, this can be a bit faster than string manipulations:

joinWords[list_] := Join @@@ (Split[ToCharacterCode@list, Last[#] == 92 &] /. 
    {h__, 92} :> {h}) // FromCharacterCode

joinWords@Pillsy`testLines   
(* {"foo", "barbazquux", "wongle\\ bongle", "wingle", "pringleprongle", "blort"} *)
$\endgroup$
1
  • $\begingroup$ This one is considerably slower than Kuba's solution; 2.5 ms vs 0.5 ms. $\endgroup$
    – Pillsy
    Mar 25, 2014 at 20:31
1
$\begingroup$

One alternative solution, that seems faster, but isn't really that much less horrible, uses Sow/Reap and increments a counter to use as a tag:

Pillsy`reapCatenateContinuedLines[lines : {___String}] :=
 Module[{counter = 0},
  StringJoin @@@ Last@Reap[
     Scan[
      If[StringMatchQ[#, ___ ~~ "\\"],
        Sow[StringDrop[#, -1], counter],
        Sow[#, counter++]] &,
      lines]]];
$\endgroup$
1
$\begingroup$

Haven't really evaluated this in terms of speed, but throwing it into the mix anyway:

f[] := Sequence[]
f[first_String, rest___String] := 
 If[StringTake[first, -1] == "\\", 
  f[StringDrop[first, -1] <> First@{rest}, 
   Sequence @@ Rest@{rest}], {first, f[rest]}]

Flatten[f @@ Pillsy`testLines]
(* {"foo", "barbazquux", "wongle\\ bongle", "wingle", "pringleprongle", "blort"} *)
$\endgroup$
2
  • $\begingroup$ This is going to have performance problems similar to the ones with ``PillsynaiveCatenateContinuedLines; when I tried it with twice as many lines of input, it took about 4 times as long. The common functional programming idiom of recursively breaking a list into a head and a tail doesn't really work with Mathematica's pattern matching. $\endgroup$
    – Pillsy
    Mar 25, 2014 at 20:39
  • $\begingroup$ I would've expected that - because of the (head: tail) pattern match - this would be faster, at least compared to matching in the middle of a list, as you do in your naiveCatenateContinuedLines. I tried my function on a list 10 times the size of your test lines (basically generated by doing Flatten[ConstantArray[PillsytestLines, 10]]` ) and Timing showed that it was 10 times slower compared to the original. A 100 times larger list came out to be 200-300 times slower compared to the original. (But yeah, doesn't hold a candle to Kuba's solution.) $\endgroup$
    – Aky
    Mar 25, 2014 at 21:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.