[erlang-questions] Strings as Lists

Masklinn <>
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
> spectacularly
> inefficient in programming languages with more conventional
> representations.
> 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 mailing list