Double-Ended Queue on Slice/Array

[Peter Fröhlich]

Hi all,

I needed this for a small project and I am cleaning it up for general
use now. Maybe someone else did one of these before but I couldn't
find another implementation (of just a data structure that is, not
some queue-shaped concurrency-thingy). Comments/issues welcome.

https://github.com/phf/go-queue

Cheers,
Peter
--
Peter H. Froehlich <http://www.cs.jhu.edu/~phf/>
Senior Lecturer | Director, Johns Hopkins Gaming Lab

The views stated in this communication are my own and do not express
the position or views of The Johns Hopkins University.

[Peter Fröhlich]

Just FYI, there have been a few more fixes since the first post and
the import path does now follow the Go conventions. Documentation is
here: http://godoc.org/github.com/phf/go-queue/queue

[Kevin Gillette]

Regarding the editorial: there's a very strong motivation from univalued map accesses returning the zero value for a missing key, and it's not a convention; it's part of the basic definition of maps in Go, along with nil maps acting like empty maps for any operations that wouldn't affect the content (such as allowing deletes, reads, and iteration on nil maps).

Regarding the actual implementation, I feel this is yet another area that can strongly benefit from a deep understanding of the zen of sort.Interface. Any non-interface slice can be used as a double-ended queue: precisely zero percent of the difficulty lies in storing elements, thus zero percent of a deque library should be concerned with storing elements itself. While it's possible for you to go the extra distance and use reflect to provide a concrete-typed veneer and prove that no type-mismatch panics occur, it's something that the compiler can't verify, and is less efficient by a large constant factor (often involving a dereference per access), and thus is comparatively undesirable.

At some point I'll explore this topic to see how feasible a simple API would be to use if only operated in terms of integer indices.

I do agree that it's reasonable for panics to occur, even when the out-of-bounds condition is simulated. Essentially, if the _programmer_ did something wrong that can't be caught at compile time, it usually deserves a panic; if the "user" did something wrong, it deserves an error value.

[Peter Fröhlich]

On Fri, Nov 1, 2013 at 7:54 PM, Kevin Gillette
<extempor...@gmail.com> wrote:
> Regarding the actual implementation, I feel this is yet another area that
> can strongly benefit from a deep understanding of the zen of sort.Interface.
> Any non-interface slice can be used as a double-ended queue: precisely zero
> percent of the difficulty lies in storing elements, thus zero percent of a
> deque library should be concerned with storing elements itself. While it's
> possible for you to go the extra distance and use reflect to provide a
> concrete-typed veneer and prove that no type-mismatch panics occur, it's
> something that the compiler can't verify, and is less efficient by a large
> constant factor (often involving a dereference per access), and thus is
> comparatively undesirable.

I didn't know that sort.Interface was considered "Zen" now. There are
at least two ways of approaching all of these things: Either write the
specialized container and keep the elements general, or have someone
else write a more general container with specific elements and offer
certain specialized behavior (like sorting or heaps) on top of that.
The former leads to requirements on the elements (up to and including
zero requirements as is the case here) while the latter leads to a lot
of duplicated code (see the very sort module you reference with its
duplicated implementations of slices for basic types). I guess where
you see "Zen" I see a design tradeoff to be made in the least
convoluted way, and copying sort.Interface and friends for queues
doesn't seem worth it. Of course if you actually do it, please be sure
to let us know the outcome in terms of performance. I for my part am
happy to have at least beaten container/list.

[Kevin Gillette]

On Saturday, November 2, 2013 9:43:18 AM UTC-6, Peter Froehlich wrote:

I didn't know that sort.Interface was considered "Zen" now.

In combination with sort.Sort, it provides a well-tested generic algorithm implementation while still maintaining full type safety; pretty much anything that can fit into the sentence "you _could_ do X with generics support, but this way doesn't need it and is better anyway" is pretty well "zen."

 

There are at least two ways of approaching all of these things: Either write the
specialized container and keep the elements general, or have someone
else write a more general container with specific elements and offer
certain specialized behavior (like sorting or heaps) on top of that.
The former leads to requirements on the elements (up to and including
zero requirements as is the case here) while the latter leads to a lot
of duplicated code (see the very sort module you reference with its
duplicated implementations of slices for basic types).

I fully agree. Though there are "runtime overhead requirements" that are additionally imposed, and "safety requirements" that are difficult to satisfy with the latter. With the former, all the requirements are placed on the application programmer, for better or worse.

 

I guess where you see "Zen" I see a design tradeoff to be made in the least
convoluted way, and copying sort.Interface and friends for queues
doesn't seem worth it.

To clarify (and it seems you understood what I meant): "in the vein of sort.Interface" rather than "a deque managed in terms of the actual sort.Interface."

 

Of course if you actually do it, please be sure to let us know the outcome in terms of performance.

Hypothetically it should have better performance for the same algorithm; such efforts like this tend to flop on the performance front, even compared to a linear amount of boxing and type assertion operations, if a large amount of bookkeeping is needed just to support the abstraction. If it is manageable, but the performance is not considerably worse than an interface{} solution, I think there'll be some who'd appreciate the additional peace of mind.

Recently I've thought about whether a large subset of container/ring could be reimplemented in a similar "not stored here" approach; there wouldn't be much benefit in doing so since some sacrifice in convenience (even beyond the inconvenience of type assertions and the corresponding loss of trivial type checks that container/ring already has). I sense that deques would require comparatively fewer sacrifices to get something decent in the sort.Interface realm of things. Until I can actually demonstrate the concept (much less figure out how to come up with a comprehensible API), I'm going to drop the point.

 

I for my part am happy to have at least beaten container/list.

Agreed, and it should be a better fit for a number of use-cases which currently depend on container/list.