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

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

In the problem https://www.codechef.com/problems/CHEFQUE,

submission : https://ideone.com/l2LPvy got TLE. It used comp().

However, when I didn't use comp() and just used sort( vc.begin(), vc.end() ) it got accepted. Submission link https://ideone.com/NgbwUO.

Even though both are doing same thing, why comp() is giving TLE and how can we improve on it. Please somebody guide me on this.

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

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

I think the problem is that using a function pointer for the comparison wastes a lot of time in function calls. The second version uses the comparison operator directly.

In your example, there are 281009016 calls to comp(). This takes its toll. Passing arguments by reference saves ~0.5s. Unfortunately, it seems the compiler ignores inlining the function. So, I don't see better than just avoid using comp() here.

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

Change bool comp( pair<...> pa1, pair<...> pa2 ) to bool comp( const pair<...>& pa1, const pair<...>& pa2).

Remember that in C++, passing variables to a function copies the variables each time you call it. In your case, you are passing a pair<pair<ll, int>, bool>, which uses around 24 bytes if I'm not mistaken. In essence, by just passing your pair you already did work. What more if you did it n log n times in a sort, you get an overhead factor of 24.

The thing is, you can bypass the default parameter copy by declaring it as a constant reference. Use bool comp(const TYPE& a, const TYPE& b) instead of bool comp(TYPE a, TYPE b). By doing so, instead of copying your variables everytime, you just copy its address but reference the same variable. Normally, addresses are just around 4 bytes... 20 bytes less!

The reason why the default pair sort is faster is because C++ STL implements constant referencing in all its default sorts. It's the standard.

EDIT: It seems you already tried the constant reference but it's still TLE? Why don't you try

inline bool comp(const pair<pair<ll, int>, bool>& pa1, const pair<pair<ll, int>, bool>& pa2) {
    return pa1.f.f < pa2.f.f || (pa1.f.f == pa2.f.f && pa1.f.s < pa2.f.s);
}

~~~~~

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

    This too https://ideone.com/ANL4Xo is giving TLE. Above BekzhanKassenov suggested the same but the code is producing TLE on codechef.

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

      Moreover it is taking 3.5s while without comp() the code is taking 2.7s on ideone. So, is there any other method which brings execution time to approx 2.7s?

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

        That's really weird. I tried some submissions. Here's what I found.

        inline function pointer, equal before less: TLE

        inline bool comp(const pair<pair<ll, int>, bool>& pa1, const pair<pair<ll, int>, bool>& pa2) {
            if (pa1.f.f == pa2.f.f)
            	return pa1.f.s < pa2.f.s;
            return pa1.f.f < pa2.f.f;
        }
        

        inline function pointer, less before equal: TLE

        inline bool comp(const pair<pair<ll, int>, bool>& pa1, const pair<pair<ll, int>, bool>& pa2) {
            return pa1.f.f < pa2.f.f || (pa1.f.f == pa2.f.f && pa1.f.s < pa2.f.s);
        }
        

        struct comparator, equal before less: TLE

        struct comp {
            inline bool operator()(const pair<pair<ll, int>, bool>& pa1, const pair<pair<ll, int>, bool>& pa2) const {
                if (pa1.f.f == pa2.f.f)
                	return pa1.f.s < pa2.f.s;
                return pa1.f.f < pa2.f.f;
            }
        };
        

        struct comparator, less before equal: Accepted 1.76s

        struct comp {
            inline bool operator()(const pair<pair<ll, int>, bool>& pa1, const pair<pair<ll, int>, bool>& pa2) const {
                 return pa1.f.f < pa2.f.f || (pa1.f.f == pa2.f.f && pa1.f.s < pa2.f.s);
            }
        };
        

        I found out that the last one, according to WikiBooks, is the "most optimal one", though I don't know yet why it's optimal. Weird.

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

          It got accepted using inline function. Thanks a lot.

          Can u plz explain why it got accepted now but was giving TLE before?

          Again thanks a lot.

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

          I think the answer to why is at the end of the section you linked: "Function-objects are usually expanded inline and are therefore as efficient as in-place code, while functions passed by pointers are rarely inlined."

          I didn't expect the compiler to treat them so differently regarding inlining.