Блог пользователя mshcherba

Поведение двумерного массива в C++
Автор mshcherba, история, 8 лет назад, перевод, По-русски

Здесь приведены 2 решения одной задачи: 20274603, 20298628. Единственная разница между ними — это двумерный массив last. В первом случае было last[MAXN][MAXQ], а во втором — last[MAXQ][MAXN]. MAXN = 103 + 7, MAXQ = 105 + 7. Я итерировался только через то измерение, которое имеет размер MAXN. Первый код примерно в 5 раз медленнее. Кто-то может объяснить почему? Спасибо заранее.

  • Проголосовать: нравится
  • +1
  • Проголосовать: не нравится

»
8 лет назад, # |
  Проголосовать: нравится +12 Проголосовать: не нравится

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

→ Ответить
»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Автокомментарий: текст был переведен пользователем mshcherba (оригинальная версия, переведенная версия, сравнить).

→ Ответить
»
8 лет назад, # |
← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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.

→ Ответить
  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    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.

    → Ответить