讨论/技术交流/为什么leetcode上c++的vector这么慢??/
为什么leetcode上c++的vector这么慢??

感觉 leetcode 上的vector速度比数组慢很多。

比如说这道题 1163.按字典序排在最后的子串,最近学了后缀数组,发现这道题可以用,就试了一下,结果vector版本的直接超时,换成数组后提交耗时 900ms900ms 左右,leetcode 上 c++ 的限时应该是 2s2s,也就是两个版本的速度差了两倍以上!我自己也测试了一下,结果是两者速度差距不大,但为什么在 leetcode 上会差这么多?

class Solution {
public:
    string lastSubstring(string s) {
        const int n = s.size();
        int m = 128;
        vector<int> bucket(m);
        vector<int> sa(n), rk(n), cosa(n), cork(n);
        for (int i = 0;i < n;++i) ++bucket[rk[i] = s[i]];
        for (int i = 1;i < m;++i) bucket[i] += bucket[i - 1];
        for (int i = n - 1;0 <= i;--i) sa[--bucket[rk[i]]] = i;
        for (int w = 1;w < n;w *= 2) {
            int p = 0;
            for (int i = n - 1;n - w <= i;--i) cosa[p++] = i;
            for (int i = 0;i < n;++i) if (w <= sa[i]) cosa[p++] = sa[i] - w;
            bucket.assign(m, 0);
            for (int i = 0;i < n;++i) ++bucket[rk[cosa[i]]];
            for (int i = 1;i < m;++i) bucket[i] += bucket[i - 1];
            for (int i = n - 1;0 <= i;--i) sa[--bucket[rk[cosa[i]]]] = cosa[i];
            swap(rk, cork);
            rk[sa[0]] = p = 0;
            int prex = cork[sa[0]];
            int prey = sa[0] + w < n ? cork[sa[0] + w] : -1;
            for (int i = 1;i < n;++i) {
                const int curx = cork[sa[i]];
                const int cury = sa[i] + w < n ? cork[sa[i] + w] : -1;
                if (curx != prex || cury != prey)
                    rk[sa[i]] = ++p;
                else rk[sa[i]] = p;
                prex = curx;
                prey = cury;
            }
            if (p == n)
                break;
            m = p + 1;
        }
        return s.substr(sa[n - 1]);
    }
};
class Solution {
public:
    string lastSubstring(string s) {
        const int n = s.size();
        int m = 128;
        const auto buffer = new int[4 * n];
        const auto bucket = new int[max(m, n)]();
        const auto sa = buffer, cosa = sa + n;
        auto rk = cosa + n, cork = rk + n;
        for (int i = 0;i < n;++i) ++bucket[rk[i] = s[i]];
        for (int i = 1;i < m;++i) bucket[i] += bucket[i - 1];
        for (int i = n - 1;0 <= i;--i) sa[--bucket[rk[i]]] = i;
        for (int w = 1;w < n;w *= 2) {
            int p = 0;
            for (int i = n - 1;n - w <= i;--i) cosa[p++] = i;
            for (int i = 0;i < n;++i) if (w <= sa[i]) cosa[p++] = sa[i] - w;
            memset(bucket, 0, sizeof(int) * m);
            for (int i = 0;i < n;++i) ++bucket[rk[cosa[i]]];
            for (int i = 1;i < m;++i) bucket[i] += bucket[i - 1];
            for (int i = n - 1;0 <= i;--i) sa[--bucket[rk[cosa[i]]]] = cosa[i];
            swap(rk, cork);
            rk[sa[0]] = p = 0;
            int prex = cork[sa[0]];
            int prey = sa[0] + w < n ? cork[sa[0] + w] : -1;
            for (int i = 1;i < n;++i) {
                const int curx = cork[sa[i]];
                const int cury = sa[i] + w < n ? cork[sa[i] + w] : -1;
                if (curx != prex || cury != prey)
                    rk[sa[i]] = ++p;
                else rk[sa[i]] = p;
                prex = curx;
                prey = cury;
            }
            if (p == n)
                break;
            m = p + 1;
        }
        return s.substr(sa[n - 1]);
    }
};
共 3 个回复

但这里的数组是用new创建的,并不是在栈上。而且有差距正常,但我觉得不至于差两倍以上。

能用数组为什么非要用vector呢?

硬要说的话一个是开在堆上一个是开在栈上,有点性能差异也是很正常的吧