Week of March 26th:
The lab really helped me understand the different sorting algorithms. Apparently, there are 2 things you can do to optimize performance: run the cprofile and check which areas are taking up the most computation, then rewrite them. However, this may not always solve the issue (for example, in bubblesort 1 and 2, as the algorithm may be too intensive even at the simplest implementation). In this case, we were advised to write a new algorithm altogether.
The cprofile was very insightful. For example, I learned that just storing the length of the list in a dummy variable instead of calling len(L) at each recursive call can save quite a bit of time. I did not know that in the long-run, the len() call would weigh the time down so much. I also learned that boolean comparison statements slow the sorts down too.
The Excel chart for all three types of lists was very insightful. The timsort destroyed everyone each time, but I was still curious about it. Apparently it is compiled in C, which, being a "lower" language grants it the super speed, and uses various methods to find runs, or subsets of the list that are already sorted. I learned that (even though the code is alot longer than the sorts we looked at) it spends the majority of the time deciding which sort to use, but that this really pays off because it makes the actual sorting instantaneous. In any case, I was very impressed.
I still don't really get Big-O, in the sense that almost all of the graphs in my chart looked somewhat parabolic. But is there a quick way to 'eyeball' the worst-case-complexity just by looking at the algorithm? The last question on the midterm implied this, but as I'm still uncertain, and I need to ask about this.
Surprisingly, the early exit in bubble_sort 2 added no real benefits as my investigation with the TA showed. Also want to know why this happens.
The lab really helped me understand the different sorting algorithms. Apparently, there are 2 things you can do to optimize performance: run the cprofile and check which areas are taking up the most computation, then rewrite them. However, this may not always solve the issue (for example, in bubblesort 1 and 2, as the algorithm may be too intensive even at the simplest implementation). In this case, we were advised to write a new algorithm altogether.
The cprofile was very insightful. For example, I learned that just storing the length of the list in a dummy variable instead of calling len(L) at each recursive call can save quite a bit of time. I did not know that in the long-run, the len() call would weigh the time down so much. I also learned that boolean comparison statements slow the sorts down too.
The Excel chart for all three types of lists was very insightful. The timsort destroyed everyone each time, but I was still curious about it. Apparently it is compiled in C, which, being a "lower" language grants it the super speed, and uses various methods to find runs, or subsets of the list that are already sorted. I learned that (even though the code is alot longer than the sorts we looked at) it spends the majority of the time deciding which sort to use, but that this really pays off because it makes the actual sorting instantaneous. In any case, I was very impressed.
I still don't really get Big-O, in the sense that almost all of the graphs in my chart looked somewhat parabolic. But is there a quick way to 'eyeball' the worst-case-complexity just by looking at the algorithm? The last question on the midterm implied this, but as I'm still uncertain, and I need to ask about this.
Surprisingly, the early exit in bubble_sort 2 added no real benefits as my investigation with the TA showed. Also want to know why this happens.
No comments:
Post a Comment