c++ - C++中的自数字

嘿，我和我的 friend 们试图击败彼此的运行时，以生成1到一百万之间的“Self Numbers”。我已经用C++编写了我的文章，但我仍在努力节省宝贵的时间。

这是我到目前为止的一切

#include <iostream>

using namespace std;

bool v[1000000];
int main(void) {
  long non_self = 0;
  for(long i = 1; i < 1000000; ++i) {
    if(!(v[i])) std::cout << i << '\n';
    non_self = i + (i%10) + (i/10)%10 + (i/100)%10 + (i/1000)%10 + (i/10000)%10 +(i/100000)%10;
    v[non_self] = 1;
  }
  std::cout << "1000000" << '\n';
  return 0;
}

该代码现在可以正常工作，我只想对其进行优化。
有小费吗？谢谢。

最佳答案

我构建了一个不需要任何模或除法运算的备用C解决方案:

#include <stdio.h>
#include <string.h>

int main(int argc, char *argv[]) {
   int v[1100000];
   int j1, j2, j3, j4, j5, j6, s, n=0;
   memset(v, 0, sizeof(v));
   for (j6=0; j6<10; j6++) {
      for (j5=0; j5<10; j5++) {
         for (j4=0; j4<10; j4++) {
            for (j3=0; j3<10; j3++) {
               for (j2=0; j2<10; j2++) {
                  for (j1=0; j1<10; j1++) {
                     s = j6 + j5 + j4 + j3 + j2 + j1;
                     v[n + s] = 1;
                     n++;
                  }
               }
            }
         }
      }
   }
   for (n=1; n<=1000000; n++) {
      if (!v[n]) printf("%6d\n", n);
   }
}

它生成97786个自编号，包括1和1000000。
随着输出，它需要

real        0m1.419s
user        0m0.060s
sys         0m0.152s

当我将输出重定向到/dev/null时，它需要

real     0m0.030s
user     0m0.024s
sys      0m0.004s

在我的3 GHz四核钻机上。

为了进行比较，您的版本会产生相同数量的数字，因此我认为我们都是正确的或同样是错误的。但您的版本不满意

real    0m0.064s
user    0m0.060s
sys     0m0.000s

在相同条件下，大约是原来的两倍。

那，或者您正在使用long的事实，这在我的机器上是不必要的。在这里，int达到20亿。也许您应该检查自己的INT_MAX？

更新

我有预感，分段计算总和可能会更好。这是我的新代码:

#include <stdio.h>
#include <string.h>

int main(int argc, char *argv[]) {
   char v[1100000];
   int j1, j2, j3, j4, j5, j6, s, n=0;
   int s1, s2, s3, s4, s5;
   memset(v, 0, sizeof(v));
   for (j6=0; j6<10; j6++) {
      for (j5=0; j5<10; j5++) {
         s5 = j6 + j5;
         for (j4=0; j4<10; j4++) {
            s4 = s5 + j4;
            for (j3=0; j3<10; j3++) {
               s3 = s4 + j3;
               for (j2=0; j2<10; j2++) {
                  s2 = s3 + j2;
                  for (j1=0; j1<10; j1++) {
                     v[s2 + j1 + n++] = 1;
                  }
               }
            }
         }
      }
   }
   for (n=1; n<=1000000; n++) {
      if (!v[n]) printf("%d\n", n);
   }
}

...以及您所知道的，这使顶部循环的时间从12 ms减少到4 ms。也许是8点，我的时钟似乎在那儿有些不安。

状况，摘要

实际找到1M的自我编号大约需要4毫秒，而我在衡量任何进一步的改进时遇到了麻烦。另一方面，只要输出到控制台，尽管有尽最大努力来利用缓冲，它仍将持续约1.4秒。 I/O时间大大缩短了计算时间，以至于任何进一步的优化实际上都是徒劳的。因此，尽管受到更多评论的启发，但我还是决定独自一人。

引用的所有时间均在我的(相当快的)计算机上，并且仅用于相互比较。你的旅费可能会改变。