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?