2
\$\begingroup\$

I'm trying to implement a suffix array for use in programming competitions. I'm using the CodeForces example and trying to "make it my own" so I can make sure I understand it and feel better about using it.

Here's what I have so far:

struct SuffixArray {
    vector<int> sa, pos, tmp;
    int n, gap;

    SuffixArray(string s) {
        n = s.length();
        sa = pos = tmp = vector<int>(n);
        for (int i=0; i<n; i++) sa[i] = i, pos[i] = s[i], tmp[i] = 0;
        for (gap = 1;; gap *= 2) {
            quickSort(sa, n, 0, n - 1);
            for (int i=0; i<n-1; i++) tmp[i+1] = tmp[i] + sufCmp(sa[i], sa[i+1]);
            for (int i=0; i<n; i++) pos[sa[i]] = tmp[i];
            if (tmp[n-1] == n - 1) break;
        }
    }

    bool sufCmp(int i, int j) {
        if (pos[i] != pos[j]) return pos[i] < pos[j];
        i += gap;
        j += gap;
        return (i < n && j < n) ? pos[i] < pos[j] : i > j;
    }

    int partition(vector<int> &arr, int lo, int hi) {
        int p = arr[hi];
        int pi = lo;
        for (int i=lo; i<hi; i++) {
            if (sufCmp(arr[i], p)) {
                swap(arr[i], arr[pi]);
                pi++;
            }
        }
        swap(arr[hi], arr[pi]);
        return pi;
    }

    void quickSort(vector<int> &arr, int sz, int lo, int hi) {
        if (lo < hi) {
            int p = partition(arr, lo, hi);
            quickSort(arr, sz, lo, p-1);
            quickSort(arr, sz, p+1, hi);
        }
    }
};

This works, but it is hopelessly slower than the original. On this problem from SPOJ, it scores in the range expected by a naive solution which is \$O(n^2 \log n)\$.

My question is, why? My guess is it either has to do with the way I am storing and accessing data (wrapping everything in a struct, using vectors instead of pre-allocated arrays), or it could be an issue with my quickSort implementation (since the suffix array will already be 'mostly' sorted on all but the first iteration, using the last element as pivot could be bad), but I don't understand enough about what's going on under the hood to be sure.

I tested the pivot theory by using the middle element instead of the last element as the pivot for the quicksort... still way too slow.

\$\endgroup\$
4
  • \$\begingroup\$ Welcome to CodeReview! This is quite the first post, I hope you get some fine answers. \$\endgroup\$
    – Legato
    Apr 1, 2015 at 17:21
  • \$\begingroup\$ Why do you change from basic_string<char> to vector<int>? I suspect that the type conversion may be part of the problem. \$\endgroup\$
    – Snowbody
    Apr 2, 2015 at 2:55
  • \$\begingroup\$ Where does that happen? \$\endgroup\$ Apr 2, 2015 at 3:11
  • \$\begingroup\$ The input parameter to the constructor is of type string, but the various arrays are stored as vector<int> which are copied from the string. \$\endgroup\$
    – Snowbody
    Apr 2, 2015 at 13:20

1 Answer 1

2
\$\begingroup\$
vector<int> sa, pos, tmp;
int n, gap;

Surely you could come up with better variable names than these? Also, tmp and sa are only used inside the constructor, so they should be local variables, not struct members.

SuffixArray(string s)

This should be const string & s to avoid unnecessary copying of the string.

for (int i=0; i<n; i++) sa[i] = i, pos[i] = s[i], tmp[i] = 0;

The comma operator has a few legitimate uses, but this is not one of them. Coding it this way will lead to problems if you need to modify the loop body at all. The right way to do this is to make a multi-statement loop the usual way: curly braces surrounding multiple lines with one statement on each line.

 for (int i=0; i<n; i++)
 {
   sa[i] = i;
   pos[i] = s[i];
   tmp[i] = 0;
 }
     for (gap = 1;; gap *= 2) {

Why do you have a for loop with an empty termination condition?

\$\endgroup\$
5
  • \$\begingroup\$ Thanks for the critiques Snowbody. I didn't notice that I was copying the string unnecessarily, good catch. You are also right that tmp should be a local variable. sa would be too, but it contains the actual suffix array which I will need access to when I add more functionality later. \$\endgroup\$ Apr 2, 2015 at 2:24
  • \$\begingroup\$ I'm sorry if I didn't make this clear but I am not the original author of this code (it's from CodeForces). I agree that the style is on the terse side, but for programming competitively, it is easier to work with. I'm mainly looking for enhancements in the performance of the code. Do you have any critiques that fall in that category? \$\endgroup\$ Apr 2, 2015 at 2:37
  • \$\begingroup\$ If you're not the author of the code, it's not really on-topic for codereview. See meta.codereview.stackexchange.com/a/3654/11647 \$\endgroup\$
    – Snowbody
    Apr 2, 2015 at 3:56
  • \$\begingroup\$ Admittedly, I did not see that rule. However, while I'm not the original author, I have tweaked the original code a fair amount, and these tweaks are the subject of my question, so I think it's still on-topic (correct me if I'm wrong). Do you have any idea why the changes I made would decrease the performance of the code so much? Thanks again for your help. \$\endgroup\$ Apr 2, 2015 at 4:10
  • \$\begingroup\$ The only thing I can think of is the implementation of sort as the code looks functionally identical. Do you have access to a timing profiler? \$\endgroup\$
    – Snowbody
    Apr 2, 2015 at 13:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.