Released at 24 May, the Lovelock is another great step to a better user experience. I installed it today and was shocked by the revolutionary changes to the GNOME desktop, now it's the GNOME shell that I'm interacting with.
It may seem unfamiliar and even irritating when I found no minimize button and everything in my Desktop folder does not show up on the desktop and I have to find applications in another place. But, but, but after I read the release note which is well prepared for the situation that a user like me can have, it answered me all my questions, and in one hour, I started to love it! Fedora name this 15th release Lovelock, does that mean something?
The Super key is really handy, it calls up immediately all windows opened for you to select one. Also it brings the launch bar to front so launching an application can be done instantly with the advantage that it does not take any space when you are working in the application.
Also the Firefox 4, just great! I love it, especially the Sync.
As a programmer, I have the gcc 4.6 in this new release, I have vim 7.3, I have sons 2.0.1 ...
All in all, I love the Lovelock, better than ever.
Saturday, June 11, 2011
Introduction to Algorithms - The Reading Notes: Part 4, Maximun Sum Sub-Array (BF)
Maximum Sub Sub-Array is an interesting problem. It goes like this, I'm given a series of values and I'm asked to find a continuous sub-series that has the maximum sum.
For example, if I'm given a series of value -3, 2, 5, 6, -1, 2, -5, 5, then I find that the sub-series 2,5,6 gives 13 which quite large, but 2, 5, 6, -1, 2 sums up even more, it gives 14. If I look further, I find that the sub-series 2, 5, 6, -1, 2, -5, 5 gives the same maximum of 14. So we may have more than one maximum and our goal is to find any one of them.
ITA mentions the brutal force algorithm that has Ω(n^2) running time, it says the algorithm is to calculate sums of all sub-series possible (there is O(n^2) number of sub-series) and if we can evaluate each sub-series in constant time then we can have Ω(n^2) algorithm, but it does not say how. ITA introduces also a very fast (O(nlgn) algorithm based on DaC (Divide and Conquer).
I understand that this ITA chapter is for DaC so no need to talk more details on this brutal force algorithm and it's put in the exercise. So, let's finish the Ω(n^2) brutal force algorithm first then we will see how to implement the DaC one.
So you already know the number of sub-series is O(n^2), suppose we have a n-length series, but why? The answer is this number equals to the number of ways you have when you try to select any two numbers in the series (those two numbers defines the start and end of the sub-series), that is n(n-1)/2.
Now comes to the question how we calculate the sum of each sub-series. If we just simply calculate sums for all sub-series, then we have to sum n sub-series of length 1, n-1 sub-series of length 2, n-2 sub-series of length 3, ..., 1 sub-series of length n. In total, we need to do add n+2(n-1)+3(n-2)...+ n times, which is equivalent to sum(for i = 1 to n) (i*(n-i+1)), which renders our algorithm O(n^3) in terms of time consumption.
Now we need to do more to get a faster algorithm. Just one more glance at our previous O(n^3) algorithm we find that the sub-series have many common parts and we add those parts repeatedly many times once for each sub-series. That's the key to reduce running time.
I will now use a n*n matrix to save sums of each sub-series, say, [0-1], [0-2]... [1,2], [1,3]... Also each single element represents also a sub-series of length 1, they are also stored in the matrix [0,0], [1,1] ... So only the upper triangle of the matrix is used. The advantage to save the sums in the matrix is that it's very easy to find a sub-series that can be used to build the next sum, because we know that:
sum(sub[i, j]) = sum(sub[i, j-1]) + v[j] = sum(sub[i, j-1]) + sub[j, j]
OK, that's enough for the theory, let's see the code. But wait a moment, before implementing the algorithm, let's put in place the unit test!
I'll use another class for the MaxSubArray unit test, separated from that of the sort algorithms. With CppUnit, I just simply create a .h and .cpp for the new tests, no other configuration is needed.
MiscTest.h
MiscTest.cpp
Finally, I can start implementing the algorithm. Then I run the unit test each time I think my algorithm will work, then fix bugs and retry. Here is the final version that passes the test above:
Let discuss the faster version that takes only O(nlgn) time, in the next post. Thank you and like to know your feedback.
For example, if I'm given a series of value -3, 2, 5, 6, -1, 2, -5, 5, then I find that the sub-series 2,5,6 gives 13 which quite large, but 2, 5, 6, -1, 2 sums up even more, it gives 14. If I look further, I find that the sub-series 2, 5, 6, -1, 2, -5, 5 gives the same maximum of 14. So we may have more than one maximum and our goal is to find any one of them.
ITA mentions the brutal force algorithm that has Ω(n^2) running time, it says the algorithm is to calculate sums of all sub-series possible (there is O(n^2) number of sub-series) and if we can evaluate each sub-series in constant time then we can have Ω(n^2) algorithm, but it does not say how. ITA introduces also a very fast (O(nlgn) algorithm based on DaC (Divide and Conquer).
I understand that this ITA chapter is for DaC so no need to talk more details on this brutal force algorithm and it's put in the exercise. So, let's finish the Ω(n^2) brutal force algorithm first then we will see how to implement the DaC one.
So you already know the number of sub-series is O(n^2), suppose we have a n-length series, but why? The answer is this number equals to the number of ways you have when you try to select any two numbers in the series (those two numbers defines the start and end of the sub-series), that is n(n-1)/2.
Now comes to the question how we calculate the sum of each sub-series. If we just simply calculate sums for all sub-series, then we have to sum n sub-series of length 1, n-1 sub-series of length 2, n-2 sub-series of length 3, ..., 1 sub-series of length n. In total, we need to do add n+2(n-1)+3(n-2)...+ n times, which is equivalent to sum(for i = 1 to n) (i*(n-i+1)), which renders our algorithm O(n^3) in terms of time consumption.
Now we need to do more to get a faster algorithm. Just one more glance at our previous O(n^3) algorithm we find that the sub-series have many common parts and we add those parts repeatedly many times once for each sub-series. That's the key to reduce running time.
I will now use a n*n matrix to save sums of each sub-series, say, [0-1], [0-2]... [1,2], [1,3]... Also each single element represents also a sub-series of length 1, they are also stored in the matrix [0,0], [1,1] ... So only the upper triangle of the matrix is used. The advantage to save the sums in the matrix is that it's very easy to find a sub-series that can be used to build the next sum, because we know that:
sum(sub[i, j]) = sum(sub[i, j-1]) + v[j] = sum(sub[i, j-1]) + sub[j, j]
OK, that's enough for the theory, let's see the code. But wait a moment, before implementing the algorithm, let's put in place the unit test!
I'll use another class for the MaxSubArray unit test, separated from that of the sort algorithms. With CppUnit, I just simply create a .h and .cpp for the new tests, no other configuration is needed.
MiscTest.h
1: #ifndef MISCTEST_H 2: #define MISCTEST_H 3: #include <cppunit/extensions/HelperMacros.h> 4: 5: 6: class MiscTest : public CppUnit::TestFixture { 7: 8: CPPUNIT_TEST_SUITE( MiscTest); 9: CPPUNIT_TEST( testMaxSubArray_0); 10: CPPUNIT_TEST_SUITE_END(); 11: 12: private: 13: public: 14: 15: void setUp(); 16: void tearDown(); 17: 18: // Test cases. 19: void testMaxSubArray_0(); 20: 21: }; 22: #endif MiscTest.cpp
1: #include "MiscTest.h" 2: #include "MaxSubArray.h" 3: 4: using namespace Common::Algorithm::MaxSubArray; 5: 6: // Registers the fixture into the 'registry' 7: CPPUNIT_TEST_SUITE_REGISTRATION( MiscTest ); 8: 9: void MiscTest::setUp() 10: { 11: } 12: void MiscTest::tearDown() 13: { 14: } 15: 16: // Test normal case. 17: void MiscTest::testMaxSubArray_0() 18: { 19: int iArray[] = {-10, 5, 7, -2, 19, 50, -30, 32, -24, 18}; 20: std::vector<int> v(iArray, iArray + sizeof(iArray) / sizeof(int)); 21: 22: int rStart = 0; 23: int rEnd = 0; 24: int rSum = 0; 25: MaxSubArray::CalcBF(v, rStart, rEnd, rSum); 26: 27: CPPUNIT_ASSERT_EQUAL( 1, rStart); 28: CPPUNIT_ASSERT_EQUAL( 7, rEnd); 29: CPPUNIT_ASSERT_EQUAL(81, rSum); 30: 31: } Finally, I can start implementing the algorithm. Then I run the unit test each time I think my algorithm will work, then fix bugs and retry. Here is the final version that passes the test above:
1: void MaxSubArray::CalcBF(std::vector<int> &v, int &oStart, int &oEnd, int &oSum) 2: { 3: // Trivial cases, size = 0 or 1. 4: if (v.size() == 0) 5: { 6: oStart = 0; 7: oEnd = 0; 8: oSum = 0; 9: return; 10: } 11: 12: if (v.size() == 1) 13: { 14: oStart = 0; 15: oEnd = 0; 16: oSum = v[0]; 17: return; 18: } 19: 20: oSum= 0; 21: oStart = 0; 22: oEnd = 0; 23: std::vector<int> vResult; 24: 25: // Initialize vResult. 26: for (size_t i = 0; i < v.size(); i++) 27: { 28: for (size_t j = 0; j < v.size(); j++) 29: { 30: if (i == j) 31: { 32: vResult.push_back(v[i]); 33: } 34: else 35: { 36: vResult.push_back(0); 37: } 38: } 39: } 40: 41: 42: // Calculate the results. 43: // We use a matrix to store sum of all intervals 44: // 00 01 02 03 04 45: // 10 11 12 13 14 46: // 20 21 22 23 24 47: // 30 31 32 33 34 48: // 40 41 42 43 44 49: // M[i,i] = v[i] 50: // M[i,j] = sum(i,j) for 0 <= i < j <= v.size(). 51: // It takes O(n^2) time. 52: for (size_t i = 0; i < v.size(); i++) 53: { 54: for (size_t j = 0; j < v.size(); j++) 55: { 56: if (i < j) 57: { 58: vResult[ i * v.size() + j] = vResult[ i * v.size() + j - 1 ] + 59: vResult[ j * v.size() + j]; 60: if (oSum < vResult[i * v.size() +j]) 61: { 62: oSum = vResult[i * v.size() + j]; 63: oStart = i; 64: oEnd = j; 65: } 66: } 67: } 68: } 69: } Let discuss the faster version that takes only O(nlgn) time, in the next post. Thank you and like to know your feedback.
Thursday, June 2, 2011
Introduction to Algorithms - The Reading Notes: Part 3, Merge Sort
Merge sort is a better sorting algorithm than insertion sort in terms of worst case running time. It's also the algorithm that I ran into when I have my interview for my current job.
The ITA book uses it as an example of the Divide and Conquer philosophy which basically divides a big problem into several smaller ones then solve each of them first, when the smaller problems are solved, the big problem becomes easier to solve. This usually results in a recursive algorithm as the case of the merge sort. I'm not sure it's a good place to introduce this concept in the beginning part of the book, the learning curve is quite steep.
The merge sort contains two parts, the divide or recursive part and the merge part. The idea is to divide the whole list to sort into two lists each of half the original size and sort the two lists separately, then merge the two sorted smaller lists into one sorted list to get the problem solved. The magic is to repeat this procedure for the two smaller lists too, so they became four even smaller lists, and so on.
The merge part is quite straightforward, compare the elements at the head position of two sorted list, and put the larger (or smaller) into the result list until one of the list contains no element, then we can safely put the rest of the other list into the result list. Only one thing to remark, the vector constructor who takes to iterators s and e means to construct a vector that contains elements from s to e-1 of the original vector.
The recursive part is a bit tricky. Personally, I prefer to give a unique interface to the users of my sorting library, so I'd like to call my interface MergeSort::Sort(input_vector_to_sort, order). Then I found that I need a helper method that can be called recursively and I named it as DoSort(). DoSort() takes two additional parameters, the start and the end position in the list that defines the sub-list to be sorted. It starts by dividing the input vector into two smaller ones then it calls itself recursively for each smaller vector, finally it merges the two smaller vector (sorted now).
Finally, the interface method is fairly simple:
The ITA book uses it as an example of the Divide and Conquer philosophy which basically divides a big problem into several smaller ones then solve each of them first, when the smaller problems are solved, the big problem becomes easier to solve. This usually results in a recursive algorithm as the case of the merge sort. I'm not sure it's a good place to introduce this concept in the beginning part of the book, the learning curve is quite steep.
The merge sort contains two parts, the divide or recursive part and the merge part. The idea is to divide the whole list to sort into two lists each of half the original size and sort the two lists separately, then merge the two sorted smaller lists into one sorted list to get the problem solved. The magic is to repeat this procedure for the two smaller lists too, so they became four even smaller lists, and so on.
The merge part is quite straightforward, compare the elements at the head position of two sorted list, and put the larger (or smaller) into the result list until one of the list contains no element, then we can safely put the rest of the other list into the result list. Only one thing to remark, the vector constructor who takes to iterators s and e means to construct a vector that contains elements from s to e-1 of the original vector.
1: void MergeSort::Merge(std::vector<int> &v, int p, int q, int r, bool bNonDecreasing) 2: { 3: std::cout << "Merging sub array: " << p << ":"<< q-1 << " and " << q << ":" << r-1 << std::endl; 4: std::vector<int> vSub1(v.begin()+p, v.begin()+q); 5: std::vector<int> vSub2(v.begin()+q, v.begin()+r); 6: std::cout << "vSub1.size: " << vSub1.size() << ", vSub2.size: "<< vSub2.size() << std::endl; 7: int iLastValue = (bNonDecreasing ? INT_MAX : INT_MIN); 8: 9: vSub1.push_back(iLastValue); 10: vSub2.push_back(iLastValue); 11: 12: int i = 0; 13: int j = 0; 14: for (int k = p; k < r; k++) 15: { 16: if ( bNonDecreasing && (vSub1[i] < vSub2[j]) || 17: !bNonDecreasing && (vSub1[i] > vSub2[j])) 18: { 19: v[k] = vSub1[i]; 20: i++; 21: } 22: else 23: { 24: v[k] = vSub2[j]; 25: j++; 26: } 27: 28: } 29: } The recursive part is a bit tricky. Personally, I prefer to give a unique interface to the users of my sorting library, so I'd like to call my interface MergeSort::Sort(input_vector_to_sort, order). Then I found that I need a helper method that can be called recursively and I named it as DoSort(). DoSort() takes two additional parameters, the start and the end position in the list that defines the sub-list to be sorted. It starts by dividing the input vector into two smaller ones then it calls itself recursively for each smaller vector, finally it merges the two smaller vector (sorted now).
1: void MergeSort::DoSort(std::vector<int> &v, int p, int r, bool bNonDecreasing) 2: { 3: std::cout << "Sorting sub array: " << p << ":" << r << std::endl; 4: if (p < r) 5: { 6: int q = (p+r)/2; 7: std::cout << "Dividing sub array: " << p << ":" << q << ", " << q+1 << ":" << r << std::endl; 8: DoSort(v, p, q, bNonDecreasing); 9: DoSort(v, q+1, r, bNonDecreasing); 10: Merge(v, p, q+1, r+1, bNonDecreasing); 11: } 12: } Finally, the interface method is fairly simple:
1: void MergeSort::Sort(std::vector<int> &v, bool bNonDecreasing) 2: { 3: if (v.size() < 1 ) 4: { 5: return; 6: } 7: 8: DoSort(v, 0, v.size()-1, bNonDecreasing); 9: } Wednesday, May 11, 2011
Introduction to Algorithms - The Reading Notes: Part 2, Insertion Sort
Insertion Sort is probably the simplest algorithm so it is used in many books as the first example. ItA discusses this minion algorithm right in the Part I Foundations, Chapter 2 Getting Started.
The aim of the algorithm is to sort a set of keys in a certain order: You have some keys as input then the algorithm will give you a ordered list of your keys. Here is how the insertion sort works: suppose all the keys are in an input list, then the algorithm starts working on the the keys one by one in a certain order, for example from left to right. Each time it works on a key, it save it's value, then it looks all keys already processed (they are to the left of the current key), from right to left, by comparing the current key with them and moving the processed keys one place to the right if it should be placed after the current key, according to the ordering rule. This process ends until when an already processed key that should be placed to the left of the current key or there is no more already processed keys. Then we put the current key in the place of the last already processed key we found. Now that we find a good place for the current key, we can start processing the next unprocessed key.
The algorithm is simple, code the pseudo code in C++ is straightforward. What I'd to say here is how I set up the whole project with CppUnit and SCons.
CppUnit is very handy for unit test, especially when I'm writing libraries. Just as in this ITA project, I'd like to put all the algorithms in some libraries, I don't need to write a separate main cpp file just to test these algorithms, instead, I setup a CppUnit testing framework for this. It's easier to maintain. For how to install/use CppUnit, here is the CppUnit Documentation.
First, I implement the Insertion Sort algorithm in InsertSort.cpp and .h files and I put them in a folder named Sorting. With TDD in mind, I write only the class declaration but leaving the method empty.
Then I setup the CppUnit framework: I need three files: SortingTest.h and .cpp, where I'll implement test code for all the sorting algorithms I'll write; TestMain.cpp. where is the "main" function of the test code. The beauty of using CppUnit is this "main" function has only infrastructure interest, it's not related to the particular test cases. So once setup, I don't need to change it. I'll only work on the SortingTest class.
Now I will write a test case:
The aim of the test case is to test the basic function of the algorithm, I initialize a vector with 10 integers, then I call the InsertSort(), finally, I test that the vector is sorted by examining that each element has the expected value. CppUnit provides a macro CPPUNIT_ASSERT_EQUAL for this kind of test.
Now that I have the algorithm code (although not yet complete), I have the testing code, I can compile both and run my test. I use SCons for this. SCons is very convenient yet powerful. Basically, you write a configuration file usually named as SConstruct, inside you tell scons how to build your project.
The Library keyword at line 1 specifies a library to build, the source code are all the .cpp files in the Sorting folder.
The test code should be built with the Program keyword, as in line 3. It needs all source code in the CppUnitTest folder and two libraries: the CppUnit library and the Sorting library that I'm testing. The Sorting library is in my local folder so I need to tell SCons where to find it with LIBPATH keyword as in line 6 above. Finally, the test code need the Sorting library header to compile, I'll tell SCons to find the Sorting headers in the Sorting folder with CPPPATH keyword as in line 7.
OK, now I save the Sconstruct file then I type scons. It compiles my Sorting library and the testing code.
I can run the test immediately and it fails evidently. Now you can start to write the InsertSort() method, but personally, I will write some more test cases before writing the InsertSort() method. For example, I will write one case when the input is empty, another when all inputs have the same value, etc.
Finally, I write my InsertSort() method and correct all failing cases, once all test cases pass, I'm quite confident that my InsertSort() works correctly.
Here is the how the InsertSort() is implemented:
Modification: When I started to write the merge sort, I found it could be better to rename the class and the methods, and finally, I ended up with a solution that gives each sorting algorithm a class and they all have the same Sort() method declaration.
The aim of the algorithm is to sort a set of keys in a certain order: You have some keys as input then the algorithm will give you a ordered list of your keys. Here is how the insertion sort works: suppose all the keys are in an input list, then the algorithm starts working on the the keys one by one in a certain order, for example from left to right. Each time it works on a key, it save it's value, then it looks all keys already processed (they are to the left of the current key), from right to left, by comparing the current key with them and moving the processed keys one place to the right if it should be placed after the current key, according to the ordering rule. This process ends until when an already processed key that should be placed to the left of the current key or there is no more already processed keys. Then we put the current key in the place of the last already processed key we found. Now that we find a good place for the current key, we can start processing the next unprocessed key.
The algorithm is simple, code the pseudo code in C++ is straightforward. What I'd to say here is how I set up the whole project with CppUnit and SCons.
CppUnit is very handy for unit test, especially when I'm writing libraries. Just as in this ITA project, I'd like to put all the algorithms in some libraries, I don't need to write a separate main cpp file just to test these algorithms, instead, I setup a CppUnit testing framework for this. It's easier to maintain. For how to install/use CppUnit, here is the CppUnit Documentation.
First, I implement the Insertion Sort algorithm in InsertSort.cpp and .h files and I put them in a folder named Sorting. With TDD in mind, I write only the class declaration but leaving the method empty.
Then I setup the CppUnit framework: I need three files: SortingTest.h and .cpp, where I'll implement test code for all the sorting algorithms I'll write; TestMain.cpp. where is the "main" function of the test code. The beauty of using CppUnit is this "main" function has only infrastructure interest, it's not related to the particular test cases. So once setup, I don't need to change it. I'll only work on the SortingTest class.
Now I will write a test case:
1: // Test normal case. 2: void SortingTest::testInsertSort_0() 3: { 4: int iArray[] = {10, 5, 7, -2, 19, 50, 300, 320, 160, 1000}; 5: std::vector<int> v(iArray, iArray + sizeof(iArray) / sizeof(int)); 6: Common::Algorithm::Sort::InsertSort(v); 7: CPPUNIT_ASSERT_EQUAL(v[0], -2); 8: CPPUNIT_ASSERT_EQUAL(v[1], 5); 9: CPPUNIT_ASSERT_EQUAL(v[2], 7); 10: CPPUNIT_ASSERT_EQUAL(v[3], 10); 11: CPPUNIT_ASSERT_EQUAL(v[4], 19); 12: CPPUNIT_ASSERT_EQUAL(v[5], 50); 13: CPPUNIT_ASSERT_EQUAL(v[6], 160); 14: CPPUNIT_ASSERT_EQUAL(v[7], 300); 15: CPPUNIT_ASSERT_EQUAL(v[8], 320); 16: CPPUNIT_ASSERT_EQUAL(v[9], 1000); 17: }The aim of the test case is to test the basic function of the algorithm, I initialize a vector with 10 integers, then I call the InsertSort(), finally, I test that the vector is sorted by examining that each element has the expected value. CppUnit provides a macro CPPUNIT_ASSERT_EQUAL for this kind of test.
Now that I have the algorithm code (although not yet complete), I have the testing code, I can compile both and run my test. I use SCons for this. SCons is very convenient yet powerful. Basically, you write a configuration file usually named as SConstruct, inside you tell scons how to build your project.
1: Library(target='Sorting/Sorting', \ 2: source=Glob('Sorting/*.cpp')) 3: Program(target='CppUnitTest/TestMain', \ 4: source=Glob('CppUnitTest/*.cpp'), \ 5: LIBS=['cppunit','Sorting'], \ 6: LIBPATH='Sorting', \ 7: CPPPATH=['Sorting', 'CppUnitTest']) The Library keyword at line 1 specifies a library to build, the source code are all the .cpp files in the Sorting folder.
The test code should be built with the Program keyword, as in line 3. It needs all source code in the CppUnitTest folder and two libraries: the CppUnit library and the Sorting library that I'm testing. The Sorting library is in my local folder so I need to tell SCons where to find it with LIBPATH keyword as in line 6 above. Finally, the test code need the Sorting library header to compile, I'll tell SCons to find the Sorting headers in the Sorting folder with CPPPATH keyword as in line 7.
OK, now I save the Sconstruct file then I type scons. It compiles my Sorting library and the testing code.
I can run the test immediately and it fails evidently. Now you can start to write the InsertSort() method, but personally, I will write some more test cases before writing the InsertSort() method. For example, I will write one case when the input is empty, another when all inputs have the same value, etc.
Finally, I write my InsertSort() method and correct all failing cases, once all test cases pass, I'm quite confident that my InsertSort() works correctly.
Here is the how the InsertSort() is implemented:
1: void Sort::InsertSort(std::vector<int> &v) 2: { 3: int key = 0; 4: 5: // Trivial case, nothing to do. 6: if (v.size() <= 1) 7: { 8: return; 9: } 10: 11: for (int j = 1; j < v.size(); j++) 12: { 13: key = v[j]; 14: int i = j-1; 15: while (i >= 0 && v[i] > key) 16: { 17: v[i+1] = v[i]; 18: i--; 19: } 20: v[i+1] = key; 21: } 22: } 23: Modification: When I started to write the merge sort, I found it could be better to rename the class and the methods, and finally, I ended up with a solution that gives each sorting algorithm a class and they all have the same Sort() method declaration.
1: void InsertSort::Sort(std::vector<int> &v, bool bNonDecreasing) Monday, May 9, 2011
Introduction to Algorithms - The Reading Notes: Part 1, Introduction
I started reading this book recently and I will share my understandings and thoughts with you.
I will discuss the problems in the book and I'd like to inject in particular more on the software engineering aspects of those algorithms: how to implement them so they can be used in a real-life software project to solve practical problems.
Finally, I will code those algorithms in C++ and build the code under Fedora Linux with Scons. I will also adopt the TDD methodology (TDD stands for Test Driven Development) and use CppUnit for unit testing.
Here are some useful links for this project:
The code formatter, it formats the source code into HTML so they look better when put in the blog. Currently it formats C#, VB and some other languages but not C/C++. I'll continue looking for one but before I find something, I'll use this one for the moment.
The SCons user's guide.
The CppUnit Documentation.
I will discuss the problems in the book and I'd like to inject in particular more on the software engineering aspects of those algorithms: how to implement them so they can be used in a real-life software project to solve practical problems.
Finally, I will code those algorithms in C++ and build the code under Fedora Linux with Scons. I will also adopt the TDD methodology (TDD stands for Test Driven Development) and use CppUnit for unit testing.
Here are some useful links for this project:
The code formatter, it formats the source code into HTML so they look better when put in the blog. Currently it formats C#, VB and some other languages but not C/C++. I'll continue looking for one but before I find something, I'll use this one for the moment.
The SCons user's guide.
The CppUnit Documentation.
Saturday, May 7, 2011
A Real-life Story about Return by Reference - Part II
Now we know that we should follow some "best practices" when dealing with return by reference:
1. Use toto aToto = getToto() or toto aToto(getToto()), don't write toto aToto; aToto = getToto();
2. Don't return a reference to a local variable, except when you know what you are doing
3. Let member function return a reference to a member variable when the performance is really an issue, and call it with toto &aTotoRef = aToto.getTotoRef() to really take advantage of return by reference. Otherwise, return by value. Always take care of the variable holding the reference result, use it only during the life time of the object itself.
There is one last thing you may want to know, that is the RVO does not work all the time, as a result it cost you one more construction/destruction of your object when you return it by value. I won't say it's a penalty you have to pay, it's just the fair cost you have to pay as the compiler can not help you more because your code asks for more. So when RVO does not work? Well, when the compiler can not decide which is the object it needs to return at compile time. Here is an example:
toto getTotoWithParam(bool first)
{
if (first)
{
toto aToto;
return aToto;
}
else
{
toto bToto;
return bToto;
}
}
Then, when calling this function, it will show you that the RVO is not apllied.
toto a = getTotoWithParam(false);
toto constructor.
toto copy constructor.
toto destructor.
toto destructor.
The object is constructed inside the function then used to copy construct the object holding the result. Compared with the getToto() function, one more object (temporary object) is created.
toto aToto = getToto():
toto constructor.
toto destructor.
So that all about the return by value/reference that I want to tell you, I hope you now know what to do given a certain situation.
Good luck and I'd like to know what you are thinking about this.
1. Use toto aToto = getToto() or toto aToto(getToto()), don't write toto aToto; aToto = getToto();
2. Don't return a reference to a local variable, except when you know what you are doing
3. Let member function return a reference to a member variable when the performance is really an issue, and call it with toto &aTotoRef = aToto.getTotoRef() to really take advantage of return by reference. Otherwise, return by value. Always take care of the variable holding the reference result, use it only during the life time of the object itself.
There is one last thing you may want to know, that is the RVO does not work all the time, as a result it cost you one more construction/destruction of your object when you return it by value. I won't say it's a penalty you have to pay, it's just the fair cost you have to pay as the compiler can not help you more because your code asks for more. So when RVO does not work? Well, when the compiler can not decide which is the object it needs to return at compile time. Here is an example:
toto getTotoWithParam(bool first)
{
if (first)
{
toto aToto;
return aToto;
}
else
{
toto bToto;
return bToto;
}
}
Then, when calling this function, it will show you that the RVO is not apllied.
toto a = getTotoWithParam(false);
toto constructor.
toto copy constructor.
toto destructor.
toto destructor.
The object is constructed inside the function then used to copy construct the object holding the result. Compared with the getToto() function, one more object (temporary object) is created.
toto aToto = getToto():
toto constructor.
toto destructor.
So that all about the return by value/reference that I want to tell you, I hope you now know what to do given a certain situation.
Good luck and I'd like to know what you are thinking about this.
Sunday, April 24, 2011
Books to read (once more)
Mathematics, Data Structures & Algorithms
Discrete Mathematics and Its Applications
(Fifth Edition), Kenneth H.Rosen
Concrete Mathematics : A Foundation for Computer Science
(Second Edition), Ronald L. Graham / Donald E. Knuth / Oren Patashnik
Introduction to Algorithms (Second Edition)
, Thomas H. Cormen / Charles E. Leiserson / Ronald L. Rivest / Clifford Stein
Data Structures, Algorithms, and Applications in C++
， Sartaj Sahni
Data Structures & Program Design In C (Second Edition), Robert Kruse / C.L. Tondo / Bruce Leung
The Art of Computer Programming
Donald E.Knuth
Compiler
Compilers: Principles, Techniques, and Tools
(2nd Edition)
[Alfred V. Aho / Ravi Sethi / Jeffrey D. Ullman]
Advanced Compiler Design and Implementation
[Steven S. Muchnick]
Operating System
Operating System Concepts
(Now we have the 7th Edition)
[Abraham Silberschatz / Peter Baer Galvin / Greg Gagne]
Operating Systems : Design and Implementation
(Now we have the 3rd Edition)
[Andrew S. Tanenbaum / Albert S. Woodhull]
C++
C++ Primer
Lippman / Josee Lajoie]
The C++ Programming Language (Special Edition)
[Bjarne Stroustrup]
Effective C++
(Now we have the 3rd Edition)
More Effective C++
Scott Meyers
C++ Gotchas: Avoiding Common Problems in Coding and Design
Stephen C.Dewhurst
Modern C++ Design: Generic Programming and Design Patterns Applied
Andrei Alexandrescu
ASM
The Art of Assembly Language
Randall Hyde (x86)
Introduction to 80x86 Assembly Language and Computer Architecture
Richard C. Detmer
UNIX Programming
Advanced Programming in the UNIX Environment
[W. Richard Stevens]
The UNIX Programming Environment
[Brianw. Kernighan]
UNIX Network Programming, Volume 1 : The Sockets Networking API (Third Edition)
[W. Richard Stevens / Bill Fenner / Andrew M. Rudoff]
UNIX Network Programming Volume 2 : Interprocess Communications (Second Edition)
[W. Richard Stevens]
Computer Networks
Computer Networks (Fourth Edition)
[Andrew S. Tanenbaum]
TCP/IP Illustrated, Volume 1 : The Protocols
TCP/IP Illustrated, Volume 2 : The Implementation
TCP/IP Illstrated, Volume 3 : TCP for Transactions, HTTP, NNTP, and the UNIX Domain Protocols
[W. Richard Stevens]
Internetworking with TCP/IP Vol I : Principles, Protocols, and Architecture (Third Edition)
Internetworking with TCP/IP Vol II : Design, Implementation, and Internals (Second Edition)
Internetworking with TCP/IP Vol III : Client-Server Programming and Applications, BSD Socket Version (Second Edition)
Internetworking with TCP/IP Vol III : Client-Server Programming and Applications, Windows Sockets Version
[Douglas E. Comer / David L. Stevens]
Database
An Introduction to Database Systems (Seventh Edition)
[C. J.Date]
Database System Concepts (Fourth Edition)
[Abraham Silberschat / Henry F.Korth / S.Sudarshan]
Software Engineering
Code Complete， Steven C. McConnell
Pragmatic programmer: from journeyman to master， Andrew Hunt and David Thomas
Peopleware：Productive Projects and Teams, Tom DeMarco, Timothy Lister
Discrete Mathematics and Its Applications
(Fifth Edition), Kenneth H.RosenConcrete Mathematics : A Foundation for Computer Science
(Second Edition), Ronald L. Graham / Donald E. Knuth / Oren PatashnikIntroduction to Algorithms (Second Edition)
, Thomas H. Cormen / Charles E. Leiserson / Ronald L. Rivest / Clifford SteinData Structures, Algorithms, and Applications in C++
， Sartaj Sahni Data Structures & Program Design In C (Second Edition), Robert Kruse / C.L. Tondo / Bruce Leung
The Art of Computer Programming
Donald E.Knuth
Compiler
Compilers: Principles, Techniques, and Tools
(2nd Edition)[Alfred V. Aho / Ravi Sethi / Jeffrey D. Ullman]
Advanced Compiler Design and Implementation
[Steven S. Muchnick]
Operating System
Operating System Concepts
(Now we have the 7th Edition)[Abraham Silberschatz / Peter Baer Galvin / Greg Gagne]
Operating Systems : Design and Implementation
(Now we have the 3rd Edition)[Andrew S. Tanenbaum / Albert S. Woodhull]
C++
C++ Primer
Lippman / Josee Lajoie]
The C++ Programming Language (Special Edition)
[Bjarne Stroustrup]
Effective C++
(Now we have the 3rd Edition)More Effective C++
Scott Meyers
C++ Gotchas: Avoiding Common Problems in Coding and Design
Stephen C.Dewhurst
Modern C++ Design: Generic Programming and Design Patterns Applied
Andrei Alexandrescu
ASM
The Art of Assembly Language
Randall Hyde (x86)
Introduction to 80x86 Assembly Language and Computer Architecture
Richard C. Detmer
UNIX Programming
Advanced Programming in the UNIX Environment
[W. Richard Stevens]
The UNIX Programming Environment
[Brianw. Kernighan]
UNIX Network Programming, Volume 1 : The Sockets Networking API (Third Edition)
[W. Richard Stevens / Bill Fenner / Andrew M. Rudoff]
UNIX Network Programming Volume 2 : Interprocess Communications (Second Edition)
[W. Richard Stevens]
Computer Networks
Computer Networks (Fourth Edition)
[Andrew S. Tanenbaum]
TCP/IP Illustrated, Volume 1 : The Protocols
TCP/IP Illustrated, Volume 2 : The Implementation
TCP/IP Illstrated, Volume 3 : TCP for Transactions, HTTP, NNTP, and the UNIX Domain Protocols
[W. Richard Stevens]
Internetworking with TCP/IP Vol I : Principles, Protocols, and Architecture (Third Edition)
Internetworking with TCP/IP Vol II : Design, Implementation, and Internals (Second Edition)
Internetworking with TCP/IP Vol III : Client-Server Programming and Applications, BSD Socket Version (Second Edition)
Internetworking with TCP/IP Vol III : Client-Server Programming and Applications, Windows Sockets Version
[Douglas E. Comer / David L. Stevens]
Database
An Introduction to Database Systems (Seventh Edition)
[C. J.Date]
Database System Concepts (Fourth Edition)
[Abraham Silberschat / Henry F.Korth / S.Sudarshan]
Software Engineering
Code Complete， Steven C. McConnell
Pragmatic programmer: from journeyman to master， Andrew Hunt and David Thomas
Peopleware：Productive Projects and Teams, Tom DeMarco, Timothy Lister
Subscribe to:
Posts (Atom)
Posts
