math - 如何有效地乘以数字中的每个数字

Question

我想将数字中的每个数字相乘。

例如

515 would become 25(i.e 5*1*5)
10 would become 0(i.e 1*0)
111111 would become 1(i.e 1*1*1*1*1*1)

我用这段代码来做到这一点

public static int evalulate(int no)
{
    if(no==0)return 0;
    int temp=1;

    do
    {
        temp=(no%10)*temp;
        no=no/10;
    }while(no>0);

    return temp;
}

问题是我想评估大约 亿 像这样的数字

for(int i=0;i<1000000000;i++)evaluate(i);

这大约需要 146 我的处理器上的秒数。我想在 内评估它一些 秒。

那么，是否可以使用一些 shift 来优化此代码？ , and , or运算符，以便我可以减少评估时间 不使用多线程或并行化它

谢谢

Answer 1

首先，弄清楚您可以在内存中存储多少个数字。在本例中，假设您可以存储 999 个号码。

您的第一步将是预先计算从 0 到 999 的所有数字的数字乘积，并将其存储在内存中。所以，你会有一个数组:

  multLookup = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 
                0, 1, 2, 3, 4, 5, 6, 7, 8, 9,
                0, 2, 4, 6, 8, 10, 12, 14, 16, 18,
                0, 3, 6, 9, 12, 15, 18, 21, 24, 27,
                0, 4, 8, 12, 16, 20, 24, 28, 32, 36,
                ...]

现在，你要把你的号码分成一堆 3 位数字。例如，如果您的号码是 1739203423 ，你可以把它分解成 1 , 739 , 203 , 和 423 .您可以在 multLookup 中查找这些内容中的每一个。数组，并将结果相乘，如下所示:

  solution = multLookup[1] * multLookup[739] * multLookup[203] * multLookup[423];

使用这种方法，您的计算速度将提高 3 倍(因为我们选择了 999 个项目存储在内存中)。要将其速度提高 5，请将 99999 个数字存储在内存中并执行相同的步骤。在您的情况下，将速度提高 5 意味着您将在 中找到您的解决方案。 29.2 秒 .

注意:增益与您在内存中存储的数字数量并不完全线性。请参阅此答案下评论中 jogojapan 的推理，了解原因。

如果您对数字显示的顺序或数字范围(假设您的输入仅在 [0, 10000] 的范围内)了解更多，则可以使该算法更智能。

在您的示例中，您使用 for 循环从 0 到 1000000000 进行迭代。在这种情况下，这种方法将非常有效，因为内存不会非常频繁地出现页面错误并且缓存未命中的情况会更少。

可是等等! 您可以使其更快(对于您的特定 for 循环迭代示例)!!你问怎么样？缓存!假设您正在查看 10 位数字。

假设您从 8934236000 开始.根据内存解决方案中的 999 位数字，您可以将其分解为 8 , 934 , 236 , 和 000 .然后你会乘以:

solution = multLookup[8] * multLookup[934] * multLookup[236] * multLookup[0];

接下来，您将使用 8934236001 ，将其分解为 8 , 934 , 236 , 和 001 ，并乘以:

solution = multLookup[8] * multLookup[934] * multLookup[236] * multLookup[1];

依此类推……但我们注意到，对于接下来的 997 次迭代，前三个查找是相同的!所以，我们缓存它。

cache = multLookup[8] * multLookup[934] * multLookup[236];

然后我们使用缓存:

for (int i = 0; i < 1000; i++) {
    solution = cache * i;
}

就像那样，我们几乎将时间减少了 4 倍。所以你把你拥有的大约 29.2 秒的解决方案除以 4 以遍历 中的所有十亿数字。 ~7.3 秒