4

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

例如

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运算符优化此代码，以便我可以在不使用多个线程或并行化的情况下减少评估时间

谢谢

4

3 回答 3

8

首先，弄清楚你可以在内存中存储多少个数字。对于此示例，假设您可以存储 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 seconds 内达到您的解决方案。

注意：增益与您在内存中存储的数字数量并不完全呈线性关系。请参阅此答案下评论中的 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 秒内遍历所有十亿个数字

于 2013-06-28T05:19:56.660 回答
6

如果您可以存储所有数字的每个操作的结果..那么您可以使用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;
}
于 2013-06-28T04:58:49.837 回答
1

我做了一些测试，在我的 PC（至强 3.2GHz）上使用简单的 C/C++ 代码，

最后没有 = i = 999999999 ==> 387420489 nb sec 23

#include "stdafx.h"
#include <chrono>
#include <iostream>

#undef _TRACE_

inline int evaluate(int no)
{
#ifdef _TRACE_
    std::cout << no;
#endif

    if(no==0)return 0;
    int temp=1;

    do
    {
        temp=(no%10)*temp;
        no=no/10;
    }while(no>0);
#ifdef _TRACE_
    std::cout << " => " <<  temp << std::endl;
#endif // _TRACE_
    return temp;
}

int _tmain(int argc, _TCHAR* argv[])
{
    std::chrono::time_point<std::chrono::system_clock> start(std::chrono::system_clock::now());
    int last = 0;
    int i = 0;
    for(/*int i = 0*/;i<1000000000;++i) {
        last = evaluate(i);
    }
    std::cout << "last no = i = " << (i-1) << " ==> " << last << std::endl;
    std::chrono::time_point<std::chrono::system_clock> end(std::chrono::system_clock::now());
    std::cout << "nb sec " << std::chrono::duration_cast<std::chrono::seconds>(end - start).count() << std::endl;

    return 0;
}

我还使用 openMP 测试了多线程上的循环拆分，结果为 0 秒，所以我想说，如果您考虑使用真正高效语言的性能问题，它会很有用。

pragma omp parallel for 
for(int i = 0;i<1000000000;++i) {
     /*last[threadID][i] = */evaluate(i);
}
于 2013-06-28T05:10:58.873 回答