In this exercise I'm using Visual Studio 2019 and a modified version of the std_lib_facilities header found here.
Chapter 26 // Exercise 11
Time the sum example from section 26.6 with m being square matrices with dimensions 100, 10,000, 1,000,000, and 10,000,000. Use random element values in the range [-10:10). Rewrite the calculation of v to use a more efficient (not O(N2)) algorithm and compare the timings.
I literally had no memory of how to use the matrix code from Chapter 24 at all. It was practically a year ago for me at this point. It took me a while to figure out how to use it again and what to do.
row_sum needs to be implemented. After that I had trouble creating the random matrices of certain values as I kept getting bad memory allocations and I was only at a matrix of size 10,000. I'm pretty sure Bjarne did this intentionally, or he was using a super computer, as mine kept running out of memory trying to allocate values into the matrices. I did some quick calculations and realised this is because a matrix of size 10,000 x 10,000 is trying to allocate memory for 100,000,000 doubles. A double is 8 bytes, so we're roughly trying to allocate memory for 762 MB of memory in one go. For the next size up of 1,000,000 that would equate to 7.45 terabytes!
Yeah, Bjarne definitely did this on purpose. So instead of creating these large matrices, I decided to "simulate" the large matrix by just computing the sum. However, this is still very slow and will take forever past 10,000.
Ultimately I don't believe there is a way to use a more efficient algorithm because summing all the elements in a matrix is O(N^2). All we can do is try and make the code more efficient like passing by reference or using multithreading.
No comments:
Post a Comment