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.
http://pastebin.com/mbgLg1Dk
Should get AC
It is giving me TLE. Moreover, there is significant difference in time too if u see the link on ideone. One is taking 2.7s while other approx 5s.
What about this one? http://pastebin.com/GZmjve72
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.
Change
bool comp( pair<...> pa1, pair<...> pa2 )tobool 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 ofbool 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
~~~~~
This too https://ideone.com/ANL4Xo is giving TLE. Above BekzhanKassenov suggested the same but the code is producing TLE on codechef.
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?
That's really weird. I tried some submissions. Here's what I found.
inline function pointer, equal before less: TLE
inline function pointer, less before equal: TLE
struct comparator, equal before less: TLE
struct comparator, less before equal: Accepted 1.76s
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.
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.
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.
But previously I suggested version with functor and rahul_1234 said that it's TLE. Your version differs from mine only with word
inline. AFAIK all member functions in class/struct are inline by default?U can check urself by submitting on problem link given above. That was producing TLE but using inline works.
I don't have codechef account :)
I've never heard that member functions are inline by default. I don't think so, but don't have a reference at hand at the moment.
https://isocpp.org/wiki/faq/inline-functions#inline-member-fns
The standard says that the declaration of inline and non-inline looks the same. This is not saying that member-functions are inline. The inline keyword is put on the member-function definition.
You can see in the example. The first is the declaration and the second is the definition.
Alright, from next section https://isocpp.org/wiki/faq/inline-functions#inline-member-fns-more it follows that my version was inlined :)
Interesting, I hadn't read the other sections of the page. The compiler decided to ignore it then, but accepts the inline suggestion when we specifically write inline.
inlinegenerally tells the compiler "hey, compile me without using a function stack as if I'm being run in the same line." It's like a macro, but it's not. Not sure how it works assembly level, I just know it's really fast because it's like a direct command.Just read this, should be helpful.