search

kth-competitive-programming / kactl

KTH Algorithm Competition Template Library (... eller KTHs AC-tillverkande lapp)
2.7k stars 726 forks source link

Suffix array is a bit slow #190

Open simonlindholm opened 3 years ago

simonlindholm commented 3 years ago

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 2 years ago

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.