[erlang-questions] list:join() for erlang?
Sat Sep 15 07:20:25 CEST 2007
On 14 Sep 2007, at 9:11 pm, Bob Ippolito wrote:
> Sure, it works great for concatenating two lists, but it's not
> necessarily great for O(N^2) lists. Given that most of them will
> probably be short, I absolutely concede that ++ could very well be a
> performance winner in some cases. However, given that lists:reverse is
> special-cased I could imagine that lists:flatten could be also at some
> point and then the performance landscape could change dramatically.
(a) I repeat, you have misunderstood the advice about ++.
In this particular problem, the version using ++ is not only
linear in the size of the input, it is optimal: it does
fewer conses than the flatten version, and every single one
of the conses it builds is a required part of the output.
The thing is that (Xs++Ys)++Zs is inefficient compared with
Xs++(Ys++Zs), and if you read the code I posted attentively,
you will see that each and every instance of ++ is one of the
Xs++(stuff) form, where Xs is one of the inputs. That is the
(b) I've done a few benchmarks, and the turning of reverse/1 into a
BIF doesn't seem to have made much difference. I have tried
comparing my own reverse/1 (using an unrolled reverse/2) and
found it difficult to measure any difference between that and
(c) Except for iolists, where the point is NOT to flatten,
lists of the kind for which flatten makes sense are bad style in
programming language. If anyone speeds up flatten, it will
a sin in the Book of Life that they encouraged folly.
To cut a long story short, ++ is like a carving knife. You have to
take reasonable care using it, but avoiding the carving knife and
tearing the roast you are serving to your friensd apart with your teeth
(like using flatten) would be messy and not likely to impress them
(to put it kindly).
More information about the erlang-questions