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

Автор Freedom, 9 лет назад, По-английски

I try to solve this problem 459C - Pashmak and Buses

It has Time limit exceeded on test 9

I printed the result to screen, it took nearly 25s:

But when I print to a file, run time is 94 ms:

Can you explain the different between two methods?

Thanks.

P/s: same code

9203418

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

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

I don't know really why, but Windows console output is really slow. Maybe it's even slowed down intentionally

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

Rendering a character on screen is just a lot slower operation than writing a byte to a file or a pipe. It involves a lot more computations.

Also this is unrelated to your TLE on the server, since the server doesn't render your output in a console (your program's standard input/output is redirected to files or pipes).

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

    Thank andreyv, but I don't understand why it took more than 1s. Can you explain me more clearly.

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

      Consider what happens in both cases:

      1. When you write data to file or pipe, your program just appends bytes to an internal buffer (typically 4KB), and when the buffer is full, performs one system call to transfer all data to a file or another program.
      2. When you write data to the console, this happens:
      • A write system call is done each time your program outputs a newline, which is far more often than once per 4KB.
      • Control is transferred to the console process (can add additional costs).
      • The console process goes through each single byte, finds its corresponding character in the selected font, and then draws this character on screen. Also it has to manage scrolling.
      • If your program is printing data too fast, the pipe buffer is filled and your program is suspended until the console process finishes drawing all characters.

      Also in general the Windows console is horribly slow.