困惑于为什么我的算法运行速度比它应该慢

Question

纯粹是为了好玩,我决定写一个简单的算法,找到2和x之间的所有素数,其中x是你想要的.我用a clock_t来计算算法完成变化x值需要多长时间.(我去x = 0,然后是25000,然后是50000,然后是75000,......,最多1,000,000).例如,当x = 25000时,我进入for循环,i从2到25000,并且对于每个值i,我通过将它除以两个和它自身之间的每个数字来检查它是否是素数,寻找剩余的0.

这是算法:

vector<int> calcPrimesWithoutPrechecking(int upperLimit)
{
    vector<int> res;

    for(int i = 2; i <= upperLimit; i++)
    {
        int currentNum = i;
        bool foundDivisible = false;
        for(int j = 2; j < currentNum; j++)
        {
            if(currentNum % j == 0)
            {
                foundDivisible = true;
                break;
            }
        }

        if(!foundDivisible)
        {
            res.push_back(i);
        }
    }

    return res;
}

我想我可以通过检查我们当前正在测试的数字的最后一位数来加快速度.如果该数字是0,2,4,5,6或8,那么我甚至不必检查它是否是素数,因为我知道它不是(当然2,3和5都是,所以那些被处理在一开始的时候).我打电话给这个预先检查.这是预先检查的算法:

vector<int> calcPrimesWithPrechecking(int upperLimit)
{
    vector<int> res;
    res.push_back(2);res.push_back(3);res.push_back(5);    
    for(int i = 6; i <= upperLimit; i++)
    {
        bool foundDivisible = false;    
        int lastDig = i%10;
        if(lastDig == 0
            || lastDig == 2
            || lastDig == 4
            || lastDig == 6
            || lastDig == 8
            || lastDig == 5)
        {
            foundDivisible = true;
        }    

        int currentNum = i;
        for(int j = 2; j < currentNum && !foundDivisible; j++)
        {
            if(currentNum % j == 0)
            {
                foundDivisible = true;
                break;
            }
        }    

        if(!foundDivisible)
        {
            res.push_back(i);
        }
    }    
    return res;
}

我将结果输出到控制台,并将它们写入文本文件.然后我将时间复制到excel,并绘制它们.但是,出于某种原因,具有预检查的算法较慢.我几乎肯定它会更快.当我运行程序时,我故意关闭计算机上的每个程序,然后在发布模式下运行它.我已经在调试中测试了每个算法,它们确实都按预期工作.

这是我的数据.

x轴是我们检查的素数的数量(例如25000意味着我们正在寻找2到25000之间的所有素数),而y轴是获得所有素数的时间(以秒为单位).

有人可以解释为什么理论上应该取出许多计算的第二个算法实际上更慢？

Answer 1

使用预检查实现稍微慢一点的原因是它需要做更多的工作来消除在内循环的第一步之后将消除的许多数字.

以数字8为例:预先检查需要找到除法余数并在消除它之前执行五次比较,而没有预检查的程序8也会消除,但是只有一个除以2并且比较为零.

你可能会看到一点胜利的唯一数字是5,但这些数字并不像偶数数字那样普遍,你的程序会丢失CPU周期.

加快这一点的一个更好的方法是完全避免数字:回想一下之后的所有素数3都是形式6*k+1或者6*k-1.现在你可以快三次迭代!

另一件事是你不需要检查候选素数的平方根之后的除数(你能证明为什么会这样吗？)这种改变本身就会带来巨大的改善.

最后,一个非常有用的技巧是存储你到目前为止发现的所有素数,并将它们用于你的试验除数.这将大大提高内循环的速度.