[erlang-questions] Performance of the append/reverse idiom

[ok]

On 17 Jul 2007, at 7:18 am, Christopher Baus wrote:
> Thanks for your reply.  I agree with you, but I can see why developers
> would pause when adding an additional O(n) operation to the end of  
> a list
> accumulate operation when this could be handled at insertion time in a
> doubly linked list -- especially in CPU bound applications.

I am having a little trouble understanding this.
People are not willing to pay O(n) extra time to reverse a list,
but *ARE* willing to pay O(n) extra time to maintain those
Cthulhu-inspired backwards pointers?  That doesn't make sense to me.

> I think a reasonable solution for most apps would be to manipulate the
> data in reversed order, unless reversing is required by an I/O  
> operation.

You reverse when you need to reverse, obviously.  It isn't always I/O
operations that force a particular order.

One solution is simply to use body recursion instead of tail recursion
(which of course adds an O(n) overhead) or to use list comprehension
(which is currently implemented using body recursion, so has an O(n)
overhead).

Really, the best thing to do is to write the clearest code you can so
that you get it right and THEN PROFILE IT.  In all programming  
languages,
people usually start off worrying about the wrong things entirely when
it comes to performance.