[erlang-questions] Strings as Lists
Thu Feb 14 09:37:09 CET 2008
On 14 Feb 2008, at 05:02 , Richard A.O'Keefe wrote:
>> First off, I append to
>> strings a lot more than I prepend to them.
> I take this to mean that you do stuff like
> S0 = ~0~,
> S1 = S0 ++ ~1~,
> Sn = Sn_1 ++ ~n~
> perhaps in a loop. Right, this is not efficient. But it is
> inefficient in programming languages with more conventional
> It is O(n**2). For example,
> x = ""
> for (i = 1; i <= 100000; i++) x = x "a"
> just took 30.5 seconds in awk on my machine, 62.2 seconds in Perl,
> and a massive
> 631 seconds in Java. That was using gcj; I lost patience with the
> Sun SDK and
> killed it. (AWK faster than Java? Yes, it often is.)
Yep, that's a widely known fact, so it's not surprising and it's why
people usually suggest using the equivalent to IOLists in imperative
languages with immutable array-based strings. In the case of Java, a
StringBuilder or StringBuffer (I just did the test on my macbook 2GHz,
timing with `time`, using a StringBuilder for that loop yields 0.314s,
using regular strings... 243s).
More information about the erlang-questions