I experienced a following problem while dealing with some text processing. I have a text and want to get the same text with parts enclosed into {} or [] stripped away. Substituting them with a ' ' would also work. Here is the code I wrote (T is Data.Text): stripBrackets :: T.Text -> T.Text stripBrackets text = snd $ T.mapAccumL f 0 text where f depth c = let depth' = depth + d' c c' | depth > 0 || depth' > 0 = ' ' | otherwise = c in (depth', c') d' '{' = 1 d' '[' = 1 d' '}' = -1 d' ']' = -1 d' _ = 0 The only problem is that it takes about a minute to complete on 3GHz+ processor when text is a 30k chars long. Any ideas how to improve this code? -- Regards, Petr
On Sunday 12 September 2010 21:23:50, Petr Prokhorenkov wrote:
I experienced a following problem while dealing with some text processing.
I have a text and want to get the same text with parts enclosed into {} or [] stripped away. Substituting them with a ' ' would also work.
Here is the code I wrote (T is Data.Text):
stripBrackets :: T.Text -> T.Text stripBrackets text = snd $ T.mapAccumL f 0 text where f depth c = let depth' = depth + d' c c' | depth > 0 || depth' > 0 = ' '
| otherwise = c
in (depth', c')
d' '{' = 1 d' '[' = 1 d' '}' = -1 d' ']' = -1 d' _ = 0
The only problem is that it takes about a minute to complete on 3GHz+ processor when text is a 30k chars long.
Any ideas how to improve this code?
First, is it intentional that stripBrackets "a]b[c]" = "a]b[c]" and not "a]b " ? Also that it doesn't distinguish between the types of brackets, e.g. stripBrackets "{a]" = " " ? Of course, if you know that the text is properly bracketed, that's not important. Concerning the performance, it seems that mapAccumL actually has quadratic complexity instead of linear because it doesn't get fused. Ouch. I think stripBrackets :: T.Text -> T.Text stripBrackets text = T.concat $ go 0 text where go depth inp = case T.breakBy (`elem` "{[]}") inp of (pre,post) -> case T.uncons post of Nothing -> if depth > 0 then [T.pack $ replicate (T.length pre) ' '] else [pre] Just (c,tl) -> let depth' | c `elem` "{[" = depth + 1 | otherwise = depth - 1 in (if depth > 0 then T.pack (replicate (T.length pre) ' ') else pre) : T.pack (if depth > 0 || depth' > 0 then " " else [c]) : go depth' tl has the same semantics as your function. It's not blazingly fast either (using String for that purpose is much faster), but it's orders of magnitude faster than T.mapAccumL. Note that it's easy to remove the parts enclosed in brackets instead of replacing it by ' ' here.
-- Regards, Petr
Cheers, Daniel
On Sun, Sep 12, 2010 at 12:23 PM, Petr Prokhorenkov
I experienced a following problem while dealing with some text processing.
Thanks for the report and the test case. There's nothing wrong with your code - read on for details. You ran into one of the few functions in Data.Text that I copied straight over from the list implementation due to it not being used often. Unfortunately, that implementation constructs a new Text value (using cons) on every iteration through the loop, and as you might expect that's very slow even on tiny inputs, as it has quadratic behaviour. I've rewritten both strict and lazy mapAccumL and mapAccumR to use as much of the stream fusion machinery as possible. (By the way, there's an interesting fact behind why those functions started out life as they did: you can't write mapAccum functions using only stream machinery, due to their types, and the strict code is more work to write if you can't use the stream machinery. In the early days it just wasn't worth writing the more complex variants of them, as I had more pressing performance concerns at the time.) Where the old version of mapAccumL caused your test case to take 5 seconds to process an 11KB file (ouch!), with the rewritten version, your code can process an 81MB file in the same amount of time, without any changes to your code, and that O(n^2) behaviour is gone :-) text 0.8.1.0 is now up on hackage, with the fix included. Enjoy!
I really didn't expect mapAccumL to have quadratic complexity. Thank you a
lot for the fix!
On Mon, Sep 13, 2010 at 5:06 AM, Bryan O'Sullivan
On Sun, Sep 12, 2010 at 12:23 PM, Petr Prokhorenkov < prokhorenkov@gmail.com> wrote:
I experienced a following problem while dealing with some text processing.
Thanks for the report and the test case. There's nothing wrong with your code - read on for details.
You ran into one of the few functions in Data.Text that I copied straight over from the list implementation due to it not being used often. Unfortunately, that implementation constructs a new Text value (using cons) on every iteration through the loop, and as you might expect that's very slow even on tiny inputs, as it has quadratic behaviour.
I've rewritten both strict and lazy mapAccumL and mapAccumR to use as much of the stream fusion machinery as possible. (By the way, there's an interesting fact behind why those functions started out life as they did: you can't write mapAccum functions using only stream machinery, due to their types, and the strict code is more work to write if you can't use the stream machinery. In the early days it just wasn't worth writing the more complex variants of them, as I had more pressing performance concerns at the time.)
Where the old version of mapAccumL caused your test case to take 5 seconds to process an 11KB file (ouch!), with the rewritten version, your code can process an 81MB file in the same amount of time, without any changes to your code, and that O(n^2) behaviour is gone :-)
text 0.8.1.0 is now up on hackage, with the fix included. Enjoy!
participants (4)
-
Bryan O'Sullivan -
Daniel Fischer -
Felipe Lessa -
Petr Prokhorenkov