[erlang-questions] Coming Back (maybe improving lists:reverse/1)

Ivan Carmenates Garcia co7eb@REDACTED
Thu Oct 8 15:24:48 CEST 2015


Yes I mean the C implementation, because if you do 1 millon of repetances of
lists:length/1 in Erlang and the same for lists:reverse/1 for the same list,
lists:length takes 16 milliseconds in my pc and lists:reverse takes 64
milliseconds.

> So when using lists:reverse/1 it takes four times what lengths does,

Four times *what*?  lists:reverse/1 may well be implemented in C by now, but
in Erlang we can write

    length(L) -> length_plus(L, 0).

    length_plus([_|Xs], N) -> length_plus(Xs, 1+N);
    length_plus([],     N) -> N.

    reverse(L) -> reverse_append(L, []).

    reverse_append([X|Xs], Ys) -> reverse_append(Xs, [X|Ys]);
    reverse_append([],     Ys) -> Ys.

This is a *single* traversal.  The two algorithms are essentially the same.
Such extra cost as there is in reverse/1 compared with
length/1 has to do with allocating and initialising memory; using doubly
linked lists would only increase that cost.

> so I can play guess, and just that, that you are using indeed a double
linked list so you spend one O(n) to transverse the list, three O(1), which
is an O(1) in total of course I am just counting the operations as well, to
swap the preview and next pointers for each node so the list will be in the
reverse order and other O(1) to return the new list which is a pointer of
course to the old list just reversed.

There is no changing of pointers in Erlang lists.  There is no possibility
of in-place updates of lists.  If I do

    L = [1,2,3],
    R = lists:reverse(L)

then I expect L to be completely unaltered.  No Erlang operation is
permitted to (visibly) alter any reachable value in any (detectable) way.=




More information about the erlang-questions mailing list