damn-fast-priority-queue icon indicating copy to clipboard operation
damn-fast-priority-queue copied to clipboard

Implement changes from @mfiano

Open phoe opened this issue 4 years ago • 1 comments

https://gist.github.com/mfiano/3ddf2810cf8101f66009c3fdde8b020b

  • The local swap functions are closing over state. Make them take the parent and left/right indices. To do this just return the left/right indices and wrap the callers in (setf parent-index ...).
  • You can lexibind some aref lookups that are called multiple times, particular the parent, left, and right priority.
  • In some various other places in the codebase, you can also lexibind the aref calls that are called more than once. I forget where though.

Also read-eval (ash 1 64) just to be sure it's a constant for implementations that don't do constant folding for whatever reason.

phoe avatar May 22 '21 17:05 phoe

Also see the benchmark at https://github.com/jdz/simple-pairing-heap/blob/master/bench.org

phoe avatar Jan 27 '22 09:01 phoe