Thoughts on laziness (long)

Pierpaolo BERNARDI <>
Thu Oct 19 16:16:19 CEST 2000


On Thu, 19 Oct 2000  wrote:

> * Every attempt I've seen to build a clever, general data structure in
>   Erlang has resulted in something that's slower than either lists or
>   ETS. Two examples:
> 
> ra_list
> 
>    ra_list is one of Okasaki's data structures. It's a data
>    structure with both list-like and array-like behaviour;
>    you get O(log N) access to any element AND O(1) head()/tail()

And O(log N) replace.

> Doing a quick benchmark doesn't give very encouraging results.
> 
>   Sum: take a list of numbers 1..N and sum them (not Gauss' way ;-)
> 
>   Update: change the 3rd, middle and 3rd-last elements in a list
> 
>          -----list------     ------ra-list--   -------ets-----  gb_tree
>    N     sum     update      sum      update   sum    update    update
>    ----------------------------------------------------------------------
>    100   107     197         962      84      1660    50        87
>    1000  921     3666        9903     127       16k   60        89
>    10k   9324    46k         93k      168      168k   74        96
>    100k  493k    660k        1357k    188     2109k   84        97
> 
>    The table shows execution time, i.e. larger numbers are worse.

I too implemented ralists.  If I remember correctly, my implementation
was about 5/6 times slower than built-in lists in a
cons/head/tail-based benchmark.

Source code is appended below.

Worth noting is the fact that uninitialized RALs can be built
which occupy very little space. E.g. ral:create(1000000000000) does work.

PB

================================================================

%%% File    : ral.erl
%%% Author  : Pierpaolo Bernardi <>
%%% Purpose : Implements Random Access Lists.
%%% Created : 14 Dec 1998 by Pierpaolo Bernardi <>


% See Okasaki - Purely Functional Data Structures.

-module(ral).
-author('').

%-compile(export_all).

-export([empty/0,
         cons/2,
         head/1,
         tail/1,
         is_empty/1,
         nth/2,
         update/3,
         ralength/1,
         create/2,
         create/1,
         drop/2,
         rev_append/2,
         rev/1,
         append/2,
         flatten/1,
         to_list/1,
         from_list/1,
         iota/1,
         map/2,
         iter/2,
         for_all/2,
         exists/2,
         mem/2,
         split/1,
         combine/2
        ]).

%% A RAL is represented either as the atom 'the_empty_ral', or a list
%% of the form: [{Size,Tree} ... | the_empty_ral]. Size is the number
%% of nodes contained in the Tree, Tree is either {X} for a leaf node
%% or {X,LeftSubtree,RighSubtree} for nonleaf nodes.


empty() -> the_empty_ral.


% cons(Item,Ral).

cons(X,[{Size1,T1}, {Size2,T2}|Rest]) when Size1 =:= Size2 ->
    [{1+Size1+Size2,{X,T1,T2}}|Rest];
cons(X,[{Size1,T1}, {Size2,T2}|Rest]) when Size1 /= Size2 ->
    [{1,{X}}|[{Size1,T1}, {Size2,T2}|Rest]];
cons(X,Y) ->
    [{1,{X}}|Y].


% head(Ral).

head([{Size,{X}}|Rest]) -> X;
head([{Size,{X,T1,T2}}|Rest]) -> X.


% tail(Ral).

tail([{Size,{X}}|Rest]) -> Rest;
tail([{Size,{X,T1,T2}}|Rest]) ->
    Size1 = Size div 2,
    [{Size1,T1},{Size1,T2}|Rest].


% is_empty(Ral).

is_empty(the_empty_ral) -> true;
is_empty(X) -> false.


tree_nth(Size,{X},0) -> X;
tree_nth(Size,{X,T1,T2},0) -> X;
tree_nth(Size,{X,T1,T2},I) ->
    Size1 = Size div 2,
    if I =< Size1 -> tree_nth(Size1,T1,I-1);
       true -> tree_nth(Size1,T2,I-1-Size1)
    end.


% nth(Ral,Index).

nth([{Size,T}|Rest],I) when I < Size -> tree_nth(Size,T,I);
nth([{Size,T}|Rest],I) -> nth(Rest,I-Size).


tree_update(Size,{X},0,Y) -> {Y};
tree_update(Size,{X,T1,T2},0,Y) -> {Y,T1,T2};
tree_update(Size,{X,T1,T2},I,Y) ->
    Size1 = Size div 2,
    if I =< Size1 -> {X,tree_update(Size1,T1,I-1,Y),T2};
       true -> {X,T1,tree_update(Size1,T2,I-1-Size1,Y)}
    end.


% update(Ral,Index,NewItem).

update([{Size,T}|Rest],I,Y) when I < Size ->
    [{Size,tree_update(Size,T,I,Y)}|Rest];
update([{Size,T}|Rest],I,Y) ->
    [{Size,T}|update(Rest,I-Size,Y)].


% Additional efficient operations not described in paper (Okasaki)

% ralength(Ral).

ralength(the_empty_ral) -> 0;
ralength([{Size,T}|Rest]) -> Size + ralength(Rest).


make(X,N,Size,T,Rest) when Size > N -> Rest;
make(X,N,Size,T,Rest) -> make(X, N, 1+Size+Size, {X,T,T}, [{Size,T}|Rest]).

select(0,X,Xs) -> Xs;
select(M,[{Size,T}|Rest],Xs) when M < Size -> select(M,Rest,Xs);
select(M,[{Size,T}|Rest],Xs) -> select(M-Size,[{Size,T}|Rest],[{Size,T}|Xs]).


% create(Size,Elem).

create(N,X) when integer(N)  ->
    % make a list of all trees up to size n, then select 
    % those trees that form the greedy decomposition 
    select(N,make(X,N,1,{X},the_empty_ral),the_empty_ral).

create(N) -> create(N,not_initialized).


tree_drop(Size,T,0,Rest) -> [{Size,T}|Rest];
tree_drop(Size,{X},1,Rest) -> Rest;
tree_drop(Size,{X,T1,T2},I,Rest) ->
    Size1 = Size div 2,
    if I =< Size1 -> tree_drop(Size1,T1,I-1,[{Size1,T2}|Rest]);
       true -> tree_drop(Size1,T2,I-1-Size1,Rest)
    end.


% drop(Ral,N).

drop(Xs,0) -> Xs;
drop([{Size,T}|Rest],I) ->
    if I < Size ->
            tree_drop(Size,T,I,Rest);
       true ->
            drop(Rest,I-Size)
    end.



% Pierpaolo 

decompo_loop(C,Top) ->
    Next = C+C+1,
    if Next > Top -> {Top-C,[C]};
       true -> {Rest,Sizes} = decompo_loop(Next,Top),
               if Next =:= Rest -> {0,[Next|Sizes]};
                  C > Rest -> {Rest,Sizes};
                  true -> {Rest-C,[C|Sizes]}
               end
    end.

decompo(N) ->
    if N < 0 -> invalid_argument;
       N =:= 0 -> the_empty_ral;
       true -> {Rest,Sizes} = decompo_loop(1,N),
               case Rest of
                   0 -> Sizes;
                   1 -> [1|Sizes]
               end
    end.


tree_rev_append({X},L) -> cons(X,L);
tree_rev_append({X,T1,T2},L) ->
    tree_rev_append(T2, tree_rev_append(T1,cons(X,L))).


% rev_append(Rovescianda,Tail).

rev_append(the_empty_ral,L2) -> L2;
rev_append([{Size,T1}|T2],L2) -> rev_append(T2, tree_rev_append(T1,L2)).


% rev(Ral).

rev(L) -> rev_append(L,the_empty_ral).


tree_append({X},L) -> cons(X,L);
tree_append({X,T1,T2},L) -> cons(X,tree_append(T1, tree_append(T2,L))).

% append(Ral1,Ral2).

append(the_empty_ral,L2) -> L2;
append([{Size,T1}|T2],L2) -> tree_append(T1,append(T2,L2)).

% flatten(RalOfRals).

flatten(the_empty_ral) -> the_empty_ral;
flatten(L) -> append(head(L),flatten(tail(L))).


tree_to_list({X},Acc) -> [X|Acc];
tree_to_list({X,T1,T2},Acc) -> [X|tree_to_list(T1,tree_to_list(T2,Acc))].


tol(the_empty_ral,Acc) -> Acc;
tol([{Size,T1}|T2],Acc) -> tree_to_list(T1,tol(T2,Acc)).

% to_list(Ral).

to_list(L) -> tol(L,[]).


from_list_loop([],Acc) -> Acc;
from_list_loop([X|Xs],Acc) -> from_list_loop(Xs,cons(X,Acc)).

% from_list(List).

from_list(L) -> from_list_loop(lists:reverse(L),the_empty_ral).


tree_iota(Da,1) -> {Da};
tree_iota(Da,Size) ->
    Half = Size div 2,
    {Da, tree_iota(Da+1,Half), tree_iota(Da+Half+1,Half)}.

iota_loop([],Da) -> the_empty_ral;
iota_loop([X|Xs],Da) -> [{X,tree_iota(Da,X)}|iota_loop(Xs,(Da+X))].

% iota(Int).

iota(N) -> iota_loop(decompo(N),0).


tree_map(F,{X}) -> {F(X)};
tree_map(F,{R,T1,T2}) -> {F(R), tree_map(F,T1), tree_map(F,T2)}.

% map(Fun,Ral).

map(F,the_empty_ral) -> the_empty_ral;
map(F,[{Size,T1}|T2]) -> [{Size,tree_map(F,T1)}|map(F,T2)].


tree_iter(F,{X}) -> F(X);
tree_iter(F,{X,T1,T2}) ->
    F(X),
    tree_iter(F,T1),
    tree_iter(F,T2).


% iter(Fun,Ral).

iter(F,the_empty_ral) -> the_empty_ral;
iter(F,[{Size,T1}|T2]) ->
    tree_iter(F,T1),
    iter(F,T2).


tree_for_all(F,{X}) -> F(X);
tree_for_all(F,{X,T1,T2}) ->
    F(X) and tree_for_all(F,T1) and tree_for_all(F,T2).


% for_all(Fun,Ral).

for_all(F,the_empty_ral) -> true;
for_all(F,[{Size,T1}|T2]) -> tree_for_all(F,T1) and for_all(F,T2).


tree_exists(F,{X}) -> F(X);
tree_exists(F,{X,T1,T2}) -> F(X) or tree_exists(F,T2) or tree_exists(F,T2).


% exists(Fun,Ral).

exists(F,the_empty_ral) -> false;
exists(F,[{Size,T1}|T2]) -> tree_exists(F,T1) or exists(F,T2).


tree_mem(X,{I}) when X =:= I -> true;
tree_mem(X,{I}) -> false;
tree_mem(X,{I,T1,T2}) when X =:= I -> true;
tree_mem(X,{I,T1,T2}) -> tree_mem(X,T1) or tree_mem(X,T2).

    
% mem(Item,Ral).

mem(X,the_empty_ral) -> false;
mem(X,[{Size,T1}|T2]) -> tree_mem(X,T1) or mem(X,T2).


tree_split({{X,Y}}) -> {{X},{Y}};
tree_split({{X,Y},T1,T2}) ->
    {T11,T12} = tree_split(T1),
    {T21,T22} = tree_split(T2),
    {{X,T11,T21},{Y,T12,T22}}.


% split(RalOfPairs).

split(the_empty_ral) -> {the_empty_ral,the_empty_ral};
split([{Size,T1}|T2]) ->
    {T11,T12} = tree_split(T1),
    {T21,T22} = split(T2),
    {[{Size,T11}|T21],[{Size,T12}|T22]}.


tree_combine({X1},{X2}) -> {{X1,X2}};
tree_combine({X1,T11,T21},{X2,T12,T22}) ->
    {{X1,X2}, tree_combine(T11,T12), tree_combine(T21,T22)}.


% combine(Ral1,Ral2).

combine(the_empty_ral,the_empty_ral) -> the_empty_ral;
combine([{Size1,T11}|T21],[{Size2,T12}|T22]) when Size1 =:= Size2 ->
    [{Size1,tree_combine(T11,T12)}|combine(T21,T22)].


% end




More information about the erlang-questions mailing list