reduce, local/non-local/global scopes, cache

In the past weeks we finished off the semester by learning about reduce, local/non-local/global scopes, and cache.

Reduce is a built in function that takes a function, a sequence, and a value (called 'initial'). Reduce takes the sequence and applies the function to every value in the sequence. If an initial is given, the initial will be placed at the beginning of the items.

I had a lot of trial and error before I figured out how to use this built-in function. Eventually I came up with a simple example that showed how it worked:

def add(x, y):

    return x + y

def add_list(t: list):

    return reduce(add, t, 0)

With this function you would be able to add up all the items in a list (basically sum()).

Reduce seems to be very useful for minimizing the amount of code you have to write to reach your desired result.

We also learned about local, non-local, and global scopes. Assigning a value locally means to assign a value deep within the function. Assigning a value non-locally means to assign a value in the outermost scope that is still within the function. Assigning a value globally means to assign a value in the global scope (e.g. I can call the value in the Python shell). Writing nonlocal before assigning something to a variable allows me to assign values in the outer (but no global) scope and writing global before assigning something to a variable allows me to assign values in the global scope.

I had a hard time figuring out how to use nonlocal and global because typing in help(nonlocal) or help(global) in the Python shell did nothing. So I turned to Google.

The last thing we learned was cache, the introduction of a dictionary into a recursive function to minimize the number of steps to complete its implementation, thereby significantly cutting down on running time. In class, we saw that using a dictionary instead of simply powering through recursive calls severly cut down on running time of the fibonacci sequence function. Referring to a dictionary to retrieve a value is much faster than recursively calling a function over and over again, since we already know what the value is. We cut down on a lot of redundancy.

I am still trying to completely understand this concept but the general idea is clear to me. I still find it a little difficult to trace through this process, especially with the fibonacci sequence function that Danny showed us.

By reading the slogs of my classmates, it seems that most people understand the reduce function and the idea of local, non-local, and global scopes. But some people, myself included, seem to be having trouble with the idea of introducing a dictionary to cut down on the number of steps to implement a recursive function (cache).

I will definitely try to incorporate these functions and ideas into my future code.

SLOG Topic: Sorting algorithms

The algorithms we analyzed in class were mainly selection sort, merge sort, and quick sort.

In selection sort, we would look for the largest value by going through the list and keeping track of the largest value thus far, and then put it in its proper location (the right-most spot). Selection sort has a running time of O(n^2).

In merge sort we would keep splitting the list into halves and each of those halves into halves until we have one-element lists. Then we would compare each pair to make those mini lists to create bigger sorted lists, and eventually we would reach the sorted list. Merge sort has a running time of O(n log n).

In quick sort we choose a value in the list as a 'pivot'. Numbers to the left of the pivot are to be smaller than the pivot, and numbers to the right are to be greater than the pivot. We start from the left side and keep going right until we reach a number that is greater than or equal to the pivot. This is the ‘leftmark’. We also start from the right side and keep going left until we reach a number that is less than or equal to the pivot. This is the ‘rightmark’. Then we swap the leftmark and rightmark. We continue going left and right nor new leftmarks and rightmarks to swap until the leftmark and rightmark reach each other. We then put a pivot in between. Then we repeat the process with left and right sides of pivot as two different lists. Quick sort has a running time of O(n log n) in its best case scenario and O(n^2) in its worst case scenario (this worst case scenario is extremely rare).

Choosing the most efficient algorithm will generally involve choosing the algorithm with the lowest big-O notation. In lab 9 we analyzed the running time of these algorithms by sorting a few thousand values. As we increased the number of values the algorithms with O(n^2) running time lagged significantly compared to the O(n log n) algorithms. Efficiency is increased dramatically when the algorithm sorts recursively as opposed to using multiple loops.

After reading the slogs of my classmates, it seems that everyone has a tight grasp on comparing different sorting algorithms.

property()

Last week we learned about the built-in python function property. I didn't really know how to use this function until I asked for advice on Piazza. But even after figuring out I wasn't really sure what the point of this function was because up until now we've been assigning values as self.x = x as soon as we called our class. But I soon realized that you can add if statements to prevent future users of your code to input invalid values. The example Danny used was:

    symbol = property(get_symbol, set_symbol, None, None)

    def set_symbol(self: 'RegexTreeNode', s: str) -> None:
        """set private symbol"""
        if not s in '01e|.*':
            raise Exception('Invalid symbol: {}'.format(s))
        else:
            self._symbol = s

The highlighted part in set_symbol made it so that if the someone was to pass a value other than 01e|.* as the parameter then an error would be raised. This could be one of the pitfalls in A2, even though it was not specified that we had to take such cases into consideration.

After reading the slogs of my classmates, it seems like others are also having trouble understanding how to use the property function and what it should be used for.

I look forward to using this function in my future code.

More sorting adventures

This past week we continue to learn about various types of sorting. Reading over the slog entries of classmates, it seems that most people have grasped this concept, especially those taking csc165 this semester, as we are also learning this topic in that class. I feel that the algorithms that have an average run-time of O(n^2) are generally easier to understand. I found that in most cases O(n^2) algorithms tend to use for loops inside for loops, as in selection sort. The algorithms that have an average run-time of O(n log n) are a little harder to understand. Some examples are merge sort and quick sort. The general idea of theses O(n log n) algorithms are to divide the array into smaller arrays and those arrays into even smaller arrays.These types of algorithms make use of recursion to sort the array.

One problem I have is understanding how a recursive algorithm would have a run-time of O(n log n). Another question I have is why sorting recursively would result in a shorter run-time compared to something like O(n^2) run-time. If any classmates reading this could explain I’d appreciate it!

Binary Search Trees and Running Time Analysis

One topic we covered this week were the binary search trees. This is a tree where a number designated as the main root would be placed as the starting point of the tree. Then you can insert additional numbers into the tree, and the code would sort it so that numbers less then the parent would be put into the left sub tree and numbers greater would be put into the right sub tree. I enjoy working with binary search trees, especially when there is a __str__() method where we can print a visual representation of the tree.

The other topic we were briefly introduced to was running time analysis. This is the analysis of how fast or slow your function would run. Depending on how you implement the algorithm in your function, the running time may increase or decrease. It may increase/decrease constantly, logarithmically, linearly, quadratically, exponentially, etc. This is a very interesting topic. Thus far our code would run and return a value immediately but this may not be the case for a larger amount of code. Also, we as students may not care as much about the running time of our programs but it would be very important to programmers of commercial software.

After reading the slogs of my classmates, it seems that most people have a grasp on these concepts.

List Nodes

This week we learned about list nodes. These are lists of nodes within each other that can represent trees. In our examples we used each node and leaf merely carried a number but I can see it’s uses if it were to carry other types of information. We also learned to use the __repr__ method, in which simply inputting an object would return it’s ‘cargo’, as opposed to inputting ‘print(object)’ or ‘object.__str__()’. It seems to be quite useful and convenient.

Most other bloggers seem to understand this concept well.

Oct 14-18

This week we did not learn anything new because we had the Thanksgiving holiday and a test on Wednesday.