Chapter 5 notes

• Object-oriented programming: A programming paradigm where programmers define custom data types that have custom methods embedded within them.
• Object: An object is a custom data structure that organizes and encapsulates variables and methods into a single data type. It is used near-interchangeably with “instance.”
• Class: A custom data type comprised of multiple variables and/or methods. Instances or objects are created based on the template provided by the class.

• Class: 对特定类型数据的一般性描述
• instance: 基于指定类型的 class 特例（实例）

• 需要类名，构造函数 init
• 成员的初始值可以是任意类型，包括函数，或者其他类（或类成员）

# 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 instance
myName = Name()
# accessing
print(myName.firstname)
# assignment
myName.firstname = "Gray"

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

• 保证 key 的存在
• 在存储数据的同时，提供 methods 方便数据的管理

• Encapsulation：封装，将变量与成员函数的定义至于类中，保证类中的数据不会被其他函数或程序误用。
• 通用的 Method分类：constructor, destrcutor, getters, setters

• Constructor: A common type of method in writing classes that specifies some code to run whenever a new instance of the class is created. The constructor often has parameters that provide values to initialize the variables defined by the class.
• Destructor: A common type of method in writing classes that specifies how the instance of a class is to be destroyed, such as releasing its memory back to the computer.

• Getter: A common type of method in writing classes that returns the value of a variable contained within the class
• Setter: A common type of method in writing classes that sets a variable contained within the class to a new value

• 构造函数的初始化列表需要在 init 内部定义
• 构造函数可以接受外部传递的 variable

# 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")

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

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（name），等于给了这个 instance 修改旧 instance 内内容的权限。任何通过新 instance 修改的内容，均会直接影响旧的 Instance， 比如：

myPerson1 = Person(Name("David", "Joyner"), "brown", 30)
myPerson2 = myPerson1
myPerson2.eyecolor = "blue"

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)

# 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()

• 如果希望进行实拷贝，传递的参数类型必须是 immutable 的参数。
• 对于 instance，如果希望直接拷贝，我们需要强制创建一个新的 instance 作为参数。
• 如果该 instance 需要另外一个 instance 作为参数，那么这个 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)

• Abstraction: A principle of object-oriented programming that states that only essential information should be made visible to the outside program.
• Polymorphism : The principle that a method call can behave differently depending on the arguments and object with which it is called.
• Inheritance: A principle of object-oriented programming where classes can be created that are “subclasses” of other classes, inheriting all the variables and methods from the other class while supplying new variables, methods, or behaviors of these own.

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.

• Data Compression
• Random Number Generator
• Search Algorithms

• Complexity: The rate at which the number of operations requires to run an algorithm grows based on the value of the input on which it operates.
  • 讨论复杂度的时候，通常会讨论最坏情况（upper bounds）的运行时间

• Big O Notation: A notation for expressing the worst-case efficiency of an algorithm in terms of the size of the input.
• 使用 $O$ 或者 $\Omega$ 表示
• 衡量的是 Order of magnitude（数量级），不会考虑常数系数（比如 $O(n^2/2)$）的复杂度是 $O(n^2)$
• 算法大多数都有自己擅长的数据领域。不同的数据中，同样的算法带来的复杂度会有高有低。

• $O(1)$：constant，执行次数与数据集的大小无关
• $O(n)$：linear：执行次数与数据集的大小呈线性关系
• $O(n^2)$：Quadratic：执行次数是数据集大小的平方
• $O(n^3)$：Polynomial：执行次数是数据集大小的立方（及其以上）
• $O(2^n)$：Exponential：执行次数是基于常数的，指数项为数据集大小的指数
• $O(log(n)$：logarithmic：执行次数是数据集大小的平方根结果
• $O(nlog(n)$： Loglinear：执行次数是数据集大小平凡根与数据集大小的乘积（通常出现在排序中）
• $O(n)$：Factorial：执行次数是数据集大小的阶乘（通常出现在递归中）

• Recursion: A programming method characterized by functions that, during their operation, call additional copies of themselves
  • 主要思想是将问题分解为更小的，可以用相同方法解决的问题。

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

• $5!$ 有没有办法分解为更小的，但性质相同的问题
• $5!$ 最后会不会有一个终结的 case

可以看出来，$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

• base case: $1$ ($F(1) = 1$, $F(2) = 1$)
• general: $F(n-2) + F(n-1) (n > 2)$

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)

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

Bubble Sort 的核心是：

• 比较相邻的两个元素
• 如果顺序不对，就调换两个元素的位置。
• 所有元素比较完成后，再重复上面的步骤，直到排序完成

实现的细节：

• 用一个 swap tag 来判断当前是否还有交换发生。
• 没有交换发生意味着排序换成

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

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

该算法的核心是：

• 扫描整个 list，将最小的值找出来，插入到 list 第一个元素之前
• 将其他剩余的元素视作整个 list，重复上面的步骤（e.g. 第一轮 0-9，第二轮 1-9，以此类推），直到排序换成

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

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

Insertion sort 的核心是：

• 将整个 list 分成两部分，已经排序的和没有排序的。
• 排好序的部分处于左边，从两个数开始。
• 每一轮从右边未排序部分加入一个数到左边
• 将该数与已排序部分的所有数比较，比较完毕后将其插入对应的位置

对应的位置的查找原理：

• 将新加入的数与已排序部分每一个数进行对比
• 如果有一个数大于新加入的数，那么该数一定是已排序部分中，大于新加入数的最小的那一个。
• 因此，新加入数应该插入该数之前

细节：

• 找到了大于新加入的数的数以后，就无需再进行余下的比较了。

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

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

Merge Sort 的核心是：

• 拆分：将整个 list 进行递归式的对半拆分
• 比较：对拆分完的两个 list 进行首元素比较。
• 排序：建立一个新的 list，将之前比较结果中较小的数添加到该 list 中。删除原有 List 的对应数，再进行下一轮的首元素比较。
• 合并：当比较完成时，原有的两个 list 至少会有一个为空。此时新 list 中的数是按照从小到大依次排序好的，直接与剩余的，原有 list 中的数合并，即可完成排序。

实现细节：

• 使用递归的方式来进行 list 拆分。
• 每个 list 按中点划分为左右两个子 List
• base case 是两个子 list 均包含一个数的时候。此时的 list 长度为 2，直接返回即可。
• 如果不是 base case：
  • 首先对当前的 list 进行划分
  • 其次分别对 sub list 应用 merge sort。
  • 当 sub list 的 mergesort() 调用到栈顶时，返回的左右 sublist 分别只有一个数，此时可以开始进行比较
    • 如果左边小于右边，那么将左边的数添加到结果 list 中，并删除左边 list 中的数。反之对右边做同样的操作
    • 最后将剩余的，sublist 中的所有数添加到结果 List 中，并返回该 list。
  • 返回的 list 即为下一层栈的 sublist，且已经排好序。这样递归式的对 sublist 进行排序，最终就能得到结果。

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

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

• 只能应用于有序数据集
• 使用递归
• 算法复杂度为 $O(log(n))$

Binary Search 的核心：

• 使用当前范围的中间数与搜索关键词比较
  • 相等即证明找到
  • 不相等：关键词小于当前中间数，证明搜寻范围应该在中间数的左边，反之在右边

实现细节：

• 循环结束条件：找到匹配，或搜寻范围为空。如果是闭区间（$[0, len(list) - 1]$，那么搜寻范围为空的条件是 min >max
• 新范围的边界：由于是闭区间；因为当前中间数已经比较过了，重新规划新搜索区间时需要将中间数从范围内摘除出去：$[:mid -1]$ 或是 $[mid + 1: ]$

# 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)

• 如果只搜寻一次，那么 linear search 高效
• 搜寻次数越多，Binary search + Merge sort 越高效

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