Skip to content
New issue

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

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

Already on GitHub? # to your account

perf: improve performance of filter_period_intersect #436

Merged
merged 3 commits into from
Nov 11, 2023

Conversation

cjc7373
Copy link
Contributor

@cjc7373 cjc7373 commented Nov 10, 2023

In general, this reduces complexity of O(n^2) to O(n lgn).
From the benchmark we can see the performance gain:

     Running benches/bench.rs (target/release/deps/bench-a5f1a4e304f6ce84)
Gnuplot not found, using plotters backend
1000 events             time:   [443.46 µs 444.09 µs 444.76 µs]
                        change: [-92.832% -92.611% -92.413%] (p = 0.00 < 0.05)
                        Performance has improved.

@ErikBjare
Copy link
Member

Very nice! Slightly embarrassed that it was O(n^2) to begin with 😅

Thank you so much for this!

@ErikBjare ErikBjare merged commit 55cad4a into ActivityWatch:master Nov 11, 2023
# for free to join this conversation on GitHub. Already have an account? # to comment
Labels
None yet
Projects
None yet
Development

Successfully merging this pull request may close these issues.

2 participants