search

lspitzner / pqueue

Haskell priority queue package
Other
15 stars 13 forks source link

Make queues more compact #28

Open treeowl opened 3 years ago

treeowl commented 3 years ago

For simple queues, the obvious place to start is something like

newtype Zero k = Zero k

For key-value queues, we could start by storing multiple entries in the leaves.

The next potential step would be switching from binomial queues to 3-nomial or even 4-nomial queues.

konsumlamm commented 3 years ago

I tried to adapt the current code to use 3-nomial queues (though I'm not entirely sure it's correct) and according to my (somewhat naive) benchmarks, the speed for insert stays about the same, while deleteMin gets considerably faster (I only benched those two operations, since those are the most important ones). So I think we should definitely consider switching to 3-nomial or 4-nomial queues!

EDIT: The speedup only seems to really occur for random values though.

treeowl commented 1 year ago

Suppose we replace data Zero a = Zero with newtype One a = One a. That means the binomial heap will no longer support binomial trees of size one. That means that MinQueue will need one constructor for even sizes and another constructor for odd sizes. Conjecture: we'll get smaller, faster queues without too much extra effort. Downside: it'll be more work to add support for queues that don't track the minimum or size. Annoyance: the benefits for the Prio version will be somewhat less, which feels awkward.

Is there an alternative that naturally supports binomial trees of size 1 with less effort?