java固定算法的性能时间

Question

下面的程序是用来计算数字的完美幂的

最终的结果是让Perfect Power在0.01秒的执行时间内完成所有测试用例

目前，10000的程序最终结果时间性能约为2+秒，1073741824的程序最终结果时间性能需要更长的时间。需要帮助将所有完美电源的时间降低到0.01秒或更少

以下是程序代码：

    /**
  
 *
 * A utlity class to calculate the perfect power of an integer
 */
public class PerfectPower {
    public static void main(String[] args) {
        new TimeExec(new Runnable() {
            public void run() {
                   System.out.println("Perfect Power of 17 is " + getPerfectPower(17));
            }
        }, "Get Perfect Power of 17", System.out).start();
        
        new TimeExec(new Runnable() {
            public void run() {
                   System.out.println("Perfect Power of 625 is " + getPerfectPower(625));
            }
        }, "Get Perfect Power of 625", System.out).start();
        
        new TimeExec(new Runnable() {
            public void run() {
                   System.out.println("Perfect Power of 1024 is " + getPerfectPower(1024));
            }
        }, "Get Perfect Power of 1024", System.out).start();
        
        new TimeExec(new Runnable() {
            public void run() {
                   System.out.println("Perfect Power of 10000 is " + getPerfectPower(10000));
            }
        }, "Get Perfect Power of 10000", System.out).start();
        
        new TimeExec(new Runnable() {
            public void run() {
                   System.out.println("Perfect Power of 1073741824 is " + getPerfectPower(1073741824));
            }
        }, "Get Perfect Power of 1073741824", System.out).start();  
    }

    /**
     * Get the perfect power for a number.
     * @param x number for which to calculate the perfect power.
     */
    public static int getPerfectPower(int x) {
        int largestP = 1;
           
        for (int b = 1; b < x; b++) {
        for (int p = 1; p < x; p++) {
           
                if (Math.pow(b,p) == x) {
                    largestP = p;
                }
           }           
        }
        
        return largestP;
    }

}

结束代码：

17的完美幂是1 TimeExec：获得17:0.001s的完美功率

625的完美幂为2 TimeExec:获得625:0.026s的完美功率

1024的完美幂是2 TimeExec:获得1024:0.052s的完美功率

10000的完美幂是2 TimeExec:获得10000:1.9秒的完美功率

需要此代码才能在.01s下打印 1073741824的完美幂为X TimeExec:获得：XX的完美功率。XXXs

Answer 1

首先，我们寻找参数中给定的完美幂数的最大指数。最大指数的最佳候选值是基为2，因此我们将从2开始循环，而不是1

其次，最小的指数是2（而不是回退1），因此最大基，其中base²=x，是maxBase=sqrt（x），因此我们将在该基值处结束循环

我们的目标是公式b^p=x，我们从参数中得到x，从循环中得到b，因此我们可以使用p=log（x）/log（b）计算p，然后检查这是否是一个整数

避免舍入错误的最佳方法是舍入到最接近的整数，然后检查b^p==x

其代码为：

public static int getPerfectPower(int x) {
    double maxBase = Math.sqrt(x);
    for (int b = 2; b <= maxBase; b++) {
        long p = Math.round(Math.log(x) / Math.log(b));
        if (Math.pow(b, p) == x)
            return (int) p;
    }
    return 1;
}

测试

public static void main(String[] args) {
    test(17);
    test(625);
    test(1024);
    test(10000);
    test(1073741824);
}
static void test(int x) {
    long start = System.nanoTime();
    int exponent = getPerfectPower(x);
    long end = System.nanoTime();
    System.out.printf("Perfect Power of %d is %d (%.9fs)%n",
                      x, exponent, (end - start) / 1e9);
}

输出

Perfect Power of 17 is 1 (0.000022500s)
Perfect Power of 625 is 4 (0.000003700s)
Perfect Power of 1024 is 10 (0.000003700s)
Perfect Power of 10000 is 4 (0.000003500s)
Perfect Power of 1073741824 is 30 (0.000001700s)

---

或者，我们可以循环指数而不是基，将时间复杂度从O（sqrt（x））更改为O（log（x）），这在技术上更快，但此处的值太小，无法注意到任何性能差异

无需进一步解释，代码如下：

public static int getPerfectPower(int x) {
    // x = b ^ p   <==>   p = log(x) / log(b)   <==>   b = exp(log(x) / p)
    double logX = Math.log(x);
    int maxExp = (int) Math.round(logX / Math.log(2));
    for (int p = maxExp; p > 1; p ) {
        long b = Math.round(Math.exp(logX / p));
        if (Math.pow(b, p) == x)
            return p;
    }
    return 1;
}

Answer 2

您使用嵌套的从1到x的两个循环测试了太多的案例

对于指数p，您可以将最可能的基数计算为b0=floor(pow(x,1.0/p))。如果您想保持谨慎，那么测试b=b0-1, b0, b0+1的幂是否等于x，但是b=b0-1的情况永远不会有效

然后，当达到b0=1时，可以停止增加指数