[erlang-questions] Strings as Lists

[Alpár Jüttner]

> >   Yeah, I could work with
> > reversed strings, but that's a hack to deal with using the wrong data
> > type.
> 
> No, it has to do with the fact that appending on the right is O(n)
> whether one uses lists or arrays.

A minor correction: appending at the end of an array (std::vector<>) is
O(1) operation in C++. The trick is that it allocates a bit more space
that it is actually required. If it gets full, it allocates a two times
bigger block and copies the array into that block. In this way, the
average number of copying of the elements is at most 2. Of course it
requires 1.5 times more memory on the average.

perhaps in a loop.  Right, this is not efficient.  But it is  

> 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.

All of these C++ counterparts requires unmeasurably low time ( < 4ms) on
my laptop:

    std::vector<char> x;
    for (int i = 1; i <= 100000; i++) x.push_back('a');

    std::string x;
    for (int i = 1; i <= 100000; i++) x.push_back('a');

    std::string x;
    for (int i = 1; i <= 100000; i++) x+='a';

    std::string x;
    for (int i = 1; i <= 100000; i++) x+="a";


Regards,
Alpar