-1

In leetcode, 1388. Pizza With 3n Slices

there is my code


public static void maxSizeSlicesTest(DailyQuestion dq){
        System.out.println(dq.maxSizeSlices(new int[]{1,2,3,4,5,6}));
        System.out.println(dq.maxSizeSlices(new int[]{8,9,8,6,1,1}));
        System.out.println(dq.maxSizeSlices(StringUtils.randomIntArray(498, 1, 1000)));
        compareMaxSizeSlices(dq);
    }

    private static void compareMaxSizeSlices(DailyQuestion dq){
        // 执行时长测试
        long totalCostA = 0, costA, totalCostB=0, costB, lessA=0, lessB=0, same=0;
        for (int i=0; i<10000; i++){
            int[] slices = StringUtils.randomIntArray(3 + 3 * random.nextInt(187), 1, 1000);
            System.gc();
            costA = System.currentTimeMillis();
            dq.maxSizeSlicesOther(slices);
            costA = System.currentTimeMillis() - costA;
            System.gc();
            costB = System.currentTimeMillis();
            dq.maxSizeSlices(slices);
            costB = System.currentTimeMillis() - costB;
            if (costA>costB){
                lessB++;
            }
            else if (costA<costB){
                lessA++;
            }
            else {
                same++;
            }
            totalCostB += costB;
            totalCostA += costA;
        }
        log.info("10000次,A耗时短{}次,B耗时短{}次,相同耗时{},A总耗时{},B总耗时{}", lessA, lessB, same, totalCostA, totalCostB);
    }

// this method is normal
    public int maxSizeSlices(int[] slices) {
        return Math.max(this.maxSizeSlices(slices, 0, slices.length-2), this.maxSizeSlices(slices, 1, slices.length-1));
//        return this.maxSizeSlicesOther(slices);
    }

//  this method is other
    public int maxSizeSlicesOther(int[] slices) {
        int len = slices.length, times = len/3;
        int[][][] dp = new int[len][times+1][2];
        int from = 0, to = len-2;
        // 节点初始化
        dp[1][1][0] = slices[from];
        dp[2][1][0] = Math.max(slices[from], slices[from+1]);
        dp[1][1][1] = slices[from+1];
        dp[2][1][1] = Math.max(slices[from+1], slices[from+2]);
        for (int i=3; i<=to-from+1; i++){
            for(int k=1; k<i&&k<=times; k++){
                dp[i][k][0] = Math.max(dp[i-1][k][0], dp[i-2][k-1][0] + slices[from-1+i]);
                dp[i][k][1] = Math.max(dp[i-1][k][1], dp[i-2][k-1][1] + slices[from+i]);
            }
        }
        return Math.max(dp[to-from+1][times][0], dp[to-from+1][times][1]);
    }

    private int maxSizeSlices(int[] slices, int from, int to){
        int len = slices.length, times = len/3;
        int[][] dp = new int[len][times+1];
        // 节点初始化
        dp[1][1] = slices[from];
        dp[2][1] = Math.max(slices[from], slices[from+1]);
        for (int i=3; i<=to-from+1; i++){
            for(int k=1; k<i&&k<=times; k++){
                dp[i][k] = Math.max(dp[i-1][k], dp[i-2][k-1] + slices[from-1+i]);
            }
        }
        return dp[to-from+1][times];
    }

// StringUtils
public static int[] randomIntArray(int length, int low, int high){
        if (length <= 0 ){
            return new int[0];
        }
        if (high < low){
            return new int[0];
        }
        int[] result = new int[length];
        int width = high - low;
        for (int i=0; i<length; i++){
            result[i] = random.nextInt(width) + low;
        }
        if (log.isDebugEnabled()){
            log.debug("randomIntArray生成数据结果{}", Arrays.stream(result)
                    .mapToObj(String::valueOf).collect(Collectors.joining(",")));
        }
        return result;
    }

run result: 10000次,A耗时短705次,B耗时短5300次,相同耗时3995,A总耗时7757,B总耗时1835

My question is that why other slow than normal. I think other just one cycles and the normal has two, so it should run more quick. But the result in leetcode is normal run fast. And I run local test, the result is same. Who can explain to me the reason for this?

this is the code link

yiChen
  • 1
  • 2
  • Please use only english in Stackoverflow: https://stackoverflow.com/help/non-english-questions – aled Aug 22 '23 at 14:53
  • See: [How do I write a correct micro-benchmark in Java?](https://stackoverflow.com/questions/504103/how-do-i-write-a-correct-micro-benchmark-in-java). – David Conrad Aug 22 '23 at 15:15
  • I have marked this as a duplicate of the benchmark question because the way you are measuring performance will produce outright lies and completely wrong results. – Louis Wasserman Aug 22 '23 at 15:20

0 Answers0