-2

我正在研究一种算法，并希望使我的代码更高效。我的代码使用简单的算术和比较语句。但是，我想替换 if 语句，因为它们可能很耗时。这段代码将运行超过一百万次，因此，即使是最轻微的改进也是值得赞赏的。请回答！这是代码- 

int_1024 sqcalc(int_1024 s,int_1024 f){
    f=f*20;
    s=s-81;
    s=s-(f*9);
    if(s>=0){
        return 9;
    }
    s=s+f;
    s=s+17;
    if(s>=0){
        return 8;
    }
    s=s+f;
    s=s+15;
    if(s>=0){
        return 7;
    }
    s=s+f;
    s=s+13;
    if(s>=0){
        return 6;
    }
    s=s+f;
    s=s+11;
    if(s>=0){
        return 5;
    }
    s=s+f;
    s=s+9;
    if(s>=0){
        return 4;
    }
    s=s+f;
    s=s+7;
    if(s>=0){
        return 3;
    }
    s=s+f;
    s=s+5;
    if(s>=0){
        return 2;
    }
    s=s+f;
    s=s+3;
    if(s>=0){
        return 1;
    }
    s=s+f;
    s=s+1;
    if(s>=0){
        return 0;
    }
}

我希望替换 if 检查，因为我“认为”它们会使算法变慢。有什么建议吗？int_1024 是一个具有 1000 位的 ttmath 变量，所以保存它可能是一个不错的选择？这么大的数字可能会除法或乘法慢点，所以我尝试使用加法，但无济于事。请帮助。

4

4 回答 4

7

我不知道它是否更快，但它要短得多（并且更容易分析）。

int k[] = { 17, 15, 13, 11, 9, 7, 5, 3, 1 };
int r = 0;
f *= 20;
s -= 81;
s -= f * 9;
while (s < 0) {
    s += f;
    s += k[r];
    if (++r == 9) break;
}
if (s >= 0) return 9-r;

编辑： 事实上，最初的发布者想出了一个聪明的方法来优化这个循环，通过预先计算k数组中常量的总和，并与s总和进行比较，而不是逐步将它们添加到s.

编辑： 我遵循了月影的分析技术，但得出了不同的方程式。原始的 TeX 格式替换为 ASCII 艺术（我试图让 MathJax 为我渲染 TeX，但它不起作用）：

S[0] = s                      >= 0 => 9 - 0
S[1] = S[0]   + f + 19 - 2*1  >= 0 => 9 - 1
S[2] = S[1]   + f + 19 - 2*2  >= 0 => 9 - 2
...
S[i] = S[i-1] + f + 19 - 2*i  >= 0 => 9 - i

所以要计算S[n]：

    S[n] = S[n-1] + f + 19 - 2n
               .-- n
=>  S[n] = s +  >      (f + 19 - 2*i)
               `-- i=1       .-- n
=>  S[n] = s + n(f + 19) - 2  >      i
                             `-- i=1
=>  S[n] = s + n(f + 19) - n(n+1)
                            2
=>  S[n] = s + n(f + 18) - n

因此，不等式S[n] >= 0是 中的二次方程n。假设s < 0，我们想n成为二次解的上限。

    +--                         --+
    |               _____________ |
    |             /        2      |
    | f + 18 - . / (f + 18) + 4s  |
    |           `                 |
n = | --------------------------- |
    |             2               |

所以例程看起来像：

f *= 180;
s -= 81;
s -= f;
if (s >= 0) return 9;
f /= 9;
f += 18;
s *= 4;
int1024_t ff = f;
ff *= f;
ff += s;
ff = ff.Sqrt();
f -= ff;
f += f.Mod2();
return 9 - f/2;

但是，我不确定在大整数对象上执行这些操作的费用是否值得实现以替换上面显示的简单循环。（除非您希望扩展该功能并且需要更长的循环。）

为了比循环更快，大整数平方根实现必须始终在 4 次迭代内收敛，以超过现有 while 循环的平均预期 4.5 次迭代。但是，该ttmath实现似乎并未计算整数平方根。它似乎计算一个浮点平方根，然后对结果进行四舍五入，我猜这会比循环慢得多。

于 2012-06-08T16:15:42.203 回答
6

首先，我注意到如果final的条件if()为false，则返回值是未定义的。你可能想解决这个问题。

现在，函数以

f=f*20;
s=s-81;
s=s-(f*9);
if(s>=0){
    return 9;
}

其余的看起来令人难以置信的重复。让我们看看我们是否可以使用这种重复。让我们建立一个不等式表 - s 的值与最终结果：

s + (f+17) >= 0: 8
s + (f+17) + (f+15) >= 0: 7
s + (f+17) + (f+15) + (f+13) >= 0: 6
.
.
s + (f+17) + (f+15) + (f+13) + ... + (f+1) >= 0: 0

因此，每一行都测试 s + f 的某个倍数 + 某个常数是否大于 0。返回的值、常数和 f 的倍数看起来都相关。让我们尝试表达这种关系：

(s + ((9-n)*f) + (2*n)-1 >= 0)

让我们重新排列，所以 n 在一侧。

(s + (9*f) - (n*f) + (2*n)-1 >= 0)

(s + (9*f) +1 >= (n*f) - (2*n))

(s + (9*f) +1 >= n*(f - 2))

n <= ((s + (9*f) +1) / (f - 2)

现在，该函数具有针对不同输入的一系列返回值。事实上，我们对n0..8 范围内的值感兴趣：所提供的函数对于会产生的输入是未定义的n < 0（见上文）。序言确保我们永远不会看到会产生的输入n > 8。所以我们只能说

int_1024 sqcalc(int_1024 s,int_1024 f){
    f=f*20;
    s=s-81;
    s=s-(f*9);
    if(s>=0){
        return 9;
    }
    return (s + (9*f) +1) / (f - 2);
}

对于结果未定义的所有情况，行为应该与旧版本相同，不需要大量条件或循环。

在http://ideone.com/UzMZs上展示了准确性。

于 2012-06-08T16:33:24.563 回答
0

我尝试求解二次方程，它使函数对于较大的数字变慢。按照@user315052 的答案，我编写了这个代码。

    int_1024 sqcalc(int_1024 s,int_1024 f){
int k[] = { 0, 17, 32, 45, 56, 65, 72, 77, 80, 81 };
f=f*20;
s=((f*9)+81)-s;
int i=0;
while(s>k[i]){
s-=f;
i++;
}
return 9-i;
}

在这段代码中，我不是减去一个数字然后与零进行比较，而是直接将它与数字进行比较。到目前为止，这会产生最快的结果。虽然我可以进行二进制搜索....

于 2012-06-10T16:50:52.823 回答
0

根据 OP 的评论，该函数试图找到满足不等式的所有值： 

N * ((20 * F) + N) <= S

对于所有 N，给定一个 F 和 S。

使用代数，可以得出： 

1) N^2 + 20Fn - S <= 0  (where N^2 is N*N or sqr(N))

OP 应该对 F 和 N 使用一些常数并以代数方式求解（sp？）或在网上搜索“C++ 查找根二次方程”。

选择一个功能，然后分析功能并在必要时进行优化。

于 2012-06-09T18:52:21.740 回答