why is your concatenation operator quadratic...
-
-
Replying to @ubsanitizer @RichFelker
oh, wait, right, non-ownership languages exist, sorry >.< assume ownership semantics of `operator+`
1 reply 0 retweets 1 like -
Replying to @ubsanitizer
With a proper language and guaranteed optimization, it need not be quadratic. But with naive implementation/without combining multiple concatenations, it necessarily is.
1 reply 0 retweets 0 likes -
Replying to @RichFelker
I don't believe so? Assuming ownership semantics, `a + b + c` will be equivalent to `a.extend(b); a.extend(b); a`, which is amortized O(N)
1 reply 0 retweets 0 likes -
Replying to @ubsanitizer
Unless you resize the buffer speculatively (possibly wasting lots of memory when not needed) or have lookahead for final needed size, you need a realloc (thus memcpy) for each concatenation.
1 reply 0 retweets 0 likes -
Replying to @RichFelker @ubsanitizer
Ends up being O(nm) for total length n, m concatenations.
1 reply 0 retweets 0 likes -
Replying to @RichFelker
that assumes that we're resizing it each time tho. Let's say we implement it as for (el in other) a.push(el); each push is amortized O(1); this means that n pushes is O(n), so it'll be amortizer O(final_len - initial_len)
2 replies 0 retweets 0 likes -
Replying to @ubsanitizer
Push can't be amortized O(1) if you use an array representation. If you don't, other operations will be slowish, but you can possibly make everything O(log n).
2 replies 0 retweets 0 likes -
Replying to @RichFelker @ubsanitizer
But all this (eg exponential allocation strategy) requires wasting lots of space in typical cases.
1 reply 0 retweets 0 likes -
Yes, and that's why Firefox and Chrome use 10+ GB... ;-)
Loading seems to be taking a while.
Twitter may be over capacity or experiencing a momentary hiccup. Try again or visit Twitter Status for more information.