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

Suffix array is a bit slow #190

Open

simonlindholm opened this issue Mar 20, 2021 · 1 comment

Member

simonlindholm commented Mar 20, 2021

Apparently the suffix array is a bit slow and has resulted in TLEs.

One suggestion that came up in the AC discord server (https://discord.com/channels/555883512952258563/559415184826040340/809806400070483989) is splitting

for (int i = n; i--;) sa[--ws[x[y[i]]]] = y[i];

into multiple loops, e.g.

for (int i = n; i--;) tmp[i] = x[y[i]];
for (int i = n; i--;) tmp[i] = --ws[tmp[i]];
for (int i = n; i--;) sa[tmp[i]] = y[i];

which seems to help on random data. It's not obvious why, but I'm speculating that it's due to load mispredictions.

The suffix array seems to perform worse on repetitive data though (e.g. s[i] = i % 10), and the change makes performance worse in that case. :(

evouga commented Feb 19, 2022

I'm also having trouble with this implementation; it is too slow to pass several CSES problems, such as https://cses.fi/problemset/task/1111/ or https://cses.fi/problemset/task/1110.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment