Priority search queues for Elixir.
Add psq to your list of dependencies in mix.exs
:
def deps do
[{:psq, "~> 0.1.0"}]
end
See the docs for usage and examples.
The implementation uses priority-search pennants as described in this paper, with very few modifications. Internally, tuples are used to represent nodes in the winner/loser tree (since they offered a significant performance boost over structs).
Testing uses the excellent excheck library for QuickCheck-style tests; benchmarking uses Benchee.
Contributions welcome! I'd particularly welcome:
-
Suggestions for improving the interface. I did my best to make it "elixir-y", but I haven't used it enough to know if the interface makes sense for a variety of use-cases.
-
Performance optimizations. Making a queue with 10 million entries is viable but takes quite a long time (~120s on my machine, vs ~10s for sorting the equivalent list). I'd love to get the time to build a queue be roughly equivalent to the time to sort a list. If you want to play around with that stuff, be sure to use run the benchmarks before and after (
mix run bench/bench.exs
).