Paring heap without shared_ptr #1707
Conversation
This comment was marked as duplicate.
This comment was marked as duplicate.
jere8184
force-pushed
the
paring_heap
branch
7 times, most recently
from
a18ba68 to
fb52b9f
Compare
|
unlink_node is now private. remove_node method added. 32% performance increase observed. |
jere8184
force-pushed
the
paring_heap
branch
from
fb52b9f to
82e7f1f
Compare
| std::shared_ptr<this_type> prev_sibling; | ||
| std::shared_ptr<this_type> next_sibling; | ||
| std::shared_ptr<this_type> parent; // for decrease-key and delete | ||
| this_type* child = nullptr; |
There was a problem hiding this comment.
Why did you rename the member?
There was a problem hiding this comment.
I felt it made more sense as a node can only have one child. Happy to change it back.
There was a problem hiding this comment.
In the code yes, but from a conceptual view, each node still has many children. The reason it's done this way is so that the pairing heap can be represented as a binary tree. You can read more about the concept here: https://en.wikipedia.org/wiki/Left-child_right-sibling_binary_tree
So first_child (or left_child) is more accurate.
| #if OPENAGE_PAIRINGHEAP_DEBUG | ||
| #endif |
There was a problem hiding this comment.
This code block does nohing now
| } | ||
|
|
||
| this->node_count -= 1; | ||
| size_t erase_result = this->nodes.erase(ret); |
There was a problem hiding this comment.
You are never using erase_result if OPENAGE_PAIRINGHEAP_DEBUG is false.
| * Ω(log log n), O(2^(2*√log log n')) | ||
| * caller must eventually either add node back to heap or delete it | ||
| */ | ||
| element_t pop_node() { |
There was a problem hiding this comment.
It looks like pop_node() no longer deletes the node from the pointer, so this may cause issues. Especially if other methods like unlink_node() expect that pop_node() does deletion.
If you look back at 4ab602a#diff-84a922def1ded03f0d8849cb1c1d56e758f9ae47a06cb78fc40b193294d40ab9R380 where the shared:ptr implementation was introduced, you can see that there originally was no pop_node() (only pop()). Maybe it makes sense to merge the methods again.
There was a problem hiding this comment.
I noticed as well, that's why I made pop_node() and unlink_node() private, I thought maybe as long as their callers handle the node correctly, it should be fine. I have merged both the methods.
In the ptr raw implementation that was changed by 4ab602a there's both pop_node() and pop().
There was a problem hiding this comment.
In the old implementation, pop_node was technically only a delete (more akin to remove_node now). It's a bit confusing bcause of the renames. Merging the functions is the right call I think.
heinezen
added
improvement
jere8184
force-pushed
the
paring_heap
branch
2 times, most recently
from
03571e7 to
b286c0c
Compare
jere8184
force-pushed
the
paring_heap
branch
from
30a5ed3 to
6eb3186
Compare
| #if OPENAGE_PAIRINGHEAP_DEBUG | ||
| std::unordered_set<element_t> nodes; | ||
| #endif |
There was a problem hiding this comment.
I wonder if we could keep this set only when OPENAGE_PAIRINGHEAP_DEBUG is true, so that the eap becomes even more efficient. Looks like it's only necessary for clearing up the nodes on deletion right now. I suggest we could try this solution:
- From
clear(), useiter_allto iterate through all the nodes and calldeleteon them. - Wrap all interactions of
nodeswith the#if OPENAGE_PAIRINGHEAP_DEBUGpreprocessor thing again.
There was a problem hiding this comment.
alright sound like a plan :)
|
I think I may have made a small mistake :/ |
fixes #1675