自己的数字在c ++ [英] Self numbers in c++

问题描述

嘿，我的朋友和我都试图击败对方的运行时间，在1和a之间生成自己的号码百万。我已经写了我的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<< '\\\
'; 
 non_self = i +（i％10）+（i / 10）％10 +（i / 100）％10 +（i / 1000）％10 + ）％10; 
 v [non_self] = 1; 
} 
 std :: cout<< 1000000<< '\\\
'; 
 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））; （j5 = 0; j5 <10; j5 ++）{
（j4 = 0; j4 <10; j4 ++））的
 {
 for（j3 = 0; j3 <10; j3 ++）{
 for（j2 = 0; j2< 10; j2 ++）{
 for（j1 = 0; j1< 10; ）{
s = j6 + j5 + j4 + j3 + j2 + j1; 
 v [n + s] = 1; 
 n ++; 
} 
} 
} 
} 
} 
} 
 for（n = 1; n <= 1000000; n ++）{
 if（！v [n]）printf（％6d\\\
，n）; 
} 
} 
  

它会生成97786个自己的数字，包括1和1000000。 br>
输出时需要

  real 0m1.419s 
用户0m0.060s 
 sys 0m0.152s 
  

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

  real 0m0.030s 
用户0m0.024s 
 sys 0m0.004s 
  
 
 
 
为了比较，您的版本产生相同的数字的数量，所以我假设我们既正确也是同样错误;但你的版本嚼了
  real 0m0.064s 
用户0m0.060s 
 sys 0m0.000s 
  
在相同的条件下，或大约2倍。
 
 
 
这或者你使用 long 的事实，这在我的机器上是不必要的。这里， int 增加到20亿。也许你应该检查 INT_MAX 吗？
 
 
 
 更新 
 $ b 
我有一个希望，它可能会更好地计算总和分段。这是我的新代码：
  #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）; 
} 
} 
  
 ...将顶环的时间从12ms降低到4ms。 
 
 
 
  
  
 
 $ b 
自我数字高达1M的实际发现现在大约需要4ms，我在测量任何进一步的改进时遇到麻烦。另一方面，只要输出到控制台，它将继续花费约1.4秒，尽我最大的努力来利用缓冲。 I / O时间这么大幅度地缩短计算时间，任何进一步的优化将基本上是徒劳的。 
 
 
 
 所有的时间都在我的（很快）的机器上，并且是为了仅比较目的。您的里程可能会有所不同。 
 
Hey, my friends and I are trying to beat each other's runtimes for generating "Self Numbers" between 1 and a million.  I've written mine in c++ and I'm still trying to shave off precious time.

Here's what I have so far,
#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;
}
The code works fine now, I just want to optimize it.
Any tips? Thanks.
解决方案
I built an alternate C solution that doesn't require any modulo or division operations:
#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);
   }
}
It generates 97786 self numbers including 1 and 1000000.

With output, it takes
real        0m1.419s
user        0m0.060s
sys         0m0.152s
When I redirect output to /dev/null, it takes
real     0m0.030s
user     0m0.024s
sys      0m0.004s
on my 3 Ghz quad core rig.

For comparison, your version produces the same number of numbers, so I assume we're either both correct or equally wrong; but your version chews up
real    0m0.064s
user    0m0.060s
sys     0m0.000s
under the same conditions, or about 2x as much.

That, or the fact that you're using longs, which is unnecessary on my machine. Here, int goes up to 2 billion. Maybe you should check INT_MAX on yours?

Update

I had a hunch that it may be better to calculate the sum piecewise. Here's my new code:
#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);
   }
}
...and what do you know, that brought down the time for the top loop from 12 ms to 4 ms. Or maybe 8, my clock seems to be getting a bit jittery way down there.

State of affairs, Summary

The actual finding of self numbers up to 1M is now taking roughly 4 ms, and I'm having trouble measuring any further improvements. On the other hand, as long as output is to the console, it will continue to take about 1.4 seconds, my best efforts to leverage buffering notwithstanding. The I/O time so drastically dwarfs computation time that any further optimization would be essentially futile. Thus, although inspired by further comments, I've decided to leave well enough alone.

All times cited are on my (pretty fast) machine and are for comparison purposes with each other only. Your mileage may vary.

                        
这篇关于自己的数字在c ++的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！