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

Remove O(N^2) operation from NumberedObjectCollection #556

Closed
MicahGale opened this issue Sep 30, 2024 · 0 comments · Fixed by #563
Closed

Remove O(N^2) operation from NumberedObjectCollection #556

MicahGale opened this issue Sep 30, 2024 · 0 comments · Fixed by #563
Assignees
Labels
feature request An issue that improves the user interface. performance 🐌 Issues related to speed and memory

Comments

@MicahGale
Copy link
Collaborator

Is your feature request related to a problem? Please describe.

I was analyzing some data from parsing times and found that we have O(N^2) scaling despite fixing #510. After some investigation I found the culprit is in NumberedObjectCollections.append. This runs through all of self.numbers every time which is a generator over the entire list.... O(N^2).

So this should be eliminated.

Describe the solution you'd like

A few solutions.

  1. Remove this operation from read_input and do a bulk add that is optimized
  2. Make NumberedObjectCollection a lot more like dicts, and rely on __num_cache a lot more. Through the number property we guarantee that numbers are always update for objects tied to problem. So maybe we use this O(n^2) operation only as a last resot.
@MicahGale MicahGale added feature request An issue that improves the user interface. performance 🐌 Issues related to speed and memory labels Sep 30, 2024
@MicahGale MicahGale changed the title Remove O(N<sup>2</sup>) operation from NumberedObjectCollection Remove O(N^2) operation from NumberedObjectCollection Sep 30, 2024
@MicahGale MicahGale self-assigned this Oct 2, 2024
@MicahGale MicahGale linked a pull request Oct 2, 2024 that will close this issue
3 tasks
MicahGale added a commit that referenced this issue Oct 3, 2024
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
feature request An issue that improves the user interface. performance 🐌 Issues related to speed and memory
Projects
None yet
Development

Successfully merging a pull request may close this issue.

1 participant