P_Nyagolov's blog

Some Help With Speeding Up a C# Program
By P_Nyagolov, history, 9 years ago, In English

Hello everybody,

So two-three weeks ago I started learning C#. I decided to code some problems in C# after doing that in C++ in order to practice it and of course learn some things I don't know to do in that language.

Today I came across this problem — http://codeforces.net/problemset/problem/220/B and I coded Mo's algorithm in C++. It easily got accepted with time about 2 seconds (the time limit is 4 seconds) — http://codeforces.net/contest/220/submission/15191708. Then I moved to C# and after more than an hour spent in looking for 'how to write a comparator for Array.Sort for custom class in C#', I finally submitted a code in C# — http://codeforces.net/contest/220/submission/15192611. As it can be seen, it gave TLE on the fifth test.

Then I read that for large arrays, Array.Sort uses quick sort, so I added a random shuffle before the actual sorting — http://codeforces.net/contest/220/submission/15192841, still TLE #5. I started looking for a faster input method and I read that BufferedStream may help — http://codeforces.net/contest/220/submission/15193006 — unfortunately, it didn't. At the end, I tried to store the whole output in a StringBuilder and then output it but I got TLE once again — http://codeforces.net/contest/220/submission/15193128.

Can anyone please suggest a way to speed the program up? I am quite new to C#, I tried using google but I found no more than what I described in the post.

Thanks in advance! :)

  • Vote: I like it
  • +5
  • Vote: I do not like it

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

If you want to hammer a nail and have a hammer (C++) available, why would you do it with your hand (C#)?

C# is not a language designed to be fast or usable in competitive programming. What you should practice in it is not writing contest problems that have to handle large data in minimum time, but... well, whatever you think it could be used for.

→ Reply
  • »
    »
    9 years ago, # ^ |
    ← Rev. 2   Vote: I like it +10 Vote: I do not like it

    I just tried that for fun, I know it is much slower than C++. Just thought that I may be using something slow (like cin without "magic lines" instead of scanf in C++). So I simply wondered if there is some way to optimize something so that it runs faster :) Also it is know that using getchar or fread is faster than scanf in C++, so maybe there are some optimizations that can be made in C# too, I just wanted to know :)

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it -13 Vote: I do not like it

      I suppose you can always optimise. That's the problem — as long as you use it for contest problems, you'll have to waste time (no, I don't think what you learn that way is worth the effort) with optimisations over optimisations. If you like that, why not try computing outputs by pen and paper?

      → Reply
      • »
        »
        »
        »
        9 years ago, # ^ |
        ← Rev. 2   Vote: I like it +9 Vote: I do not like it

        Well, I don't think it's the same as "computing outputs by pen and paper" :) I don't plan to use C# in contests, the case is different — I just wanted to practice it in a problem from past contest and perhaps learn something new :)

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

          Then don't try to get stuff accepted in time. Assume that you got it right when there was no WA. Avoiding TLEs will help you with exactly nothing.

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

The problem besides IO could be caused by boxing (In Java there is a similar problem when sorting Longs), but since you are using a struct it's seems unlikely. Other nefarious issue is the use of Console.WriteLine that flushes every single time. Use Console.Write or a StringBuffer/Builder to build the output and write it all once at the end.

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

    Use Console.Write or a StringBuffer/Builder to build the output and write it all once at the end.

    Yes, I did that in my last submission as I wrote, but it seems that it wasn't enough. Thanks for your opinion! :)

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it +14 Vote: I do not like it

      You are not doing the sorting properly, you must divide by the square root of N ... check your slightly changed passing solution.

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

        Ah, thanks and sorry for the effort! :) The same code (N instead of sqrt(N)) got AC in C++ btw :P

        → Reply