[erlang-questions] Memory-effective queue handling

[Richard O'Keefe]

You have a collection of {Time_Stamp, Data} items covering the
last 24 hours.  You want to add such pairs, and you also want
to remove old pairs of this kind.

Some kind of balanced search tree such as an AVL
tree or 2-3 tree can do this in O(lg n) time per
updated, where n is the number of pairs in your
collection.

A very simple hack would be to divide a sequence into
some number of buckets where the first and last are
special, so we have
	{Old,Middling,New}
New is a list running from newest to oldest within
the current bucket.  To add a new event:

add_event(When, What, {Old,Middling,New}) ->
    {Old,Middling,[{When,What}|New]}.

Old is a list running from oldest to newest within
the oldest bucket.

To remove old events:

remove_old_events(Now, {Old,Middling,New}) ->
    Bound = <| however you calculate Now - 24 hours |>,
    {remove_expired(Bound, Old),Middling,New}.

remove_expired(Bound, [{When,What}|Old])
  when When =< Bound ->
    remove_expired(Bound, Old);
remove_expired(_, Old) ->
    Old.

One extra step is to shift the buckets when the hour
strikes:

hourly_shift({_,{A,B,C,D,E,F,G,H,I,J,K,L,M,N,
                   O,P,Q,R,S,T,U,V,W,X},New}) ->
    {A,{B,C,D,E,F,G,H,I,J,K,L,M,N,
        O,P,Q,R,S,T,U,V,W,X,lists:reverse(New)},[]}.

To walk over the elements in increasing order:

foldl(Fun, Acc, {Old,{A,B,C,D,E,F,G,I,J,K,L,M,N,
                      O,P,Q,R,S,T,U,V,W,X},New}) ->
    Acc_0 = foldl(Fun, Acc, Old),
    Acc_1 = foldl(Fun, Acc_1, A),
    ...
    Acc24 = foldl(Fun, Acc23, X),
    foldl(Fun, Acc24, lists:reverse(New)).

Whether this is a good idea depends on what else you want
to do.  It also matters how many events you expect to be
in the data structure.

Oh yes, to keep track of how many events there are,
use
	{Count,Old,Middling,New}
with the other changes to the code being obvious.