Yea right, the three Os of Obsession, Outlook, and Originality together can read OOO and mean that you are Out Of Office for Others 😉
Can be on anything, but when one leads to the other in the order, it can be good, and when it feeds back, can probably be better after each cycle.
Journaling here one such cycle while working on a leet problem.
The Obsession:
Write good code that got translated to get that "faster than 100.00%" report on submission :-)
The problem was very simple, shuffle a std::string 's' based on vector<int> 'indices'.
ex: for input -- std::string s ("rat"); vectot<int> indices{1,0,2}; -- the output std::string t = "art"
The easiest solution for this is:
string t(s.length(), 0);
for(int i = 0; i < s.length(); i++){
t[indices[i]] = s[i];
}
return t;
But here is where obsession bit because of 'faster than 95.12%' feedback... and then what crazy things i tried to get that execution speed up 🙈..
Read the constraints again, tried to take advantage of the fact that 100 is the maximum size of the input string... switched to cycle sort kind of inplace shuffle, even tried to pre-allocate memory for the output string, and somehow hack std::string to wrap around it.. unfortunately, or should i say, fortunately, none of that worked..
The Outlook:
Then i took a pause and asked myself, what am i doing here? what does 100% faster mean? 100% faster has tuned into an obsession because it means well written code. i choose 100% faster as a parameter to measure the quality of code, but here i am obviously destroying it for the sake of 100% faster... so i stepped back and re-asserted that no, the operation is not a success if the patient is dead... Then i was like, ok lets shake the obsession away and think slowly case by case of various approaches and possible areas of improvement..
The Originality:
The simple approach is good, and only goes through the string once, but because we construct an output std:string and there is no interface that gets it to own precreated memory, we will end up initializing the output string once, and hence it takes 2n steps of assignment and O(n) extra memory..
The cycle sort style inplace shuffle is good, but it can also take 2n steps of comparisons though it does only n assignments.
So, what if we can cut the number of comparisons??
Time to do some case analysis of cycle sort style shuffle..
1) Worst case input order:
The worst case occurs when we need to swap n/2 elements individually with each other..
In this case, there are n/2 cycles and after each cycle we step back to the starting point of that cycle and move past it... So it takes at least 2n comparisons no matter what.
2) Best case input order:
The best case order is when we have a perfect cycle, where we start at the beginning and all the elements are chained together neatly ending up at the starting point...
This is a case that can be exploited to avoid additional n comparisons.
3) Average case input order:
It may have some split cycles, but last cycle usually ends somewhere in the middle of the string.
Even, this case can be exploited to avoid at least n/2 additional comparisons..
And that kind of thinking felt like the purpose of practicing code being met and why not don the grin if it also fetches a 'faster than 100%' on the side 😉without forgetting to ask 'can we do better'?
The Output:
No comments:
Post a Comment