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.

Sign up for GitHub

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

Jump to bottom

Taiko diffcalc cheese detector has O(n^2) complexity #10190

Closed
smoogipoo opened this issue Sep 19, 2020 · 0 comments · Fixed by #10191
Closed

Taiko diffcalc cheese detector has O(n^2) complexity #10190

smoogipoo opened this issue Sep 19, 2020 · 0 comments · Fixed by #10191
Labels
area:difficulty priority:0 Showstopper. Critical to the next release. ruleset/osu!taiko type:performance
Milestone
October 2020

Comments

@smoogipoo
Copy link
Contributor

smoogipoo commented Sep 19, 2020 •
edited

The following maps will make taiko diffcalc hang pretty much endlessly:
https://osu.ppy.sh/beatmapsets/1164271#osu/2428686
https://osu.ppy.sh/beatmapsets/1164230#osu/2428616
https://osu.ppy.sh/beatmapsets/1124068#osu/2352021
https://osu.ppy.sh/beatmapsets/1124068#osu/2352019

The reason is because these have 50000+ hitobjects (last one has 350000), and run into

osu/osu.Game.Rulesets.Taiko/Difficulty/Preprocessing/StaminaCheeseDetector.cs

Line 90 in 10400b4

markObjectsAsCheese(i, repeatedLength);

osu/osu.Game.Rulesets.Taiko/Difficulty/Preprocessing/StaminaCheeseDetector.cs

Line 127 in 10400b4

markObjectsAsCheese(i, tlLength);

with every increment of the loop, effectively iterating some 122500000000 times...
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees
No one assigned
Labels
area:difficulty priority:0 Showstopper. Critical to the next release. ruleset/osu!taiko type:performance
Projects
None yet
Milestone
October 2020
Development

Successfully merging a pull request may close this issue.

Fix n^2 characteristic in taiko diffcalc smoogipoo/osu
1 participant
@smoogipoo