找到1到10,000,000之间不丑的数字

Question

当我试图找出不丑的数字时,我遇到了一些问题.丑陋的数字是唯一的素数因子是2,3或5的数字.那么这个数字不是很难看？我试着找出1到100,000,000之间不难看的数字.我的程序可以解决问题,但似乎有点慢.我怎么能让它更快？这是代码:

#include <iostream>
#include <queue>
using namespace std;
typedef pair<unsigned long,int> node_type;
main()
{
    //generates 1500 ugly numbers into result[];
    unsigned long result[1500];
    priority_queue<node_type,vector<node_type>,greater<node_type> > Q;
    Q.push(node_type(1,2));
    for(int i=0;i<1500;i++)
    {
        node_type node = Q.top();
        Q.pop();
    switch(node.second)
    {
        case 2:Q.push(make_pair(node.first*2,2));
        case 3:Q.push(make_pair(node.first*3,3));
        case 5:Q.push(make_pair(node.first*5,5)); 
    }
    result[i]=node.first;
}
/*****************************************************
//Here is the approach I used:
//The initial value of the integer k is 1;
//and will increase by 1 every time 
//k will be checked if it's a ugly number,if not increase by 1,keep doing
//this till k is not a ugly number,then count how much ugly number(we may 
//call it n) is less the the
//current value of k.The result of (k-n) is the order number of this (k)?not ugly
//for example:the 1st not ugly number is 7.
// there are 6 ugly number less than 7,which are 1 2 3 4 5 6,
// k=1-->k==2-->.....k=7, k-n=7-6=1,so 7 is the 1st not ugly number
***************************************************************/
int T;  // The amount of cases
cin>>T;
while(T--)
{
    int n;
    int k=0,i=0,count=0;
    cin>>n;

    while(n)
    {
        if((k+1)==result[i]) {k++;i++;count++;}
        else 
        {
            k++;
            if(k-count==n) {cout<<k<<endl;break;}
        }
    }
}}

最大的问题是它似乎不够快!你能告诉我如何让它更快吗？还是有其他方法可以解决这个问题？

Answer 1

好的,我会咬人的.根据这个定义,测试一个数字是否丑陋,在计算上实际上相当简单.蛮力测试1亿个数字

#include <iostream>

bool is_ugly(unsigned n) {
  while(n % 5 == 0) n /= 5;
  while(n % 3 == 0) n /= 3;
  while(n % 2 == 0) n /= 2;

  return n == 1;
}

int main() {
  unsigned counter = 0;
  for(unsigned i = 1; i <= 100000000; ++i) {
    if(!is_ugly(i)) {
      ++counter;
    }
  }

  std::cout << counter << std::endl;
}

在我的基准测试^1中只需要半秒钟,这是非常可行的.当然,打印它们需要更长的时间,因为有99998895个非丑陋的数字低于100000000,你的终端必须全部渲染.即使重定向到/dev/null(从等式中取出渲染),打印也需要6秒(比检查长10倍),使用libstdc ++和gcc 4.9 -O2.如果你要生成所有非丑陋的数字,这不是那么容易被击败,因为瓶颈不是你可以摆脱的东西.

另一方面,如果你的目标是生成低于阈值的所有丑陋数字(或计算非丑陋数字,这与计算丑陋数字和从阈值中减去数字相同)测试所有非丑陋数字和丑陋的数字远非最佳.更好的方法是生成丑陋的数字,因为它们很少.使用递归最容易做到这一点:

#include <iostream>
#include <set>      // could also use an unordered_set, except that it turns
                    // out to be a pessimization

void generate_uglies(unsigned n, std::set<unsigned> &num, unsigned threshold) {
  // Abort recursion if we break the upper limit or find a number
  // that was already tested
  if(n <= threshold && num.find(n) == num.end()) {
    // Remember this ugly number
    num.insert(n);

    // Since n is an ugly number, these three are also ugly numbers.
    generate_uglies(n * 2, num, threshold);
    generate_uglies(n * 3, num, threshold);
    generate_uglies(n * 5, num, threshold);
  }
}

int main() {
  std::set<unsigned> num;

  generate_uglies(1, num, 100000000);

  std::cout << num.size() << std::endl;
}

这回报了,好吧......

$ time ./a.out 
1105

real    0m0.001s
user    0m0.000s
sys     0m0.000s

你可以使用它,希望这num.find(n) == num.end()是一个比非丑陋更快的测试is_ugly(n)(使用is_ugly之前的函数),但在我的基准测试中差异可以忽略不计,使用a std::unordered_set实际上慢了2-3倍.

附录:什么可以节省一些时间是产生难看的数字成std::vector<bool>与像因此100万台:

// num is to have the wanted size in advance and be full of false
void generate_uglies(unsigned n, std::vector<bool> &num) {
  if(n < num.size() && !num[n]) {
    num[n] = true;
    generate_uglies(n * 2, num);
    generate_uglies(n * 3, num);
    generate_uglies(n * 5, num);
  }
}

并在以后测试非丑陋的数字!num[i].该!num[i]测试比快得多is_ugly的功能(以下,平均亿值由〜5倍)¹.如果您打算打印它们并不重要,原因如上所述,但在不同的情况下它可能会产生明显的差异.请注意,此表需要12.5 MB RAM.

¹您的里程会有所不同,因为您的机器不是我的.我正在使用一个1.5岁的i7.