0

I recently was solving a problem in leetcode.

My first submission -

class Solution {
    public int knightDialer(int n) {
        int[] prev_dp = new int[10];
        int[] curr_dp = new int[10];
        int mod = 1000000007;
        List<List<Integer>> adjList = new ArrayList<>();
        adjList.add(new ArrayList<>(Arrays.asList(4,6)));
        adjList.add(new ArrayList<>(Arrays.asList(6,8)));
        adjList.add(new ArrayList<>(Arrays.asList(7,9)));
        adjList.add(new ArrayList<>(Arrays.asList(4,8)));
        adjList.add(new ArrayList<>(Arrays.asList(0,3,9)));
        adjList.add(new ArrayList<>(Arrays.asList()));
        adjList.add(new ArrayList<>(Arrays.asList(0,1,7)));
        adjList.add(new ArrayList<>(Arrays.asList(2,6)));
        adjList.add(new ArrayList<>(Arrays.asList(1,3)));
        adjList.add(new ArrayList<>(Arrays.asList(2,4)));
        if(n==0) return 0;
        // for 1st step;
        for(int i = 0; i<10;i++){
            curr_dp[i] = 1;
        }
        // prev_dp = curr_dp.clone();
        System.arraycopy(curr_dp,0, prev_dp,0,10);

        
        for(int j = 2; j<=n;j++){
            for(int i = 0; i<10;i++){
                int curr_sum = 0;
                for(int adjNode: adjList.get(i)){
                   curr_sum+=prev_dp[adjNode]; 
                   curr_sum = curr_sum%mod; 
                }
                curr_dp[i] = curr_sum;
            }
            // prev_dp = curr_dp.clone();
            System.arraycopy(curr_dp,0, prev_dp,0,10);
        }
        
        int ans = 0;
        for(int i = 0; i<10;i++){
            ans+=curr_dp[i];
            ans = ans%mod;
        }
        return ans;
    }
}

My second submission -

class Solution {
    public int knightDialer(int n) {
        int[] prev_dp = new int[10];
        int[] curr_dp = new int[10];
        int mod = 1000000007;
        List<List<Integer>> adjList = new ArrayList<>();
        adjList.add(new ArrayList<>(Arrays.asList(4,6)));
        adjList.add(new ArrayList<>(Arrays.asList(6,8)));
        adjList.add(new ArrayList<>(Arrays.asList(7,9)));
        adjList.add(new ArrayList<>(Arrays.asList(4,8)));
        adjList.add(new ArrayList<>(Arrays.asList(0,3,9)));
        adjList.add(new ArrayList<>(Arrays.asList()));
        adjList.add(new ArrayList<>(Arrays.asList(0,1,7)));
        adjList.add(new ArrayList<>(Arrays.asList(2,6)));
        adjList.add(new ArrayList<>(Arrays.asList(1,3)));
        adjList.add(new ArrayList<>(Arrays.asList(2,4)));
        if(n==0) return 0;
        // for 1st step;
        for(int i = 0; i<10;i++){
            curr_dp[i] = 1;
        }
        // prev_dp = curr_dp.clone();
        // System.arraycopy(curr_dp,0, prev_dp,0,10);
        for(int i = 0; i<10;i++){
            prev_dp[i] = curr_dp[i];
        }
        
        for(int j = 2; j<=n;j++){
            for(int i = 0; i<10;i++){
                int curr_sum = 0;
                for(int adjNode: adjList.get(i)){
                   curr_sum+=prev_dp[adjNode]; 
                   curr_sum = curr_sum%mod; 
                }
                curr_dp[i] = curr_sum;
            }
            // prev_dp = curr_dp.clone();
            // System.arraycopy(curr_dp,0, prev_dp,0,10);
            for(int l = 0; l<10;l++){
                prev_dp[l] = curr_dp[l];
            }
        }
        
        int ans = 0;
        for(int i = 0; i<10;i++){
            ans+=curr_dp[i];
            ans = ans%mod;
        }
        return ans;
    }
}

First submission is considerably faster(~3 times) and consume very less memory(~1/4) from the second submission. Please ignore timestamp, first submission took 70 ms and second submission took 203 ms

My questions are -

  1. Why clone and system.arraycopy are slower than copying elements with loop?
  2. Why clone and system.arraycopy take this much extra memory than copying elements with loop?
Aditya Maheshwari
  • 29
  • 1
  • 8
  • I can’t reproduce. I called `knightDialer(10_000)`. It took 27.5 ms for your first solution and 26.9 ms for the second. – Ole V.V. Oct 05 '21 at 23:55
  • 2
    Does this answer your question? [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) – Ole V.V. Oct 05 '21 at 23:56
  • @OleV.V. I think you need to run all the test cases to reproduce this. Can you try to reproduce this on leetcode? Your second link does not answer this as I want to understand why this is happening. But thanks for your suggestions. – Aditya Maheshwari Oct 06 '21 at 11:08
  • I think that what my link indirectly tells us is that this could very well be due to random variations on leetcode (and no, I am not setting up an account there in order to try your code there). – Ole V.V. Oct 06 '21 at 12:17
  • 1
    @OleV.V. I tried to run both versions again on leetcode and you were right about random variations part. Now both versions are running in nearly same amount of time and memory. – Aditya Maheshwari Oct 06 '21 at 23:35
  • Sure, I thought you might want to submit an answer. I undeleted my answer now. – Aditya Maheshwari Oct 07 '21 at 13:27

1 Answers1

1

As mentioned in the comments it was due to some variations on the judging platform. System.arraycopy and copying arrays by loop have nearly the same complexity. I verified it by running both versions multiple times.

enter image description here

Aditya Maheshwari
  • 29
  • 1
  • 8