racket / data

Other
16 stars 23 forks source link

Cleanup heap #15

Closed Metaxal closed 4 years ago

Metaxal commented 4 years ago

Before the bigger changes, I wanted to cleanup the code and also avoid some unnecessary operations (pulling some vector-set!s and vector-refs out of the loops in heapify-up and heapify-down). The performance impact is not large (about 5-10% speedup) but it will have a higher impact with encapsulation.

Shrinking and growing are now also a little cleaner by relying on a single growth function fittest-block-size instead of ad-hoc codes and (small) loops. Some tests are added to check that this function is well-behaved.

As agreed before with Sam on slack, this also changes the return value of heap-remove! to boolean? instead of void?.

Metaxal commented 4 years ago

Hi there, any update on this? I'm waiting for feedback on this one before continuing with the other PR(s).

rmculpepper commented 4 years ago

If the tests succeed, then I think this is fine to merge. I do have a suggestion for clarifying the heapify-{up,down} changes: Add back the extra vector-set but comment it out, then add a note explaining that the new version delays the upward/downward (depending on the function) moves and collapses them into one.

Also, for the new code, I would use internal definitions instead of let*, but that's up to you. (I wouldn't touch other functions just to make that change, though.)

Metaxal commented 4 years ago

All done.

Metaxal commented 4 years ago

raco setup -l data goes through fine. raco test . in the test directory: all tests pass.

rmculpepper commented 4 years ago

Is this ready now? If so, I'll merge it.

Metaxal commented 4 years ago

For me it's ready, unless someone has any new concern. @sorawee are you happy with the update?

sorawee commented 4 years ago

Yep, it looks good to me!

Metaxal commented 4 years ago

@rmculpepper It's ready.