Monday 31 March 2014

Sorting and Efficiency

Algorithmic Efficiency

In calculus, we learned about the hierarchy of which types of functions grow more quickly than others.

… ln(n) ≺ n ≺ n ln(n) ≺ n2 ≺ n3 ≺… ≺ en ≺ n! ≺ nn

In computer science, when we analyze a function’s efficiency, we consider the amount of resources it uses, for example, the number of times a loop would iterate, every time it is used on a problem of size n, in the worst-case scenario, i.e. for very large n. We find a function that approximates how the amount of resources used, and thus the run time grows with the value of n, and represent it, in general terms, using “Big O” notation. These may not hold for smaller values of n.

Name
Notation
Example
constant
O(1)
def f(x):
    return ‘taadaa!’
logarithmic
O(log n)
binary search on a sorted list
linear
O(n)
def f(L):
    for item in L:
        return ‘hello!’
“linearithmic”/ “loglinear”/ “quasilinear
O(n log n)”
merge sort, quick sort, and usually timsort
quadratic
O(n2)
bubble sort, selection sort, insertion sort
Similarly, these kinds of functions have a hierarchy, from constant, to quadratic, and so on. The lower down the efficiency of a given function is in the hierarchy, the more slowly it grows as n grows, and the more efficient it is.

Sorting Algorithms

Sorting algorithms, as we know them, sort Python lists, arbitrarily in either ascending or descending order (usually ascending). Back in CSC 108 we learned, and in CSC 148 we have revisited the following three sorting algorithms: bubble sort, selection sort, and insertion sort.

Bubble sort makes multiple passes through a list, comparing adjacent items, and exchanging those pairs of adjacent numbers that are out of order relative to each other. At the end of each pass, another of the largest items has been “Bubbled” up to its final location.

def bubble_sort(L):
    for passnum in range(len(L)-1, 0, -1):
        for i in range(passnum):
            if L[i] > L[i+1]:
                L[i], L[i+1] = L[i+1], L[i]

In a list of length n, the first pass makes (n-1) comparisons, the second, (n-2), the third, (n-3), and so on, until the last (or the (n-1)th pass, where only 1 comparison is made. Thus, a total of (n(n-1))/2 = (1/2)n2 – (1/2)n comparisons are made. This is a quadratic function, so we say that bubble sort’s “problem complexity” is quadratic, or O(n2).

Selection sort sorts lists by finding the largest (or smallest, depending on whether the list is to be in ascending or descending order) item in the yet unsorted section of the list, and swaps it with the item that is currently occupying its final location.  Notice that it only makes one exchange per pass.

def selection_sort(L):
    # find index of largest unsorted item…
    for fillslot in range(len(L)-1, 0, -1):
        ind_of_max = 0
        for I in range (1, fillslot+1):
            if L[i] > L[ind_of_max]:
                ind_of_max = i
        # swap…
        L[i], L[fillslot] = L[fillslot], L[i]

Selection sort also has a problem complexity of O(n2), but tends to execute faster because it does not swap pairs of values as often.

Insertion sort sorts lists by creating a sub-list at one end and, with each pass, adding an item to this section in such a way that it is sorted relative to the other items in this sorted section.

def insertion_sort(L):
    for i in range(1, len(L)):
        # save value to be inserted…
        temp = L[i]
        # make space in sorted section by shifting…
        j = i
        while j != I and L[j-1] > temp:
            L[j] = L[j-1]
            j -= 1
        # insert value…
        L[j] = temp

New to CSC 148, we also learned about shell sort, merge sort, quick sort, and timsort. These are all more efficient than the previous three.

Shell sort sorts lists by creating sub-lists of items that are i items apart (this is sometimes called the “gap”) and sorts these sub-lists. It repeats this process until i has been decreased to 1. Finally, it performs a single insertion sort. It requires a helper function, called gap insertion sort, which creates and sorts the sub-list for each, decreasing value of i.

def shell_sort(L):
    sublist_count = len(L) // 2
    while sublist_count > 0:
        for start in range(sublist_count):
            gap_insertion_sort(L, start, sublist_count)
            sublist_count = sublist_count // 2

def gap_insertion_sort(L, start, gap):
    for I in range (start+gap, len(L), gap):
        current_val = L[i]
        pos = i
        while pos >= gap and L[pos-gap] > current_val:
            L[pos] = L[pos-gap]
            pos -= gap
        L[pos] = current_val

Shell sort is more efficient than insertion sort alone because, by the time all the incremented sub-lists have been sorted, insertion sort has very few comparisons left to make. It usually has a problem complexity that is between O(n) and O(n2), for example, O(n3/2), depending on the list.

Merge sort is the first of our sort algorithms to use recursion. It continually splits a list in half, and then invokes merge sort on both halves until all sub-lists are either of length 1 or 0, and thus sorted by definition. It then merges all the sub-lists into a single, sorted list; using the helper function, merge.
def merge_sort(L):
    if len(L) < 2:
        return L
    else:
        left_sub = L[ : len(L) // 2]
        right_sub = L[len(L) // 2 : ]
        return merge(merge_sort(left_sub), merge_sort(right_sub))

def merge(L1, L2):
    L = []
    L1. reverse()
    L2.reverse()
    while L1 and L2:
        if L1[-1] < L2[-1]:
           L.append(L1.pop())
    L1.reverse()
    L2.reverse()
    return L + L1 + L2

Merge sort divides the list in half log(n) times  and merges n times. It, therefore, has a problem complexity of O(n log n).

Quick sort takes some arbitrary pivot, for example, the first item in the list, and moves all the items less than it to the left; all the items greater, to the right. Note that there are ways in which pivots can be strategically chosen to maximize efficiency. Quick sort is then invoked recursively on the two sub-lists.

def quick(L):
    if len(L) < 2:
        return L[ : ]
    else:
        # i = randint(0, len(L)-1)
        i = 0
        return(quick([x for x in L if x < L[i]] + L[i] + \
             quick([x for x in (L[0:i] + L[i+1: ]) if x >= L[i]]))

Quick sort, like merge sort, also has efficiency O(n log n), but it does not require the additional memory that merge sort does, and can therefore run faster.

Our final, most complicated, and most efficient sorting algorithm is timsort. It is called “timsort” because Tim Peters invented it, in 2002. This is the algorithm Python uses when we call the built-in function, sorted, on a list. Timsort is a “hybrid” sorting sorting algorithm, that uses both merge sort and insertion sort, designed to do what is most efficient for the specific list it is given. It takes advantage subsets of the given list that are already ordered, called “runs,” and uses these to sort more efficiently. Both on average, and in a worst-case scenario, it performs with O(n log n) efficiency.




[1] There are far more different levels of efficiency of functions, but these are a few of the most common or that we’ve most often dealt with in this course.

Tuesday 18 February 2014

Recursion


Fractals and Self-Similarity

A fractal is an object or image that exhibits self-similarity – self-similarity being the quality of “having a substructure analogous or identical to an overall structure” [1] on all scales. Perhaps the most straightforward example of a fractal is a simple line segment. It is a fractal because every sub-segment of a line segment is a smaller scale version of the whole, no matter what part of the line is being considered. Fractals have fractional dimensions. In theory, this means that they are not regular one, two, or three-dimensional things, but rather, actually have dimension between one and two, or two and three! There are many fractals in nature, for example Romanesco broccoli, as well as man made fractals, such as the Sierpinski gasket and Koch’s curve.

Fractals can be made by taking some kind of base shape and applying and reapplying the same change or set of changes to it, ideally ad infinitum, but usually only a very large, though ultimately finite number of times. In other words, they can be made by applying a recursive pattern. Any fractal  can be defined in terms of itself.”[2] As such, we can write code that is similarly “defined in terms of itself”, i.e. programs or functions that call themselves within their own implementation, to create representations of certain fractals on our computers. This kind of self-calling code constitutes recursive programming.

Recursion in General

When a problem can be broken down into smaller but identical or analogous problems, we can use recursion to solve it. In computer science, “recursion means ‘defining something in terms of itself’ usually at some smaller scale, perhaps multiple times, to achieve your objective.” [3] In Python, the reality of a program being “defined in terms of itself” is a little funny looking and counterintuitive at first: A function that is recursive calls itself. This may seem not to make sense at first blush, since, if we are in the middle of a function definition, how can we use the function that we haven’t even finished defining at that point? This is perfectly valid in Python and most programming languages, however. All it tells the computer to do is to pause and start applying the function to the problem on a smaller scale before continuing – where “continuing” may also include this kind of delving into smaller scales to various degrees. Basically, “recursion is induction that can be carried out by a computer.”[4] In this way, it is a very human side to programming. Usually, the result is, we computer scientists being able to solve highly complex problems with much simpler code.




[1] http://www.thefreedictionary.com/Self-similar
[2] How to Think Like a Computer Scientist: Learning with Python 3 18. Recursion (http://openbookproject.net/thinkcs/python/english3e/recursion.html)
[3] How to Think Like a Computer Scientist: Learning with Python 3 18. Recursion (http://openbookproject.net/thinkcs/python/english3e/recursion.html)
[4] Professor Danny Heap, in lecture, January 29th, 2014

Tuesday 21 January 2014

Object-oriented programming

What is object oriented programming?

Object-oriented programming, or OOP, is a programming paradigm. Since the mid 1980’s, it has in fact been the main programming paradigm. It evolved out of a need to simplify our dealings with increasingly complicated software (See footnotes: “How to Think Like a Computer Scientist…”).

Python is “infested by objects”[1]… but what are these objects? The main difference between an object vs. simply a piece of information is that an object contains both data, and the different behaviors that can be associated with that data.  “An object is a software bundle of related state and behavior.”[2] Strictly speaking, an object is “an instance of a class,”[3] where a class is a “blueprint” for that particular type of object. This “blueprint” includes the following: a class name, which is the name of the type of object; attributes, which are pieces of meta-data regarding the object; and methods, which are the operations that can be performed on such an object.

Although we were not aware of it at the time, what we were doing last term in CSC 108 was procedural programming. This is another programming paradigm, which makes use, primarily, of writing functions and calling them, in order to make one’s program run. Object-oriented programming, on the other hand, makes full use of Python’s abilities as an object-oriented programming language by creating “objects which contain both data and functionality together,” [4]

How does it benefit our understanding and use of Python?

One of the goals of CSC 108 and 148 is to begin to instill in us an aversion to excess and to redundancy. In this course, we have already learned a few ways of minimizing effort on the part of the programmer, whilst simultaneously making code easier to understand, and sometimes, as an added bonus, maximizing efficiency on the part of the computer. Examples of this include: replacing code with built-ins that do the same thing (“don’t reinvent the wheel”[5]); using comprehensions to produce a new list, tuple, dictionary, set, or similar data structure; and using ternary to evaluate one expression or another based on a condition.

Like these tools for efficiency, the approach of object-oriented programming is in keeping with the first two cardinal virtues of programming: laziness and impatience (the third and final one being “hubris”). As programmers, ideally, we never want to write the same code more than once. Emphasizing class definition over function definition, as one does in object-oriented programming, allows us to “create relationships between one object and another” by basing a new class on an old class.”[6] This makes it possible to build upon and modify work we have already done in order to fit a new situation (i.e. solve a new problem) without changing, nor having to repeat the original work. Simplifying and reducing our coding workload in this way makes it possible to create more complex programs and solve a wider variety of problems.




[1] CSC148 winter 2014, Introduction to computer science, week 1, Danny Heap (http://www.cdf.toronto.edu/~heap/148/W14/Lectures/danny/W1/intro.pdf)
[2] The Java Tutorials, What is an Object? (http://docs.oracle.com/javase/tutorial/java/concepts/)
[3]  Introduction to Object Oriented Programming Concepts (OOP) and More, 4.4. What is an Object? (http://www.codeproject.com/Articles/22769/Introduction-to-Object-Oriented-Programming-Concep#Object)
[4] How to Think Like a Computer Scientist: Learning with Python 3, 15.1. Object-oriented programming (http://openbookproject.net/thinkcs/python/english3e/classes_and_objects_I.html)
[5] CSC148 winter 2014, abstraction and idiom, week 2, Danny Heap (http://www.cdf.toronto.edu/~heap/148/W14/Lectures/danny/W2/w2.pdf)
[6] Webopedia, object-oriented programming (http://www.webopedia.com/TERM/O/object_oriented_programming_OOP.html)