How quickly can you remove spaces from a string?

Re:How quickly can you remove spaces from a string? by throwanem on Friday January 20, 2017 @03:47PM (#13446853)

Simple regexes can be reasonably quick, but you're almost certainly never going to do better than linear time, and if you get fancy, it's easy to go exponential with a large exponent.

[ Parent | on HN ]

Re:How quickly can you remove spaces from a string? by pjscott on Friday January 20, 2017 @10:57PM (#13448660)

If you want to guarantee that this will never happen, RE2 and similar regular expression engines are guaranteed to run in O(n) time, where n is the length of the target string.

https://swtch.com/~rsc/regexp/

I've had nothing but good experiences with it. (Rust's looks similar, by the way, and quite impressive.)

[ Parent | on HN ]

Re:How quickly can you remove spaces from a string? by burntsushi on Saturday January 21, 2017 @12:58AM (#13449055)

Indeed. Rust's regex engine is descended from RE2. rsc's blog posts were my guide when I first wrote it.

[ Parent | on HN ]