nhannguyen95's blog

Printing string through ostringstream is faster than printing directly string ?
By nhannguyen95, history, 8 years ago, In English

Let's take a look at my 2 submissions for problem 681C

20333485 — TLE, don't use ostringstream

20333517 — AC, use ostringstream

Briefly, the answer of the problem is a string has 1e6 lines, each line has maximum 20 characters.

In the first submission, I stored the answer in string res, then I sum "res = res + line". Finally I printed "cout << res" and got TLE

But in the second submission, I stored the answer in sout object ( an ostringstream), sum "sout << line", and printed "cout << sout.str()" and got AC ( even 4 times faster than the first submission)

I don't understand the reason behind this. Anyone could explain it ?

Thank you in advance

  • Vote: I like it
  • 0
  • Vote: I do not like it

Comments Comments (3)
| Write comment?
»
8 years ago, # |
  Vote: I like it +9 Vote: I do not like it

In the code of the first submission, try changing res = res + line by res += line.

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

    And to make it even faster, add

    res.reserve(21000005);

    in the beginning.

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

As olenihc pointed out, res = res + line works way slower than res += line.

The reason behind this is that when you are trying to assign res + line value to res, this takes O(N + M) time where N is length of res and M is length of line.

In total these operations might take O(Q^2 * L) time (where L is length of line in your case and Q is how many times did you call this operator)

This is actually pretty much, you can see 20342784 this submission, where I'm adding "1" to temporary string many times with copying, and as you can see this submission gets TL.

→ Reply