On Sun, Jun 27, 2021 at 11:58 AM Alessandro Motta <[email protected]> wrote:
> > I also like Jens' code for its pure functional elegance. I'm surprised > that building up a long list of short strings before joining them is so > much faster. After all, isn't the final `string-join` essentially doing > what the original code snipped did? (Clearly not! I will have a look at > the implementation.) > > This is a classic O(n^2) gotcha. Cons is constant work (in terms of the size of its inputs) and string-append is linear in the size of all of its arguments. So if you repeatedly string-append in a loop, you'll get the 1+2+3+4+5+6+7+8+....+n which is O(n^2), but if you collect all the arguments in a list and then call string-append once at the end, it will be linear (which implies than string-append isn't naive when it gets a lot of arguments; it looks at them twice. Once to know how much to allocate before a second pass to filling in the string). hth, Robby -- You received this message because you are subscribed to the Google Groups "Racket Users" group. To unsubscribe from this group and stop receiving emails from it, send an email to [email protected]. To view this discussion on the web visit https://groups.google.com/d/msgid/racket-users/CAL3TdOOkJjkH7Qoayjm%2BVhZ6aK9_vnDOZ_1cvFJ_RSxZJRTDNA%40mail.gmail.com.
