Thoughts on laziness (long)
Pierpaolo BERNARDI
bernardp@REDACTED
Thu Oct 19 16:16:19 CEST 2000
On Thu, 19 Oct 2000 matthias@REDACTED 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 <bernardp@REDACTED>
%%% Purpose : Implements Random Access Lists.
%%% Created : 14 Dec 1998 by Pierpaolo Bernardi <bernardp@REDACTED>
% See Okasaki - Purely Functional Data Structures.
-module(ral).
-author('bernardp@REDACTED').
%-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