如何有效地将数字中的每个数字相乘

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;
}

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

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秒内完成所有十亿个数字

Answer 2

如果您可以存储所有数字的每个操作的结果..那么您可以使用Memoization.这样你只需要计算1位数.

int prodOf(int num){
   // can be optimized to store 1/10 of the numbers, since the last digit will always be processed
   static std::vector<int> memo(<max number of iterations>, -1); 
   if(num == 0) return 0;

   if(memo[num] != -1 )return memo[num];

   int prod = (num%10)  * prodOf(num/10);

   memo[num] = prod;

   return prod;
}