Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

improve complexity of updating uid #236

Closed
maximelucas opened this issue Dec 2, 2022 · 0 comments · Fixed by #239
Closed

improve complexity of updating uid #236

maximelucas opened this issue Dec 2, 2022 · 0 comments · Fixed by #239
Labels
improve Make an existing feature better

Comments

@maximelucas
Copy link
Collaborator

maximelucas commented Dec 2, 2022

From #225 (comment) by @nwlandry:

The only concern that I have with this is that it would be amazing if we could somehow leverage the self._edge_uid to make this an O(1) update instead of an O(|E|) update. As in, once we validate the edges that have been added to update self._edge_uid, we shouldn't need to iterate over these edges again when we update again.

One way to fix it would be to collect all "valid integer" new IDs when checking if they exist already.
From this we take the max, compare it to the current H._edge_uid and update it if the new value is larger. This would break the update_uid function into two separate parts.

@maximelucas maximelucas added the improve Make an existing feature better label Dec 2, 2022
@nwlandry nwlandry linked a pull request Dec 4, 2022 that will close this issue
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
improve Make an existing feature better
Projects
None yet
Development

Successfully merging a pull request may close this issue.

1 participant