Skip to content
This repository has been archived by the owner on Apr 28, 2023. It is now read-only.

Assess speed up due to heap structure #1

Closed
razziel89 opened this issue Dec 17, 2021 · 1 comment · Fixed by #13
Closed

Assess speed up due to heap structure #1

razziel89 opened this issue Dec 17, 2021 · 1 comment · Fixed by #13
Labels
enhancement New feature or request

Comments

@razziel89
Copy link
Owner

razziel89 commented Dec 17, 2021

The current implementation that simply iterates over a graph is not as efficient as using a binary heap. Assess speed up by using a heap structure.

Greatly improve speed up by making nodes aware of which graph they are in. That way, a node can only be in one graph, but that's OK as it greatly improves performance. We will get rid of the map entirely.

@razziel89 razziel89 self-assigned this Dec 17, 2021
@razziel89 razziel89 added the enhancement New feature or request label Dec 17, 2021
@razziel89 razziel89 mentioned this issue Dec 17, 2021
@razziel89 razziel89 removed their assignment Dec 17, 2021
@razziel89 razziel89 changed the title Use binary heap Assess speed up due to heap structure Dec 21, 2021
@razziel89
Copy link
Owner Author

razziel89 commented Dec 21, 2021

Turns out a heap structure is a lot more efficient than the current graph implementation, at least when it comes to addition and removal of the cheapest element. But a heap, as currently implemented via a simple slice, is not really efficient when it comes to determining whether an element exists in it.

In #12, a heap will be implemented that is a hybrid of a struct and a map. The struct will be used for efficient addition and removal of elements in sorted order while the map will be used to determine whether an element exists.

Sign up for free to subscribe to this conversation on GitHub. Already have an account? Sign in.
Labels
enhancement New feature or request
Projects
None yet
Development

Successfully merging a pull request may close this issue.

1 participant