prabal1815's blog

Difference in execution time of two almost similar submissions in Java8.
By prabal1815, history, 8 years ago, In English

Yesterday I was doing a question 86D - Powerful array.

I implemented Mo's algorithm and got TLE in java. Then after some modifications in got accepted in 4740 ms (27581138). I started seeing the solution of others users to find ways to optimize my code so that it gets accepted in less time. I came across this solution (14855687) which passed in 2306 ms (almost half). I tried my best to do exactly the same but still my code runs in almost the same time as earlier. This time it was around 4802 ms (27581630).

Can anybody tell me what exactly is the reason behind this and what should I do to pass my submission in less time?

Thanks in advance!

  • Vote: I like it
  • 0
  • Vote: I do not like it

Comments Comments (6)
| Write comment?
»
8 years ago, # |
  Vote: I like it +6 Vote: I do not like it

It's because you're doing two division in every compare (for sorting queries I guess), but that red guy doesn't!

→ Reply
  • »
    »
    8 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    I didn't understand that. I calculated the block number whenever the compare function is called whereas the red guy has precalculated it. All of this happens in O(1) how does it effect the performance of the compare function?

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      division is fast, but it's relatively slow compared to sum or compare. Let's say it's 4x slower than compare, hence in a compare you are 4x (division) + 4x (division) + 1x (compare) = 9x slower than simple compare which in total gives you 9*nlgn time for sorting the array. Why don't you test it?

      → Reply
»
8 years ago, # |
  Vote: I like it +13 Vote: I do not like it

I tested your code and found that functions "add" and "remove" are bottlenecks.

How about if you change arr,count's type from long[] to int[]?

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    This did help alot,the submission time now was 3710ms 27630406. but still its much more and can you also please explain how does converting an array from long to int decreases the time by 1 sec?

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I don't know this is accurate explanation. The code calls "add" and "remove" about 90M times, then "count[]" is also accessed about 90M times. When the array is accessed, some contiguous units of array are loaded together. These work as a cache. Changing from long[] to int[] makes the array improving accessibility.

      → Reply