[erlang-questions] Strings as Lists
Fri Feb 15 20:20:14 CET 2008
On Feb 14, 2008, at 7:06 PM, Richard A. O'Keefe wrote:
> I wrote:
>>> No, it has to do with the fact that appending on the right is O(n)
>>> whether one uses lists or arrays.
> Since this is the *Erlang* mailing list, this should have been read as
> "whether one uses (immutable) lists or (immutable) arrays".
> On 14 Feb 2008, at 8:37 pm, Alpár Jüttner wrote:
>> A minor correction: appending at the end of an array
>> (std::vector<>) is
>> O(1) operation in C++.
> std::vector<> is not a class of immutable arrays.
> Suppose we have two byte-strings of length n and m.
> If they are immutable, the concatenation cost is O(n+m).
> If you are willing to smash the one on the left, and it is "stretchy",
> the cost is STILL not O(1), it is O(m).
Pardon my ignorance, but how it is that concatenating to the end of a
length n immutable list is not O(n)? Isn't it necessary to copy all
the list elements?
(It's also worth noting that while strictly speaking the append on a
mutable array is O(m), in practice the coefficient is very small since
it's implemented as a single memcpy.)
More information about the erlang-questions