0

After I submitted my solution to the Maximum Subarray problem on leetcode, it said my runtime was 1ms (beating ~66% submissions), then I made a couple of changes and resubmitted. This time, the runtime was 0ms (beating ~100%). I do not quite understand what contributed to the reduction in time. Here the are two versions.

Original:

public int maxSubArray(int[] nums) {
        if (nums == null) return 0;
        if (nums.length == 1) return nums[0];

        int current_max = nums[0];
        int cur = 1;
        int max = current_max;

        while (cur < nums.length) {
            current_max = Math.max(nums[cur] + current_max, nums[cur]);
            if (current_max > max) {
                max = current_max;
            }
            cur++;
        }
        return max;
    }

Updated:

public int maxSubArray(int[] nums) {
        if (nums == null) return 0;
        int l = nums.length;
        if (l == 1) return nums[0];

        int current_max = nums[0];
        int max = current_max;

        for (int i = 1; i < l; i++) {
            current_max = Math.max(nums[i] + current_max, nums[i]);
            if (current_max > max) {
                max = current_max;
            }
        }

        return max;
    }

The only two changes I did, were

  1. Changing the while loop to a for loop - Apparently there is no difference ref
  2. Store the length in a separate variable - Since Array does not compute the length and array.length is only fetching from an internal variable, I do not see any difference here either.

[EDIT]

I agree. leetcode's performance is not 100% accurate. Funny thing, I submitted my updated code again the other day, and suddenly now it's 0ms.

Kaushik Evani
  • 1,154
  • 9
  • 17
  • 7
    Leetcode doesn't give accurate answers when it comes to performance. If you want to reason about performance write a JMH benchmark that you run on your own hardware. – Karol Dowbecki May 28 '20 at 11:31
  • 2
    Seeing that something took 0ms to complete should already trigger your attention - there is no way that any operation happens instantly. – Amongalen May 28 '20 at 11:40
  • By 0ms, I assumed it would have been in some micro seconds (< 1000 microsec) – Kaushik Evani May 28 '20 at 11:43
  • 1
    You may want to check out [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) – akuzminykh Jun 01 '20 at 10:16

1 Answers1

0

First. Every time you run the same code, time consumption is not completely equals

Second. LeetCode just give you an approximate consumption, MAYBE < 1ms will return 0ms

If you want more accurate time to consider test it with jmh

https://openjdk.java.net/projects/code-tools/jmh/

https://hg.openjdk.java.net/code-tools/jmh/file/tip/jmh-samples/src/main/java/org/openjdk/jmh/samples/

Hope this may help

update

if you want compare difference between the two method just put them in one class and 

javac filename.java

then

javap -c classname

you will get bytecode of these two methods, these byte codes are what real executed in jvm

reference :

https://docs.oracle.com/javase/specs/jvms/se8/html/jvms-6.html#jvms-6.5.invokespecial]

Wangbo
  • 325
  • 7
  • 18