search

mathiasbynens / esrever

A Unicode-aware string reverser written in JavaScript.
https://git.io/esrever
MIT License
891 stars 30 forks source link

Build up result in array instead of strings #12

Closed masak closed 6 years ago

masak commented 7 years ago

Incrementally concatenating strings means a lot of intermediate strings get allocated only to be thrown away. The result is O(n**2) in both space and time.

See this post about Shlemiel the painter's algorithm for a good description about the quadratic behavior involved.

https://www.joelonsoftware.com/2001/12/11/back-to-basics/

Storing each fragment in an array and joining them all together in the end at least avoids allocating ever-longer intermediate strings. I have not run any benchmarks on very long strings, though. That might still be interesting to do.

coveralls commented 7 years ago

Coverage Status

Coverage remained the same at 80.769% when pulling 09f9b0ea0268ec805c94f36106b38222c957d114 on masak:master into 48e1f4587169d54a57f4bb4693d8ee1ea5b012f5 on mathiasbynens:master.

coveralls commented 7 years ago

Coverage Status

Coverage remained the same at 80.769% when pulling 09f9b0ea0268ec805c94f36106b38222c957d114 on masak:master into 48e1f4587169d54a57f4bb4693d8ee1ea5b012f5 on mathiasbynens:master.

coveralls commented 7 years ago

Coverage Status

Coverage remained the same at 80.769% when pulling 09f9b0ea0268ec805c94f36106b38222c957d114 on masak:master into 48e1f4587169d54a57f4bb4693d8ee1ea5b012f5 on mathiasbynens:master.