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

[Ivan Carmenates Garcia]

I fellows, I was down for a while, connection payment problems, lol. So I am
back, and I have a few ideas I would like to share. Also my cowboy extension
framework is marching very nice, I had dedicate some time to it in this
offline days.

 

My thoughts, when I was doing some algorithms for the framework, I found
some questions I would like to share because for example, when working with
lists module, and doing some recursive functions, it is usually a problem
that we need to do lists:reverse at the end of the algorism to get the data
in the right order.

 

So I can imagine Erlang implement lists using double linked lists for
obvious purposes, I haven't see the source code so I am just guessing here,
so for example when doing length you must spend one O(N) to transverse the
list, one O(1) for each element to count them and one final O(1) to return
the list. So when using lists:reverse/1 it takes four times what lengths
does, 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.

 

So guessing that it is what you do, how bad could be instead of doing that
just make list have one bit more of size in memory by saying the order it
have. So when you use lists:reverse/1 is just changing that bit to true and
when iterating the list instead of using the next function use preview
function and viseversa. The problem will be that you must spend one more
O(1) for each element when iterating to choose what function is executed
depending on the reverse bit. I just did a little simple erlang example to
prove my point, of course it is just for demonstration purposes not for real
implementation.   

 

-module(mylists).

 

-compile(export_all).

 

-type mylists_ref() :: erlang:ref().

 

-spec new(list()) -> mylists_ref().

new(List)->

    Ref = erlang:make_ref(),

    erlang:put({Ref, first}, erlang:hd(List)),

    store_list(List, Ref),

    Ref.

 

store_list([A], Ref) ->

    erlang:put({Ref, final}, A);

store_list([A,B | _] = [_ | Rest], Ref) ->

    erlang:put({Ref, A, next}, B),

    erlang:put({Ref, B, preview}, A),

    store_list(Rest, Ref).

       

-spec next(mylists_ref()) -> Element :: any().

next(MyListRef) ->

    case erlang:get({MyListRef, cursor}) of

        undefined ->

            Element =

                case erlang:get({MyListRef, reversed}) of

                    true ->

                        erlang:get({MyListRef, final});

                    undefined ->

                        erlang:get({MyListRef, first})

                end,

                erlang:put({MyListRef, cursor}, Element),

                Element;

        Element ->

            NewElement =

                case erlang:get({MyListRef, reversed}) of

                    true ->

                        erlang:get({MyListRef, Element, preview});

                    undefined ->

                        erlang:get({MyListRef, Element, next})

                end,

                case NewElement of

                    undefined ->

                        undefined;

                    Next ->

                        erlang:put({MyListRef, cursor}, Next),

                        Next

                end

        end.

 

reset(MyListRef) ->

    erlang:erase({MyListRef, cursor}).

 

 

-spec reverse(mylists_ref()) -> MyReverseListRef :: mylists_ref().

reverse(MyListRef) -> 

    reset(MyListRef),

    case erlang:get({MyListRef, reversed}) of

        undefined ->

            erlang:put({MyListRef, reversed}, true);

        true ->

            erlang:erase({MyListRef, reversed})

    end,

    ok.

 

test() ->

    MyListRef = mylists:new([1,2,3,4]),

    FirstElem = mylists:next(MyListRef),

    mylists:reverse(MyListRef),

    LastElem = mylists:next(MyListRef),

    {FirstElem, LastElem}.

 

Cheers,

Ivan (son of Gilberio).

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://erlang.org/pipermail/erlang-questions/attachments/20151007/06ffe181/attachment.htm>