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

5x optimization???
Автор Tutis, история, 5 лет назад, По-английски

I was solving this problem and after I solved it by myself I decided to implement editorial's solution. Strangely my first submission was really slow 55982450, but after changing the order of dimensions it got 5x faster 55999256.

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

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

There was a blog before where that happened before, and the reason was because of cache. When storing a multi-dimensional array in a more cache-friendly order, you will get better performance.

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

    I've noticed this specifically for sparse tables. Having st[j][i] store the 2^j-th ancestor of i is an order of magnitude faster than st[i][j].

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

      Nice one, I've never thought about this before. It makes sense. I will consider this next time I implement sparse table.

      → Ответить