filo's blog

Reading strings gets TLE in Go
By filo, history, 7 years ago, In English

Hi all,

I know Go isn't the most popular language when it comes to competitive programming but since it is added on CF I will ask this question.

In this problem I try to read two strings, the problem is that Go's bufio.Text() or bufio.ReadLine() cannot read million characters in one string.

I've tried lots of other options as well(already -57 on that problem), like increasing buffer size for Scanner, or concatenating parts of strings returned from bufio.ReadLine() but all of them gets TLE.

I am almost sure that the solution itself is pretty fast and the problem is in reading from the input.

If you have any idea how to speed it up you are welcome!

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

»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

this might help

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

    Thanks for you effort but still TLE.

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

Your solution involves O(n) inversions via fast exponentiation to 109 + 5. That's sixty million multiplications and thirty million divisions of 64-bit numbers. That's quite a lot and I can easily imagine it getting TLE even if you don't consider reading time.

Two suggestions:

  1. Generate a big test locally and check how long it takes for your solution to read the input.
  2. Optimize your solution so it doesn't do O(n) fast exponentiations.
→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Let's consider two ways of reading input A and B.

    If I read with method A I pass test 14 in 31 ms, but method A isn't suitable for test 22 because of the specifications mentioned above.

    If I read with method B, which should read whole lines without character limitations I get TLE on test 14.

    That's why I think the solution itself works quiet fast.

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

      Method B may be 10-100-1000(sic!) times slower than method A, so test 14 may actually be quite small, so that the solution works ok. This is not a joke.

      → Reply
      • »
        »
        »
        »
        7 years ago, # ^ |
        ← Rev. 3   Vote: I like it 0 Vote: I do not like it

        I got your point and even if you are right, that still doesn`t answer my question. Which method should I use? A: which is super slow or B: which cannot handle large strings. I believe what I am looking for is method C which is faster than A and can read large strings.

        P.S. I've rewritten the code in C++ it passes in 1887 ms.

        → Reply
»
7 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

I think bufio.ReadString('\n') is fast enough. On my machine it takes almost zero time to read two strings with length 106.

But I still get TLE... Maybe my inversion is too slow.

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

    Yes. With a O(n) inversion preprocess algorithm I got Accepted (32779895).

    I/O is not the bottle neck of this problem.

    n - 1 ≡ nt2k - 2 (mod P) where t = ⌊ P / n⌋ and k = P mod n.

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

      But this is still very slow on Codeforces (much slower than equivlent C++ version 32780344). I don't know why. On my machine (x86_64, linux) the C++ version takes 0.28s and the Go version takes 0.44s.

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

        Wow, thanks for your reply, good job! I am not sure was that the official solution? I feel like Go performs really badly on CF, it isn't the first occasion, but it is possible to get AC with Go, so everything is OK.

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

          I found the issue. It seems Google Go compiler for 32-bit x86 (8g) generates very low-performance code. Unfortunately, Codeforces has 32-bit judge machines.

          For 895D - String Mark, 8g generates an executable costing 2.46s on my machine. And gccgo generates an executable costing 1.28s. It seems gccgo is better Go compiler for 32-bit x86.

          Perhaps Google Go compiler is optimized for modern machine with enough registers (for example x86-64), and 32-bit x86 doesn't have much registers.

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

            Makes sense, nice research. But unfortunately there's nothing we can do, other than writing super optimized code for Go when the time limits are tight.

            → Reply