On Friday, May 01, 2015 03:19:03 AM Scott Jones wrote: > As the string grows, Julia's internals end up having to reallocate the > memory and sometimes copy it to a new location, hence the O(n^2) nature of > the code.
Small correction: push! is not O(n^2), it's O(nlogn). Internally, the storage array grows by factors of 2 [1]; after one allocation of size 2n you can add n more elements without reallocating. That said, O(nlogn) can be pretty easily beat by O(2n): make one pass through and count how many you'll need, allocate the whole thing, and then stuff in elements. As you seem to be planning to do. --Tim [1] Last I looked, that is; there was some discussion about switching it to something like 1.5 because of various discussions of memory fragmentation and reuse.
