push_element/2 - efficient sliding window

[Ulf Wiger]

Den 2005-08-12 04:44:34 skrev Richard A. O'Keefe <ok@REDACTED>:

> Suppose you want to maintain a sliding window of 20 elements,
> with new elements coming in from the left.
>
> initial_window(X) ->
>     {X,X,X,X,X,X,X,X,X,X,X,X,X,X,X,X,X,X,X,X}.
>
> add_to_window(X, {A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P,Q,R,S,T}) ->
>     {X,A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P,Q,R,S}.
>
> Do we really need built-in support for this?

It's about as justified as erlang:make_tuple/2
and erlang:append_element/2. Those two can be
implemented in exactly the same manner as you
describe, but only if it is practical to hard-
code the size of the tuple. If that isn't true,
then there is no generic way to do it in Erlang
that doesn't add significant overhead.

The cheapest way I've found so far to do a "left shift"
of a tuple is:

add_to_window(X, {List, _Tup}) ->
    List1 = tl(List) ++ [X],
    {List1, list_to_tuple(List1)}.

This is about three times as expensive as the BIF,
and also requires you to lug the window along as
a list, along with the tuple representation. Not
that this adds tremendous memory overhead. Doing
away with the list, you can do:

add_to_window(X, Tup) ->
    L = tuple_to_list(Tup),
    L1 = tl(L) ++ [X],
    list_to_tuple(L1).

This adds an element to the end of the tuple. Adding it
to the beginning without knowing the size of the tuple
is more expensive. Why? Because we have built-in support
for append and tuple_to_list/list_to_tuple (all of these
can easily be implemented in Erlang). That's what makes
the program above reasonably fast.

rshift_tuple(X, Tup) ->
    L = tuple_to_list(Tup),
    [_|R] = lists:reverse(R),
    list_to_tuple([X|lists:reverse(R)]).

Since a shift BIF would cost about the same as
tuple_to_list/1, lists:reverse/1, list_to_tuple/1
and append/2 above (they are all BIFs), the efficiency
gain of adding the BIF would be about 4x in the
generic case.

Actually erlang:make_tuple/2 was my suggestion. This
was after having written my own make_tuple/2 in Erlang
a number of times, roughly in the manner you suggest:

make_tuple(10, X) ->
    {X, X, X, X, X, X, X, X, X, X};
make_tuple(20, X) ->
    {X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X};
make_tuple(N, X) when is_integer(N) ->
    list_to_tuple(lists:duplicate(N, X)).

I see no reason why we should grace the list type with
optimized versions of append, subtract, keymember, member,
keysearch and reverse, but not offer similar optimizations
for tuples. I think tuples could be used to great advantage
in many cases where we use ETS today, if only a few steps
were taken to ease their use a little bit.

Another thing I'd like to see for tuples is a syntax
addition:

tag_search([{Tag | _} = T|_], Tag) ->
    {value, T};
...


That is, describing the "tail" of a tuple in a manner
similar to that of lists. This form is actually used
in some places in the documentation! Most likely because
it's very convenient. It could also be used to improve
backwards compatibility, since new elements in a tuple
are usually added last to preserve order.

I have not given much thought to the implementation
issues of this last item. Perhaps it's difficult...?

/Uffe
-- 
Ulf Wiger