mshcherba's blog

Behaviour of two-dimensional array in C++
By mshcherba, history, 8 years ago, In English

Here are 2 solutions of the same problem: 20274603, 20298628. The only difference between them is two-dimensional array last. In first case it was last[MAXN][MAXQ], and in the second one — last[MAXQ][MAXN]. MAXN = 103 + 7, MAXQ = 105 + 7. I iterated only over that dimension, which has size MAXN. The first code is about 5 times slower. Could anyone please explain why? Thanks in advance.

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

»
8 years ago, # |
  Vote: I like it +12 Vote: I do not like it

It's about cache-friendly code. You can read about it here.

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

    Got it finally! It depends on the order of how you run your for loops.

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

You would have known about it if you did codechef long contests. Many people got TLE just because of this and you can imagine how they felt once they knew about it after the contest.

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

    I was confused and I saw the previous codechef contests where this problem arised. Here you got AC by keeping first dimension size lower, while here you can see people complaining about how arr[n][logn] gave TLE while arr[logn][n] gave AC. Now I am really confused.

    → Reply