讨论/技术交流/计算量相同情况下,不同和相同时间复杂度的算法执行时间为什么会有明显差异/
计算量相同情况下,不同和相同时间复杂度的算法执行时间为什么会有明显差异

之前写二进制题的时候,看到一道求Int32二进制表示中1的数量的奇偶性的题目(第K个语法符号),意识到1个问题:

  1. 使用掩码O(1)解决的话,需要一次进行5步运算;
  2. 按位进行O(log2)解决,需要迭代5次,每次1步运算;
  3. 拆分第2种迭代的循环,改为if判断做5步运算;
    我发现这三种做法在大量数据测试下所需的时间差异是很明显的,先放上我的代码(Solution里分别是三种做法,main里是我的时间测试,测试数据选择了1到1e9的数据顺序执行):
class Solution {
public:
    int kthGrammar1(int n, unsigned int k) {
        --k;
        k = (k >> 16)^(k & (0x0000ffff));
        k = (k >> 8) ^(k & (0x000000ff));
        k = (k >> 4) ^(k & (0x0000000f));
        k = (k >> 2) ^(k & (0x00000003));
        k = (k >> 1) ^(k & 1);
        return k;
    }
    int kthGrammar2(int n, int k) {
        bool cnt = 0;
        --k;
        while(k){
            cnt = !cnt;
            k &= (k-1);
        }
        return cnt;
    }
    int kthGrammar3(int n, int k) {
        bool cnt = 0;
        --k;
        if(!k) return cnt;
        cnt = !cnt;
        k &= (k-1);
        if(!k) return cnt;
        cnt = !cnt;
        k &= (k-1);
        if(!k) return cnt;
        cnt = !cnt;
        k &= (k-1);
        if(!k) return cnt;
        cnt = !cnt;
        k &= (k-1);
        if(!k) return cnt;
        cnt = !cnt;
        k &= (k-1);
        if(!k) return cnt;
    }
};

int main(){
    Solution test;

    clock_t st = clock();
    for(int i=1;i<=1e9;++i){
        test.kthGrammar1(30,i);
    }
    cout << (clock()-st)/(double)CLK_TCK << endl;

    st = clock();
    for(int i=1;i<=1e9;++i){
        test.kthGrammar2(30,i);
    }
    cout << (clock()-st)/(double)CLK_TCK << endl;

    st = clock();
    for(int i=1;i<=1e9;++i){
        test.kthGrammar3(30,i);
    }
    cout << (clock()-st)/(double)CLK_TCK << endl;
}

经过时间测试,我发现在我的机器上三种做法的时间结果分别是:
5.596s
28.474s
8.455s
这表明虽然都是执行5步运算得到结果(并且1是严格执行5步,2、3通常执行不满5步),但是1的速度明显是最快的(我猜测可能因为全部使用位运算计算?);1的问题先保留,但2、3实际上是一种做法,只不过2使用了while循环,而3改用if判断终止,而两者的时间差异是明显的,这让我很难理解,希望各位能过解除我的疑惑。

3
共 5 个回复

建议学一遍csapp,对循环展开,分支预测等一些概念有一个初步的了解

2

有道理

1

是的,我知道gcc的builtin可以高效的做到这些,但我想知道的不是针对这个题目,而是这个时间差距来自哪里,毕竟执行的运算次数应该是相同的。

1

你们在聊什么??!

教你一招

class Solution {
public:
    int kthGrammar(int N, int K) {
        return __builtin_popcount(K-1)%2;
    }
};

省去你这些冗赘过程。