[erlang-questions] Behaviour of queue
Joe Armstrong
erlang@REDACTED
Fri Sep 10 11:41:19 CEST 2010
Queue as robert said, are really easy. The simplest possible queue is
just a pair of lists {In, Out}. As new elements are added they are
appended to In
So we can write:
new_queue() -> {[], []}.
add(X, {In,Out}) -> {[X|In}, Out}.
What about extracting elements from the queue - these come from Out, so ...
remove({In, [X|Out]} -> {X, {In, Out}};
...
But hang on, what happens in Out is empty - well if In is also empty
we have nothing to
remove so:
remove({[], []}) -> empty;
Otherwise In is non empty and Out is empty so we revers In and move it
to Out and try again
remove({In, []}) -> remove({[], reverse(In)}).
The nice thing about this is that amortized cost of using the queue is constant.
We create a single cons cell when adding to the In list, and a single
cons cell when
moving an element from the In to Out list - each element is only
touched once as it
moves from input to output.
This is by far the best method for short queue non persistent queues.
This pattern - a pair of two lists, one reversed one in normal order
is used over and
over again in many guises - it's the "natural" representation for a text editor.
Files are queues of lines. The current line being edited is a queue of
characters, etc.
Well worth remembering the pattern ...
/Joe
On Fri, Sep 10, 2010 at 11:13 AM, Chandru
<chandrashekhar.mullaparthi@REDACTED> wrote:
> On 9 September 2010 14:03, Fredrik Andersson <sedrik@REDACTED> wrote:
>
>> Hi all
>>
>> I have a question concerning the behaviour of the erlang queue module.
>> Does it store everything in memory or will it fallback to storing
>> things on disk if memory is running short? If it does not I need to
>> implement a layer on top of queue that will fallback to store things
>> on disk if needed.
>>
>>
> You can simulate a queue using an ordered_set mnesia table with the value of
> now() as the primary key. That might save you writing an extra layer on top.
>
> cheers
> Chandru
>
More information about the erlang-questions
mailing list