[erlang-questions] : : documentation of data structures

[Raimo Niskanen]

On Tue, Dec 11, 2007 at 02:49:31AM -0800, Lev Walkin wrote:
> Raimo Niskanen wrote:
> 
> >>>> Check the implementation. You will reveal that the operations for
> >>>> adding/removing elements from/to
> >>>> the head/tail can have O(1) complexity in some cases but in some cases
> >>>> they will have O(n) complexity.
> >>>>
> > 
> > Adding and removing elements from head or tail is as concluded above
> > that is amortized O(1). queue:len/1 is O(n), queue:reverse/1 is O(1),
> > queue:join(Q1, Q2) should be O(len(Q1)) by reading the code
> > and queue:split/2 should be O(n) by reading the code.
> 
> Actually, it'd be neat if queue:len/1 were O(1), since it is just
> a simple matter of another element in the tuple.

I did not dare to make that change sometime back in R11 or earlier,
because of the backwards compatibility ghost, again.

If I have a new node and an old node communicating by sending
a message containing a queue I can make the new node understand
an old queue (2-tuple), but not make the old node understand
a new queue (3-tuple). This assuming that no other has code
that assumes queues are 2-tuples.

I should have (then, way back) made a change so queues could
be 3-tuples ignoring the 3rd field. Then I now could make
the change to start using it. *sigh*

Then again nodes sending queues is probably far-fetched anyway,
but who am I to know...



> 
> >>> Okasaki shows a way to have a queue with O(1) worst-case complexity.
> >>> However the constant factor is rather large. The queue ADT has O(1)
> >>> amortized complexity. In addition to that, it has a rather small
> >>> constant factor, so it'll be faster overall.
> >>>
> > 
> > The erlang module 'queue' originates from an Okasaki queue implementation
> > that is small, neat, amortized O(1) with low overhead. If he (Okasaki)
> > has shown an O(1) worst-case that must be another creature.
> 
> The current implementation in `queue` is O(1) amortized non-persistent
> and described in Okasaki [1] Chapter 5.2. There's another one, which
> is O(1) amortized persistent (Ibid Chapter 6.3.2, 6.4.2), and yet
> another one, O(1) worst-case persistent (Ibid. Chapter 7.2,
> "Real-Time Queues", also 8.4.2 for real-time deque).
> 
> I was referring to the latter.
> 
> [1] Chris Okasaki. Purely Functional Data Structures.
> 

Ooo, I really should get that book...



> -- 
> Lev Walkin
> vlm@REDACTED
> _______________________________________________
> erlang-questions mailing list
> erlang-questions@REDACTED
> http://www.erlang.org/mailman/listinfo/erlang-questions

-- 

/ Raimo Niskanen, Erlang/OTP, Ericsson AB