What & How & Why

您在这里: start » cs » programming » python » courses » gtx_cs1301x » chpt_5

差别

这里会显示出您选择的修订版和当前版本之间的差别。

到此差别页面的链接

两侧同时换到之前的修订记录前一修订版
后一修订版		前一修订版
cs:programming:python:courses:gtx_cs1301x:chpt_5 [2024/01/14 13:59] – 移除 - 外部编辑 (未知日期) 127.0.0.1cs:programming:python:courses:gtx_cs1301x:chpt_5 [2024/01/14 14:03] (当前版本) – ↷ 链接因页面移动而自动修正 codinghare
行 1: 行 1:
 +======Objects & Algorithms======
 +//Chapter 5 notes//
 +----
 +====Objects====
 +  * //**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.
 +==Classes vs. Instances==
 +  * Class: 对特定类型数据的一般性描述
 +  * instance: 基于指定类型的 class 特例（实例）
 +===Objects and Instances in Python===
 +==定义 class 和 instances==
 +  * 需要类名，构造函数 ''__init__''
 +  * 成员的初始值可以是任意类型，包括函数，或者其他类（或类成员）
 +<code py>
 +# 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
 +</code>
 +==Creating Instances==
 +<code py>
 +# creating instance
 +myName = Name()
 +# accessing
 +print(myName.firstname)
 +# assignment
 +myName.firstname = "Gray"
 +
 +## nesting ##
 +myStudent = Student()
 +# assignment
 +myStudent.name.firstname = "David"
 +</code>
 +==classes 的优势==
 +  * 保证 key 的存在
 +  * 在存储数据的同时，提供 methods 方便数据的管理
 +===Encapsulating Methods in Classes===
 +  * Encapsulation：封装，将变量与成员函数的定义至于类中，保证类中的数据不会被其他函数或程序误用。
 +  * 通用的 Method分类：constructor, destrcutor, getters, setters
 +==Constructors and Destructors==
 +  * //**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.
 +==Getters and Setters==
 +  * 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
 +<WRAP center round box 100%>
 +比起直接访问数据，利用 //getter// 和 //setter// 提供了更多的便利：
 +  * 提供读写权限（保证只能从特定的权限级别访问数据）
 +  * 提供额外的功能（比如记录访问的历史记录）
 +</WRAP>
 +===Encapsulating Methods in Python===
 +==Constructors in Python==
 +  * 构造函数的初始化列表需要在 ''__init__'' 内部定义
 +  * 构造函数可以接受外部传递的 variable
 +<code py>
 +# 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")
 +</code>
 +<WRAP center round box 100%>
 +parameter 数量不满足抛出的异常为 //TypeError//.
 +</WRAP>
 +==Getters and Setters==
 +<WRAP center round info 100%>
 +Python 中没有提供 access level（比如 C++ 中公私类的申明）。python 中，如果不希望被直接调用的函数，一般前后都有两个下划线，比如 //init//
 +</WRAP>
 +<code py>
 +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
 +</code>
 +<WRAP center round tip 100%>
 +类中可以提供一个 log 成员函数，用于将每次的改动记录到文本中，方便跟踪。
 +</WRAP>
 +===Advanced Topics in Classes in Python===
 +==instance 作为初始化参数==
 +instance 可以作为另外一个 instance 的参数。比如：
 +<code py>
 +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)
 +</code>
 +==instance 的赋值==
 +将旧的 instance 赋值给新的 instance（name），等于给了这个 instance 修改旧 instance 内内容的权限。任何通过新 instance 修改的内容，均会直接影响旧的 Instance， 比如：
 +<code py>
 +myPerson1 = Person(Name("David", "Joyner"), "brown", 30)
 +myPerson2 = myPerson1
 +myPerson2.eyecolor = "blue"
 +</code>
 +这里无论是通过 ''myPerson1'' 还是 ''myPerson2'' 访问 ''eyecolor''，都会得到 ''blue'' 的结果。实际上，两个 Name 指向的都是同一个变量。
 +<WRAP center round box 100%>
 +可以说 instance 也是 mutable 的变量。
 +</WRAP>
 +==Instances as Arguments==
 +instance 也可以作为 argument 传递给函数。这种情况下，函数也会改变 instance 内部的变量值。访问实例如下：
 +<code py>
 +# 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)
 +</code>
 +注意，如果函数的 argument 不是 Mutable 的，那么函数是无法改变 argument 对应的对象的。比如：
 +<code py>
 +# 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()
 +</code>
 +==instance 的实拷贝==
 +  * 如果希望进行实拷贝，传递的参数类型必须是 immutable 的参数。
 +  * 对于 instance，如果希望直接拷贝，我们需要强制创建一个新的 instance 作为参数。
 +  * 如果该 instance 需要另外一个 instance 作为参数，那么这个 instance 也需要再重新创建一次
 +<code py>
 +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)
 +</code>
 +===Polymorphism and Inheritance and Abstraction===
 +  * **//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.
 +====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==
 +  * Data Compression
 +  * Random Number Generator
 +  * Search Algorithms
 +===Complexity and Big O Notation===
 +==Complexity==
 +  * **//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 ==
 +  * **//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)$
 +  * 算法大多数都有自己擅长的数据领域。不同的数据中，同样的算法带来的复杂度会有高有低。
 +==Common Big O Values==
 +  * $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===
 +  * //**Recursion**//: A programming method characterized by functions that, during their operation, call a**dditional copies of themselves**
 +    * 主要思想是将问题分解为更小的，可以用相同方法解决的问题。
 +==实例：factoral==
 +以 $5!$ 为例。要以递归的方式计算 $5!$，那么需要思考的有两个问题：
 +  * $5!$ 有没有办法分解为更小的，但性质相同的问题
 +  * $5!$ 最后会不会有一个终结的 case
 +可以看出来，$5!$ 可以表示为 $5 \times 4!$，$4!$ 可以表示为 $4 \times 3!$。一直直到 $2!$ 可以表示为 $2 \times 1!$。$1!$ 的值显而易见，因此可以用做 base。而之前的通项可以表达为：
 +$$
 +n \times (n-1)!
 +$$
 +因此，如果将阶乘的设计为函数 ''fractoral()''，那么该函数的伪代码可以写成：
 +<code py>
 +fractoral(n):
 +   if n > 1:
 +      return n * fractoral(n-1)
 +   else:
 +      return 1
 +</code>
 +<WRAP center round box 100%>
 +需要注意的是，这里最开始的 $n$，实际上是处于 stack 的最底层。最先计算的，实际上是我们的 base case，也就是这里的 1。这个过程可以想象为，如果我们要解 $5!$，那么首先要求 $4!$，如果要求 $4!$，首先要得到 $3!$...以此类推。当我们最终达到我们已知的 base case，也就是求得 $2!$ 时，整个递归会将求得的结果带入到 stack 下方已经展开的计算部分，直到完成计算。
 +</WRAP>
 +{{ cs:programming:python:courses:gtx_cs1301x:recursion.svg?100 |}}
 +==实例2:Fibonacci 数列==
 +  * base case: $1$ ($F(1) = 1$, $F(2) = 1$)
 +  * general: $F(n-2) + F(n-1) (n > 2)$
 +<code py>
 +Fibonacci(n):
 +    if n > 2:
 +        return Fibonacci(n-2) + Fibonacci(n-1)
 +    else:
 +        return 1
 +</code>
 +==尾递归和首递归==
 +假设在递归的过程中，同时还有其他的操作（比如 print)。根据该操作与递归调用的位置不同，递归分为**首递归**（//head recursion//）和**尾递归**（//tail recursion//）。参考下面的例子：
 +<code py>
 +# 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)    
 +</code>
 +他们的主要区别在于递归调用是否优先。如果优先调用递归（首递归），那么最开始的打印操作会处于 stack 的最底层。他必须要等到所有栈里的递归调用结束以后，才能开始打印。因此，''count_down_1()'' 的打印结果会从 ''0'' 打印到 ''5''，也就是栈顶的打印会优先执行。\\ \\ 
 +如果优先执行打印（尾递归），那么程序将先打印，再压栈。因此，''count_down_2()'' 的打印结果会从 ''5'' 到 ''0''，先压入栈的，也就是栈底的打印操作先执行。
 +===Sorting Algorithms===
 +==Bubble Sort==
 +该算法的算法复杂度为 $O(n^2)$。\\ \\ 
 +//Bubble Sort// 的核心是：
 +  * 比较相邻的两个元素
 +  * 如果顺序不对，就调换两个元素的位置。
 +  * 所有元素比较完成后，再重复上面的步骤，直到排序完成
 +实现的细节：
 +  * 用一个 swap tag 来判断当前是否还有交换发生。
 +  * 没有交换发生意味着排序换成
 +<code py>
 +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
 +</code>
 +==Selection Sort==
 +该算法的复杂度为 $O(n^2)$。\\ \\ 
 +该算法的核心是：
 +  * 扫描整个 list，将最小的值找出来，插入到 list 第一个元素之前
 +  * 将其他剩余的元素视作整个 list，重复上面的步骤（e.g. 第一轮 0-9，第二轮 1-9，以此类推），直到排序换成
 +<code py>
 +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 
 +</code>
 +==Insertion Sort==
 +该算法的算法复杂度是 $O(n^2)$。\\ \\ 
 +//Insertion sort// 的核心是：
 +  * 将整个 list 分成两部分，已经排序的和没有排序的。
 +  * 排好序的部分处于左边，从两个数开始。
 +  * 每一轮从右边未排序部分加入一个数到左边
 +  * 将该数与已排序部分的所有数比较，比较完毕后将其插入对应的位置
 +对应的位置的查找原理：
 +  * 将新加入的数与已排序部分每一个数进行对比
 +  * 如果有一个数大于新加入的数，那么该数一定是已排序部分中，大于新加入数的最小的那一个。
 +  * 因此，新加入数应该插入该数之前
 +细节：
 +  * 找到了大于新加入的数的数以后，就无需再进行余下的比较了。
 +<code py>
 +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
 +</code>
 +==Merge Sort==
 +该算法的算法复杂度是 $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 进行排序，最终就能得到结果。
 +<code py>
 +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
 +</code>
 +===Search Algorithms===
 +==Linear Search==
 +按位搜寻，算法复杂度为 $O(n)$
 +==Binary Search==
 +  * 只能应用于有序数据集
 +  * 使用递归
 +  * 算法复杂度为 $O(log(n))$
 +//Binary Search// 的核心：
 +  * 使用当前范围的中间数与搜索关键词比较
 +    * 相等即证明找到
 +    * 不相等：关键词小于当前中间数，证明搜寻范围应该在中间数的左边，反之在右边
 +实现细节：
 +  * 循环结束条件：找到匹配，或搜寻范围为空。如果是闭区间（$[0, len(list) - 1]$，那么搜寻范围为空的条件是 ''min >max''
 +  * 新范围的边界：由于是闭区间；因为当前中间数已经比较过了，重新规划新搜索区间时需要将中间数从范围内摘除出去：$[:mid -1]$ 或是 $[mid + 1: ]$
 +<code py>
 +# 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)
 +</code>
 +==Binary search + Merge sort v.s. linear search==
 +  * 如果只搜寻一次，那么 linear search 高效
 +  * 搜寻次数越多，Binary search + Merge sort 越高效
 +Binary search + Merge sort 这种方式的主要开销在 merge sort，其复杂度是 linear search 的 $log(n)$ 倍。但由于整个数据集只需排序一次，因此如果要反复进行不同内容的搜索，//Binary search// 的效率要高得多。