Efficient Code?
-
I have recently been asked to code a function to reverse a single linked list. The code that I provided is the next: void Reverse(Link *pList) { Link *pH = NULL; Link *pT = pList; while (pList) { pList = pList->Next; pT->Next = pH; pH = pT; pT = pList; } pList = pH; } I didn't use any data structure (like a stack) to reverse the list because I been said that it should save memory and be very efficient. Well, after showing my code and being reviewed I have been notified that the code works well but it shows a pretty basic skills in C++ :confused: I would like to know your opinion about it. Is there a more efficient code to reverse a single linked list? Do you agree in the fact that it shows very basic level of C++? I have been coding in C++ for 7 years and I have been evaluated before in C++ coding with a very high scores. I am just wondering if am I missing something? Thank you guys :cool:
-
I have recently been asked to code a function to reverse a single linked list. The code that I provided is the next: void Reverse(Link *pList) { Link *pH = NULL; Link *pT = pList; while (pList) { pList = pList->Next; pT->Next = pH; pH = pT; pT = pList; } pList = pH; } I didn't use any data structure (like a stack) to reverse the list because I been said that it should save memory and be very efficient. Well, after showing my code and being reviewed I have been notified that the code works well but it shows a pretty basic skills in C++ :confused: I would like to know your opinion about it. Is there a more efficient code to reverse a single linked list? Do you agree in the fact that it shows very basic level of C++? I have been coding in C++ for 7 years and I have been evaluated before in C++ coding with a very high scores. I am just wondering if am I missing something? Thank you guys :cool:
Looks like the MS's interview question =) If you have said that this is very basic code for such a skilled C++'er you should give them something like this (it's a recursive approach)
void RecursiveReverse(List **pList)
{
if( (*pList) == NULL || (*pList)->Next == NULL )
return;List \*pOldNext = (\*pList)->Next; RecursiveReverse(&pOldNext); (\*pList)->Next->Next = \*pList; (\*pList)->Next = NULL; (\*pList)= pOldNext;}
Best regards, ----------- Igor Soukhov (Brainbench/Tekmetrics ID:50759) igor@soukhov.com | ICQ:57404554 | http://soukhov.com
-
Looks like the MS's interview question =) If you have said that this is very basic code for such a skilled C++'er you should give them something like this (it's a recursive approach)
void RecursiveReverse(List **pList)
{
if( (*pList) == NULL || (*pList)->Next == NULL )
return;List \*pOldNext = (\*pList)->Next; RecursiveReverse(&pOldNext); (\*pList)->Next->Next = \*pList; (\*pList)->Next = NULL; (\*pList)= pOldNext;}
Best regards, ----------- Igor Soukhov (Brainbench/Tekmetrics ID:50759) igor@soukhov.com | ICQ:57404554 | http://soukhov.com
Given today's definition of "efficient" (i.e. fast), recursive implementations are by nature inefficient, since each recursive call requires the creation and destruction of a stack frame. However, a recursive solution may be still be valid if it's easier to understand and maintain. /ravi "There is always one more bug..." http://www.ravib.com ravib@ravib.com
-
Given today's definition of "efficient" (i.e. fast), recursive implementations are by nature inefficient, since each recursive call requires the creation and destruction of a stack frame. However, a recursive solution may be still be valid if it's easier to understand and maintain. /ravi "There is always one more bug..." http://www.ravib.com ravib@ravib.com
Hi Ravi ! I've a look thru all this topic and found no definition of "efficiency" as the "speed". Of course it's quite common definition - but not for this case. I know that my code most probably will be a slower (yeah - I know how the recursive technics works) than the original - but this code may be more efficeint for a size of code =) and definitely more "elegant" =) Best regards, ----------- Igor Soukhov (Brainbench/Tekmetrics ID:50759) igor@soukhov.com | ICQ:57404554 | http://soukhov.com
-
Hi Ravi ! I've a look thru all this topic and found no definition of "efficiency" as the "speed". Of course it's quite common definition - but not for this case. I know that my code most probably will be a slower (yeah - I know how the recursive technics works) than the original - but this code may be more efficeint for a size of code =) and definitely more "elegant" =) Best regards, ----------- Igor Soukhov (Brainbench/Tekmetrics ID:50759) igor@soukhov.com | ICQ:57404554 | http://soukhov.com
привет Igor, I agree it's more elegant and therefore more appealing. The problem about efficiency is that one has to determine how the code will be used. If the list reversal would be done infrequently, a recursive and interative solution would work equally. However, if the reversal was being done in a loop, we'd be better off with a an interative approach. In my experience, a decision to suggest a code change during a code review hinges on these factors (I'm sure there are more), in descending order of importance: - Is the code clear and easy to maintain? - Can it be made to run faster? - Can it be used to take less space? Cheers, /ravi "There is always one more bug..." http://www.ravib.com ravib@ravib.com
-
Hi Ravi ! I've a look thru all this topic and found no definition of "efficiency" as the "speed". Of course it's quite common definition - but not for this case. I know that my code most probably will be a slower (yeah - I know how the recursive technics works) than the original - but this code may be more efficeint for a size of code =) and definitely more "elegant" =) Best regards, ----------- Igor Soukhov (Brainbench/Tekmetrics ID:50759) igor@soukhov.com | ICQ:57404554 | http://soukhov.com
...and of course, - Is the code correct? :-) /ravi "There is always one more bug..." http://www.ravib.com ravib@ravib.com
-
привет Igor, I agree it's more elegant and therefore more appealing. The problem about efficiency is that one has to determine how the code will be used. If the list reversal would be done infrequently, a recursive and interative solution would work equally. However, if the reversal was being done in a loop, we'd be better off with a an interative approach. In my experience, a decision to suggest a code change during a code review hinges on these factors (I'm sure there are more), in descending order of importance: - Is the code clear and easy to maintain? - Can it be made to run faster? - Can it be used to take less space? Cheers, /ravi "There is always one more bug..." http://www.ravib.com ravib@ravib.com
Hi Ravi (surfed all the net to find out how it should be in Hindi and doesn't found any wroking online English->Hindi translator =). I'm 100% agree with you that that code is only looks great - in real practice I'd better use something more easy to understand and therefore to maintain. Best regards, ----------- Igor Soukhov (Brainbench/Tekmetrics ID:50759) igor@soukhov.com | ICQ:57404554 | http://soukhov.com
-
...and of course, - Is the code correct? :-) /ravi "There is always one more bug..." http://www.ravib.com ravib@ravib.com
Sure, just tested it - it works perfectly.;P Best regards, ----------- Igor Soukhov (Brainbench/Tekmetrics ID:50759) igor@soukhov.com | ICQ:57404554 | http://soukhov.com
-
Looks like the MS's interview question =) If you have said that this is very basic code for such a skilled C++'er you should give them something like this (it's a recursive approach)
void RecursiveReverse(List **pList)
{
if( (*pList) == NULL || (*pList)->Next == NULL )
return;List \*pOldNext = (\*pList)->Next; RecursiveReverse(&pOldNext); (\*pList)->Next->Next = \*pList; (\*pList)->Next = NULL; (\*pList)= pOldNext;}
Best regards, ----------- Igor Soukhov (Brainbench/Tekmetrics ID:50759) igor@soukhov.com | ICQ:57404554 | http://soukhov.com
Thank you Igor for your response. In my original post, I was saying that I didn't use any data structure like the stack because it's supposed to save memory and be efficient (for efficient code, my personal view is that it solves the problem in less cycles of the processor in question, and saves as many resources as it can). Your code is very elegant and effcient (from my own perspective), but I'm affraid that it would be rejected anyway based on the fact that it is using the system's stack for the recursion (Alas, a data structure), and dereferencing the double pointer takes some more time than dereferencing a single pointer. I could imagine that this will be the response from the person who asked me to do such a function. Just to be fair, I had requested to code another function related to binary trees, and guess what? I used recursion but had the same feedback X|
-
Thank you Igor for your response. In my original post, I was saying that I didn't use any data structure like the stack because it's supposed to save memory and be efficient (for efficient code, my personal view is that it solves the problem in less cycles of the processor in question, and saves as many resources as it can). Your code is very elegant and effcient (from my own perspective), but I'm affraid that it would be rejected anyway based on the fact that it is using the system's stack for the recursion (Alas, a data structure), and dereferencing the double pointer takes some more time than dereferencing a single pointer. I could imagine that this will be the response from the person who asked me to do such a function. Just to be fair, I had requested to code another function related to binary trees, and guess what? I used recursion but had the same feedback X|
Don't waste your time with the person who rejects these "classic" solutions. Best regards, ----------- Igor Soukhov (Brainbench/Tekmetrics ID:50759) igor@soukhov.com | ICQ:57404554 | http://soukhov.com