[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: queue-length should be O(1) ?

This page is part of the web mail archives of SRFI 117 from before July 7th, 2015. The new archives for SRFI 117 contain all messages, not just those from before July 7th, 2015.



Sven Hartrumpf scripsit:

> as queues are much more restricted than lists, it would
> be easy to store (and update) the queue-length in the underlying
> representation of the queue.

You trade off adding a mutation for every element added and removed to the
queue for speeding up queue-length.  I suspect that's not a good trade.
I suspect queue-empty? is far more likely to be used, and that's fast.

-- 
John Cowan          http://www.ccil.org/~cowan        cowan@xxxxxxxx
If I have not seen as far as others, it is because giants were standing
on my shoulders.  --Hal Abelson