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

Case of the Curious macro
Автор arasmus, история, 7 лет назад, По-английски

35685511 <- This has a macro min() at line 12 35686050 <- This does not In the first case...the code at line 44 && 45 (query() function) runs twice....this gave a TLE ... but why? In the second case when the macro is removed...no TLE happens!

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

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

Imagine it like a binary tree. Each call to query function generates 2 further recursive calls. The height of tree will be O(logN). So, the complexity for query function will be O(2logN) = O(N). Thus, TLE.

In other code, the binary tree becomes a path of length O(logN) due to single recursive call which reduces complexity of query function to O(logN).

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

    ...but why is the query function is being called twice because of the macro? From what i can figure.... the macro gets replaced at compile time into actual code..and hence the query function must run just once

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

      ans = min(ans, query())changes to ans = ((ans>query())?query():ans). That's why it is called twice, once for comparison and then for assignment.

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

      C/C++ macros are dumb text replacements so expression can be evaluated multiple times if it gets used multiple time. This is one of reasons why use of macros is discouraged in most professional c++ style guide (conditional compiling is an exception). I would also suggest avoiding them to beginners. Saving a few symbols might save some seconds for top participants but will not help beginners become red. The time debugging unexpected macro behaviour would be better spent getting better at algorithms and data structures. At least half the time macro can be replaced with different c++ feature that achieves the same but better.

      → Ответить