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

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

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://mirror.codeforces.com/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://mirror.codeforces.com/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://mirror.codeforces.com/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://mirror.codeforces.com/contest/220/submission/15192841, still TLE #5. I started looking for a faster input method and I read that BufferedStream may help — http://mirror.codeforces.com/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://mirror.codeforces.com/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! :)

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

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

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.

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

    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 :)

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

      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?

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

        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 :)

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

          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.

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

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.

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

    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! :)