Loading [MathJax]/jax/output/HTML-CSS/fonts/TeX/fontdata.js

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

Автор sahaun, история, 2 года назад, По-английски

I submitted exactly the same code for 86D - Мощный массив on different platforms. Here are the results:

There is a small increase in memory when using 64-bit, but the time difference is pretty huge!

Can anybody explain why?

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

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

long long is a 64-bit data type and obviously works best on a 64-bit system

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

    Makes sense, thanks.

    Is there a reason to use non-64-bit versions at all?

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

      On the 32-bit version, pointers are 32 bit, while on 64-bit, pointers are 64 bit. So if you for some reason need to store a ton of pointers, then the 32-bit version would use half the memory compared to the 64-bit version. That said, 64-bit is better to use in basically any other scenario.

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

It is actually different in my case.

GNU C++17 (64): 165333338 156 ms

GNU C++17: 165333363 62 ms

Solution also uses long long int. There is no difference in memory usage.

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

    I think you will see the differences when running a heavy program or using more pointers as pajenegod suggested above.

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

    What you see there is scanf being faster in C++17(32) than C++17(64). Switching to cin/cout makes your code run in 46 ms 165347564 in C++17(64).

    I belive that part of the reason why scanf is faster in C++17(32) than C++17(64) is that Codeforces is using a custom made I/O speed up patch for C++17(32) (link).

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

      Sorry, shouldn't there be faster instead of slower in first sentence of your comment.

      Thank you, I thought cin is always slower than scanf.

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

        Ah thanks, it should have been faster.

        About cin and scanf. I don't think there is any fundamental reason why one is faster than the other in general.

        I'd personally recommend using cin/cout instead of scanf/printf. Just remember to put something like ios::sync_with_stdio(false); cin.tie(0); in the beginning of main if you are using cin/cout.

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

          Confirmed that I'm wrong on this point, actually cin/cout is safe to use.

          The thing is you should avoid to use cin/cout together with scanf/printf with the stdio sync off, otherwise cin/cout will print everything before scanf/printf.

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

            I have never experienced any problems with cin/cout. Maybe you are just doing it wrong?

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

            Could you point me towards such examples, preferably some problem on an online judge, or maybe a custom test generation setup that makes them fail?

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

            I've never ever seen cin "skip some input randomly".

            One thing that is true is that ios::sync_with_stdio(false); is not always faster. For example, on cf the following program takes

            #include <bits/stdc++.h>
            using namespace std;
            int main() {
                //ios::sync_with_stdio(false);
                for (int i = 0; i < 10000000; ++i)
                  cout << i << '\n';
            }

            Without ios::sync_with_stdio(false);

            • C++14(32) 1559 ms

            • C++17(32) 1574 ms

            • C++17(64) 1185 ms

            • C++20(64) 1216 ms

            With ios::sync_with_stdio(false);

            • C++14(32) 1575 ms

            • C++17(32) 1559 ms

            • C++17(64) 1372 ms

            • C++20(64) 889 ms

            So C++17(64) cout actually becomes slower when you use ios::sync_with_stdio(false);. That said, cin becomes a lot faster in C++17(64) with ios::sync_with_stdio(false);, so it is still worth to use it.