目录

Objects & Algorithms

Chapter 5 notes

Objects

Classes vs. Instances

Objects and Instances in Python

定义 class 和 instances

# class name
class Student:
    #cstr, self means *this
    def __init__(self):
        # member vars
        self.firstname = "[no first name]"
        self.lastname = "[no last name]"
        self.eyecolor = "[no eye color]"
        self.age = -1

## using instances as the init value ##       
 
class Name:
    def __init__(self):
        self.firstname = "[no first name]"
        self.lastname = "[no last name]"
        
class Student:
    #cstr, self means *this
    def __init__(self):
        # construct a Name class as a default value to student class
        self.name = Name()
        self.eyecolor = "[no eye color]"
        self.age = -1

Creating Instances

# creating instance
myName = Name()
# accessing
print(myName.firstname)
# assignment
myName.firstname = "Gray"

## nesting ##
myStudent = Student()
# assignment
myStudent.name.firstname = "David"

classes 的优势

Encapsulating Methods in Classes

Constructors and Destructors
Getters and Setters

比起直接访问数据，利用 getter 和 setter 提供了更多的便利：

  • 提供读写权限（保证只能从特定的权限级别访问数据）
  • 提供额外的功能（比如记录访问的历史记录）

Encapsulating Methods in Python

Constructors in Python

# parameters are required
# self will be ignored
class Name:
    def __init__(self, firstname, lastname):
        self.firstname = firstname
        self.lastname = lastname

# construct
myName = Name("David", "John")

## parameter list with default value ##
    
    def __init__(self, 
                 firstname = "[no first name]",
                 lastname = "[no last name]"):
        
        self.firstname = firstname
        self.lastname = lastname
        
# call, lastname will be the default value "[no last name]"
myName2 = Name("David")

parameter 数量不满足抛出的异常为 TypeError.

Getters and Setters

Python 中没有提供 access level（比如 C++ 中公私类的申明）。python 中，如果不希望被直接调用的函数，一般前后都有两个下划线，比如 init 

class ExerciseSession:
    def __init__(self, name, intensity, ex_time):
        self.ex_name = name
        self.intensity = intensity
        self.ex_time = ex_time
    
    # getters

    def get_exercise(self):
        return self.ex_name
    
    def get_intensity(self):
        return self.intensity
    
    def get_duration(self):
        return self.ex_time

    # setters

    def set_exercise(self, ex_name):
        self.ex_name = ex_name
    
    def set_intensity(self, intensity):
        self.intensity = intensity

    def set_duration(self, ex_time):
        self.ex_time = ex_time

类中可以提供一个 log 成员函数，用于将每次的改动记录到文本中，方便跟踪。

Advanced Topics in Classes in Python

instance 作为初始化参数

instance 可以作为另外一个 instance 的参数。比如： 

class Person:
    def __init__(self, name, age, father=None, mother=None):
        self.name = name
        self.age = age
        self.father = father
        self.mother = mother

g_dad = Person("Mr. Burdell", 53)
g_mon = Person("Mrs. Burdell", 53)

george_p = Person("George P. Burdell", 25, g_dad, g_mon)

instance 的赋值

将旧的 instance 赋值给新的 instance（name），等于给了这个 instance 修改旧 instance 内内容的权限。任何通过新 instance 修改的内容，均会直接影响旧的 Instance， 比如： 

myPerson1 = Person(Name("David", "Joyner"), "brown", 30)
myPerson2 = myPerson1
myPerson2.eyecolor = "blue"
这里无论是通过 myPerson1 还是 myPerson2 访问 eyecolor，都会得到 blue 的结果。实际上，两个 Name 指向的都是同一个变量。

可以说 instance 也是 mutable 的变量。

Instances as Arguments

instance 也可以作为 argument 传递给函数。这种情况下，函数也会改变 instance 内部的变量值。访问实例如下： 

# song is supposed to be an instance 
def printer(song):
    print(song.name)
    print(song.album)
    print(song.year)
    print(song.artist.name)
    print(song.artist.label)
注意，如果函数的 argument 不是 Mutable 的，那么函数是无法改变 argument 对应的对象的。比如： 
# function that modified the instance
def capitalizeName(name):
    name.firstname = name.firstname.upper()
    name.lastname = name.lastname.upper()

# string is immutable
# function that has done nothing to do with the instance
def capitalizeString(instring):
    instring = instring.upper()

instance 的实拷贝

myPerson1 = Person(Name("David", "Joyner"), "brown", 30)

# instance "myPerson2" is completely rebuilded with value from myPerson1
# instance argument "name" is completely rebuilded as well
myPerson2 = Person(Name(myPerson1.name.firstname, myPerson1.name.lastname),
                   myPerson1.eyecolor, 
                   myPerson1.age)

Polymorphism and Inheritance and Abstraction

Algorithms

Algorithm: Technically, a collection of steps that transforms input into output; commonly, a complex set of lots of steps that is only feasible to perform with the efficiency of a computer.

Famous Algorithms

Complexity and Big O Notation

Complexity
Big O Notation
Common Big O Values

Recursion

实例：factoral

以 $5!$ 为例。要以递归的方式计算 $5!$，那么需要思考的有两个问题：

可以看出来，$5!$ 可以表示为 $5 \times 4!$，$4!$ 可以表示为 $4 \times 3!$。一直直到 $2!$ 可以表示为 $2 \times 1!$。$1!$ 的值显而易见，因此可以用做 base。而之前的通项可以表达为： $$ n \times (n-1)! $$ 因此，如果将阶乘的设计为函数 fractoral()，那么该函数的伪代码可以写成： 

fractoral(n):
   if n > 1:
      return n * fractoral(n-1)
   else:
      return 1

需要注意的是，这里最开始的 $n$，实际上是处于 stack 的最底层。最先计算的，实际上是我们的 base case，也就是这里的 1。这个过程可以想象为，如果我们要解 $5!$，那么首先要求 $4!$，如果要求 $4!$，首先要得到 $3!$…以此类推。当我们最终达到我们已知的 base case，也就是求得 $2!$ 时，整个递归会将求得的结果带入到 stack 下方已经展开的计算部分，直到完成计算。

实例2:Fibonacci 数列

Fibonacci(n):
    if n > 2:
        return Fibonacci(n-2) + Fibonacci(n-1)
    else:
        return 1

尾递归和首递归

假设在递归的过程中，同时还有其他的操作（比如 print)。根据该操作与递归调用的位置不同，递归分为首递归（head recursion）和尾递归（tail recursion）。参考下面的例子： 

# head
def count_down_1(start):
    if start <= 0:
        print(start)
    else:
        count_down_1(start - 1)
        print(start)
        
# tail
def count_down_2(start):
    if start <= 0:
        print(start)
    else:
        print(start)
        count_down_2(start - 1)

        
count_down_1(5)
count_down_2(5)
他们的主要区别在于递归调用是否优先。如果优先调用递归（首递归），那么最开始的打印操作会处于 stack 的最底层。他必须要等到所有栈里的递归调用结束以后，才能开始打印。因此，count_down_1() 的打印结果会从 0 打印到 5，也就是栈顶的打印会优先执行。

如果优先执行打印（尾递归），那么程序将先打印，再压栈。因此，count_down_2() 的打印结果会从 5 到 0，先压入栈的，也就是栈底的打印操作先执行。

Sorting Algorithms

Bubble Sort

该算法的算法复杂度为 $O(n^2)$。

Bubble Sort 的核心是：

实现的细节： 

def bubble_sort(lst):
    is_swap = True
    while is_swap:
        #reset tag, assume no swapping at this round
        is_swap = False
        for idx in range(len(lst)- 1):
            #if the previous number is greater than next number
            if lst[idx] > lst[idx + 1]:
                # swap
                temp = lst[idx]
                lst[idx] = lst[idx + 1]
                lst[idx + 1] = temp
                # swapping happens at this round
                is_swap = True
    return lst

Selection Sort

该算法的复杂度为 $O(n^2)$。

该算法的核心是： 

def selction_sort(lst):

    for i in range(len(lst)):
        # assume the left-most element is the miniumn
        min_idx = i
        # checking the rest of the list [i, end]
        for idx in range(i, len(lst)):
            #find the index of the miniumn
            if lst[idx] < lst[min_idx]:
                min_idx = idx
        
        # insert / swap
        temp = lst.pop(min_idx)
        lst.insert(i, temp)

        #swap might be better way
        #lst[i], lst[min_idx] = lst[min_idx], lst[i]
            
    return lst

Insertion Sort

该算法的算法复杂度是 $O(n^2)$。

Insertion sort 的核心是：

对应的位置的查找原理：

细节： 

def insertion_sort(lst):

    # sorting the base case
    if lst[0] > lst[1]:
        lst[1], lst[0] = lst[0], lst[1]
    
    # inserting starts from 2
    for i in range(2, len(lst)):

        # comparing sorted numbers with the right most(new incoming) number
        
        for idx in range(0, i):
            
            # Since the left part of the list is sorted
            # if any number in that part is larger than the new incoming number
            # that number will be the first one larger than the new incoming number
            # Therefore, the new incoming number should be inserted before that number
            
            if lst[idx] > lst[i]:
                insert_idx = idx
                temp = lst.pop(i)
                lst.insert(insert_idx, temp)
                break
    return lst

Merge Sort

该算法的算法复杂度是 $O(nlog(n))$。

Merge Sort 的核心是：

实现细节： 

def merge_sort(lst):

    if len(lst) == 1:
        return lst
    else:
        mid = len(lst) // 2

        sorted_lst = []

        left = merge_sort(lst[:mid])
        right = merge_sort(lst[mid:])

        while(len(left) > 0 and len(right) > 0):
            if left[0] < right[0]:
                sorted_lst.append(left[0])
                del left[0]
            else:
                sorted_lst.append(right[0])
                del right[0]
        
        sorted_lst.extend(left)
        sorted_lst.extend(right)

        return sorted_lst

Search Algorithms

按位搜寻，算法复杂度为 $O(n)$

Binary Search 的核心：

实现细节： 

# iteration Binary search
def binary_search_iter_3(lst, key):
    
    lst.sort()
    min = 0
    max = len(lst) - 1
    while min <= max:
        mid = (min + max) // 2
        if key == lst[mid]:
            return True
        elif key < lst[mid]:
            max = mid - 1
        else:
            min = mid + 1
    return False
 
# recursion binary search
def binary_search_rec_2(lst, key):
    
    lst.sort()
    if len(lst) == 0:
        return False
    
    mid = len(lst) // 2
    print(lst[mid])
    if lst[mid] == key:
        return True
    elif key < lst[mid]:
        return binary_search_rec_2(lst[:mid], key)
    elif key > lst[mid]:
        return binary_search_rec_2(lst[mid+1:], key)

Binary search + Merge sort 这种方式的主要开销在 merge sort，其复杂度是 linear search 的 $log(n)$ 倍。但由于整个数据集只需排序一次，因此如果要反复进行不同内容的搜索，Binary search 的效率要高得多。