[erlang-questions] Strings as Lists
Mon Feb 18 06:27:42 CET 2008
On 16 Feb 2008, at 8:20 am, Kevin Scaldeferri wrote:
> 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.
> 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?
As you can see from the quoted text above, that's EXACTLY what I said.
> (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.)
memcpy() isn't that fast.
By using suitable (immutable) trees, you can get concatenation down
while still keeping random access to O(lg n). The way Erlang (ab)
as "iolists" you can get concatenation in O(1) followed by O(n)
so it's easy for an Erlang program to build a string cheaply in
to right or right to left order using lists, but wouldn't be using
More information about the erlang-questions