A crucial idea that I learnt in this course is the importance of efficiency.
The idea of algorithmic efficiency wasn’t this important in CSC108 when we were mostly dealing with lists with defined length. However, efficiency becomes so important now because it is one of the key elements that ensures high performance of a complex code since it determines the the speed of runtime execution for the code. There are different ways to achieve efficiency, for example, one can reduce the number of functions, and use recursive functions instead of writing a bunch of loop. No matter how, the goal of code efficiency is to reduce resource consumption and runtime as much as possible.
Today, I also read my old writing in Week5 which is about recursion, and realized that I have a different understanding about the topic now. In my old post, I said that recursion is similar to while loop and for loop, because they are all about repeating calculation. However, I realize that they are very much different in the sense of efficiency. The following code aims to determine whether a sorted list contain a specific number v. It is very efficient because it employs recession. Every time it runs, it divides the list in half, and search the two parts separately at the same time. This function can also be written by while loop, but will look much longer and take more time to execute.
Today, I also read my old writing in Week5 which is about recursion, and realized that I have a different understanding about the topic now. In my old post, I said that recursion is similar to while loop and for loop, because they are all about repeating calculation. However, I realize that they are very much different in the sense of efficiency. The following code aims to determine whether a sorted list contain a specific number v. It is very efficient because it employs recession. Every time it runs, it divides the list in half, and search the two parts separately at the same time. This function can also be written by while loop, but will look much longer and take more time to execute.
class SortedList(list):
''' list in non-decreasing order '''
def __contains__(self, v, start=None, stop=None):
''' (SortedList) -> bool
Return whether SortedList (self) contains v.
'''
if start is None:
start, stop = 0, len(self) - 1
if start > stop:
return False
elif start == stop:
return self[start] == v
else:
mid = (stop + start) // 2
if self[mid] < v:
return self.__contains__(v, mid + 1, stop)
else:
return self.__contains__(v, start, mid)
No comments:
Post a Comment