WolfBlue's blog

Why is it so slow?
By WolfBlue, history, 6 years ago, In English

After a long time of trying to solve this problem, I was excited to finally have a solution that seemed to work.

I quickly submitted the solution, but to my great surprise, I obtained a TLE. I quickly searched through the code for anything suspicious, but I could not find anything — it seems to be very clearly O(n^2), with n at most 5000... but it still takes far too long: running it on my computer it seemed to take more than 1 second for the loop where I simply initialize all the values to Infinity!

Does anybody know why it would take so long to do such a simple task as this? What am I missing here?

  • Vote: I like it
  • +12
  • Vote: I do not like it

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

try swap last dimension with first one.

Then you will have 2 * n * ( (n+3)/2 ) instead of n * ( (n + 3) / 2) * 2

In your case you have too many arrays, for Java is really important.

I didnt read code much, but if you can reduce the number of layers of dp, it will help. (Or write the same code on C++, it should pass TL :) )

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

    Interesting, I didn't realize that this would cause slowdown. I implemented your suggestion and then did an algorithm adjustment to half number of operations and managed to squeeze it in with 966 ms. (It still feels a bit slow, though) I suppose that, in general, it's best to have the largest dimension be the last one in an array, though I'm used to seeing the smallest one at the end for some reason. Thanks a lot for your help!

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

too many cache hits,try swapping dimensions

→ Reply