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

The Immutable Priority Queue has poor performance in specific situations #1009

Open
Lampese opened this issue Sep 17, 2024 · 0 comments
Open
Labels

Comments

@Lampese
Copy link
Collaborator

Lampese commented Sep 17, 2024

The immut/priority_queue in the current core uses the pairing-heap algorithm, which only folds the entire heap when querying the results. Other operations are O(1). Although its constant is very small and the average complexity can be O(log n). But if it is in the case of immutable, it is likely to cause too much time to be spent on a certain version of the operation, resulting in an invalid average complexity. We should use algorithms that can maintain stable complexity even in immutable situations.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
Projects
None yet
Development

No branches or pull requests

1 participant