Often I read many code optimization techniques, but when it comes to applying them practically, it requires practice and strict adherence to a set of coding standards and making it a habit.
In order to see the difference myself before and after applying optimizations, i tried a simple example of merging two sorted arrays into one sorted array
The initial algorithm that pictured in my mind is as follows:
void MergeArrays(int* array_A, int* array_B, int* resultArray, int array_ALength, int array_BLength)
{
int k = 0, j = 0;
for(int i = 0; i < array_ALength; )
{
for(; j < array_BLength;)
{
if(i < array_ALength && array_A[i] <= array_B[j])
{
resultArray[k] = array_A[i];
k++; i++;
}
else
{
resultArray[k] = array_B[j];
k++; j++;
}
}
if(i < array_ALength)
{
resultArray[k] = array_A[i];
k++; i++;
}
}
}
Since there were two arrays, I used two ‘for’ loops. Then compare the corresponding value of each array and add the smallest to the result array and increment the pointer of result array and the array from which it is copied. The above algorithm is tested and seems to work as expected.
Lets compute the complexity of the algorithm. Looking at the two ‘for’ loops, one within another, will give an impression of time complexity of O(n*n), but a detailed observation says otherwise. The inner for loop is executed until all the elements in array_B is copied to result array (‘array_BLength’ number of elements). At the same time some of the elements in array_A may also be copied. Lets say ‘x’ elements copied (where x <= array_ALength, and array_ALength being the total number of elements). The outer ‘for loop’ copies any of the left over elements from array_A to the resultArray (array_ALength – x elements are copied).
Total complexity = array_BLength + x + array_ALength – x = array_ALength + array_BLength (sum of the number of elements in both arrays) = O(n)
Observing the above complexity,
1) we can eliminate the need for two ‘for loops’ and can merge all into one loop.
2) The code looks messy because of the presence of loop index incrementing code. This can be eliminated by post-incrementing the loop counter, while coping the elements to the result array.
The resulting algorithm after applying the above two optimizations is as follows.
void MergeArrays(int* array_A, int* array_B, int* resultArray, int array_ALength, int array_BLength)
{
int k = 0;
for(int i = 0, j = 0; i < array_ALength, j < array_BLength; )
{
if(i < array_ALength && array_A[i] <= array_B[j])
{
resultArray[k++] = array_A[i++];
}
else
{
resultArray[k++] = array_B[j++];
}
if(i < array_ALength && j >= array_BLength)
{
resultArray[k++] = array_A[i++];
}
}
}
A further review shows the above algorithm can still be optimized.
3) The two ‘if’ conditions are essentially doing the same job and they can be merged into one.
The final algorithm:
void MergeArrays(int* array_A, int* array_B, int* resultArray, int array_ALength, int array_BLength)
{
int resPtr = 0;
for(int i = 0, j = 0; (i < array_ALength || j < array_BLength); )
{
if(i < array_ALength && (array_A[i] <= array_B[j] || j >= array_BLength))
{
resultArray[resPtr++] = array_A[i++];
}
else
{
if(j < array_BLength)
resultArray[resPtr++] = array_B[j++];
}
}
}
With the above examples, I am with the opinion that, along with standard methods of optimizations, understanding and estimating the complexity of the algorithm help us write better code, making small tweaks helps to reduce the length of code and reviewing code will help us get rid of redundant code either by merging or making it a function.
In the beginning stages as a programmer it’s important to review as much code as possible and making it a habit. Obviously the final product will be more reliable and reduces the support and maintenance cost.
No comments:
Post a Comment