I was solving the Search Insert Position problem on LeetCode. The following code takes almost 9ms to run all test cases.
class Solution {
public:
int searchInsert(vector<int>& nums, int target) {
int lo = 0, hi = nums.size() - 1;
while (lo <= hi) {
int mid = lo + (hi - lo) / 2;
if (target < nums[mid]) {
hi = mid - 1;
} else if (target > nums[mid]){
lo = mid + 1;
} else {
return mid;
}
}
return lo;
}
};
When I checked out other people's top answers, I found a strange code snippet. When I copy-paste the snippet into my answer, the same code above takes only 4ms, which is faster than almost 99% of other solutions. Can anyone explain the speed up? The snippet is the following:
#include <vector>
#include <iostream>
using namespace std;
static vector<int> nums=[](){
std::ios::sync_with_stdio(false);
cin.tie(NULL);
return vector<int>{};
}();
This snippet is made to "improve performance" but for a cost. I'll explain:
std::ios::sync_with_stdio(false);
This disables the synchronization of C and C++ standard streams. By default they're synced to allow mixing C and C++ I/O streams (e.g. cout and printf would work written in a C++ file).
cin.tie(NULL);
This unties cin from cout. Again, by default they're tied to make cout appear before cin (i.e. output flushes before input) so you can make for example the following:
cout << "Number: ";
cin >> number;
When you untie them you might get to the input(cin) before getting the output (cout) flushed.
These couple lines help to make code run faster but at the cost previously explained. So use with caution.
References: https://www.geeksforgeeks.org/fast-io-for-competitive-programming
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With