From a044c62101f9030a11e7cf323648674e3b3dd67d Mon Sep 17 00:00:00 2001 From: Hui Lan Date: Sun, 14 Apr 2019 20:46:00 +0800 Subject: =?UTF-8?q?=E6=B7=BB=E5=8A=A0=E6=8E=92=E5=BA=8F=E4=B8=80=E7=AB=A0?= MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit --- LectureNotesOnPython.html | 374 ++++++++++++++++++++++++++++++++++++++-------- LectureNotesOnPython.rst | 273 ++++++++++++++++++++++++++++++++- 2 files changed, 585 insertions(+), 62 deletions(-) diff --git a/LectureNotesOnPython.html b/LectureNotesOnPython.html index be18d22..f56596b 100644 --- a/LectureNotesOnPython.html +++ b/LectureNotesOnPython.html @@ -370,52 +370,64 @@ ul.auto-toc { Authors: 蓝珲 (lanhui AT zjnu.edu.cn) Version: -0.1.1 of 2019-04-14 +0.1.2 of 2019-04-14

内容目录

-

前言

+

前言

非学究写书，无空洞行文。

Python语法简洁，库函数全面强大，编程速度快，运行速度也不慢。

大学里， 往往是专家教初学者。 专家也是从初学者过来的，只不过专家经常忘 @@ -437,12 +449,12 @@ ul.auto-toc { 初学者说“我明白了”。

-

Python的发音纠正

+

Python的发音纠正

国人普遍把th发作s。 Not quite correct。

ˈpī-ˌthän , -thən pronounciation

-

Python源流

+

Python源流

Python之父Guido van Rossum，荷兰人，1956年生，1982年阿姆斯特丹大学获得 数学与计算机科学硕士学位。有过ABC语言的工作经验。1989年设计了Python语 言。

@@ -492,7 +504,7 @@ ul.auto-toc {
-

Python的关键词

+

Python的关键词

def pass
from import
@@ -514,7 +526,7 @@ ul.auto-toc {

关键词被语言留用（reserved），无法作变量名。

-

值的类型

+

值的类型

所有的值都是对象。a = 5, help(a) a.bit_length()

数字。1， 1.，1.1， .1, 1e1, 1e-1, 1E1, 1E-1

@@ -534,7 +546,7 @@ A list of objects

元组（tuple），字典（dict）。

-

变量（Variable）

+

变量（Variable）

是一个名字（name），是指向一个值（value）的名字。

值存放在内存（memory）中的某个地址。

尽量选有意义的简短的名字。比如，代表个数用n，代表索引用i，j，k。

@@ -623,7 +635,7 @@ A list of objects
-

可变（mutable）类型与不可变类型

+

可变（mutable）类型与不可变类型

字符串是不可变的（immutable）类型，不能在原内存地址改变。

a = 'hello' 不可以原地修改a[0] = 'H'。需要修改a的值时，需要对a进行重新赋值a = 'Hello'。

列表是可变（mutable）类型，能在原内存地址改变。

@@ -648,7 +660,7 @@ A list of objects
-

数与格式化显示

+

数与格式化显示

x = 3.1415926
@@ -696,7 +708,7 @@ A list of objects
-

字符串（Strings）

+

字符串（Strings）

由字符组成。

fruit = 'banana!'
@@ -752,7 +764,7 @@ A list of objects

以上 # [start,stop,step] 代表注释（comment），注释以 # 号开头。

-

字符串相加（concatenation）

+

字符串相加（concatenation）

输出Jack, Kack, Lack, Mack, Nack, Ouack, Pack, and Quack

prefixes = 'JKLMNOPQ'
@@ -771,7 +783,7 @@ A list of objects
-

子串（slice）

+

子串（slice）

s[n:m]，其中n或m可省略。 包括第n个字符，不包括第m个字符。（索引自0开始）

@@ -795,7 +807,7 @@ A list of objects
-

搜索字符串

+

搜索字符串

def find(word, c):
@@ -821,7 +833,7 @@ A list of objects

练习：用上面三参数的find来做。

-

String类（对象）方法

+

String类（对象）方法

upper()
lower()
@@ -834,14 +846,14 @@ A list of objects
-

in操作符

+

in操作符

'a' in 'banana' 'seed' in 'banana'

练习：写出下面的函数，使得 in_both('apples', 'oranges')返回'aes'。

-

字符串比较

+

字符串比较

字典序（alphabetical order）。大写字母排在小写字母前。

字符串之间可以有以下对比操作:

@@ -857,7 +869,7 @@ in_both('apples', 'oranges')返回'aes'。

即兴定义函数，制造一个长度不小于4的密码。

-

列表

+

列表

语言的内置（built-in）类型。注意与String类比，index也是从0开始， in操作符， 求长度，获得字串，遍历操作类似。

@@ -975,7 +987,7 @@ a与b是指向[1,2,3]的两个references。 error-prone（易错）

-

列表作为参数

+

列表作为参数

def delete_head(t):
@@ -991,7 +1003,7 @@ error-prone（易错）

-

注意区别 append 与 + 操作符

+

注意区别 append 与 + 操作符

t1 = [1, 2]
@@ -1018,7 +1030,7 @@ error-prone（易错）

-

TDD - Test-driven Development

+

TDD - Test-driven Development

测试驱动开发。 My favourite。 刺激有挑战性。 帮助厘清需求。 帮助编写代码。

推荐使用pytest。如何安装？ 使用命令 pip install pytest。

在 test_cases.py 写如下测试用例。然后在命令行运行： python -m pytest test_cases.py 。

@@ -1058,13 +1070,13 @@ error-prone（易错）

-

计算复杂度

+

计算复杂度

用Big O表述复杂度。O(n)， O(n^2), O(n^3)。

密码实验回顾。

-

字典（Dictionary）

+

字典（Dictionary）

Mutable数据类型。

实际开发中超级有用。

@@ -1088,7 +1100,7 @@ error-prone（易错）

key-value pair (item)

item的顺序不可预测，不是按照创建时的顺序。

-

递增开发（Incremental Development）

+

递增开发（Incremental Development）

每次完成一小点。从易到难。

练习：给定一个字符串，数出每个字母出现的频率。

@@ -1196,7 +1208,7 @@ error-prone（易错）

 
练习： 改写函数 word_frequency ， 使它能接受第三个参数， black_lst。 black_lst 是包含要排除考虑的单词的列表。 例如， black_lst 可以是 ['the', 'and', 'of', 'to'] 。
-

key与value互换

+

key与value互换

注意到在原来的字典中一个value可能对应多个key的值。比如 d = {'a':1, 'b':2, 'c':2} 中，2就对应两个key，'b'与'c'。

 def inverse_dictionary(d):
@@ -1233,14 +1245,14 @@ error-prone（易错）
-

字典里面可以有字典

+

字典里面可以有字典

 d = { 'john':{'dob':'1990-10-23', 'height':'6 feet 5 inches'} }
-

函数

+

函数

当我们开始不断复制黏贴代码时，就要考虑把这部分代码做成函数了。

函数 unique_words 与 unique_words2 哪个运行速度快？

@@ -1259,11 +1271,11 @@ error-prone（易错）

 print(unique_words2(['hello', 'world', 'am', 'he'] * N))
-

局部变量

+

局部变量

在函数之内。函数执行结束，局部变量消失。

-

全局变量

+

全局变量

全局变量位于函数之外，模块之内。全局变量对所有模块内的函数可见（可读）。如果在函数内要对全局变量重新赋值，那么要先用 global 声明之 （declare）。

 verbose = True
@@ -1313,7 +1325,7 @@ error-prone（易错）

 
练习： 定义一个函数 empty_dict 清空字典 record。 要求: 不能用 return 语句。 提示： 可以用 pop 方法， 或者直接给 record 赋值 {} 。
-

调用函数与传递参数

+

调用函数与传递参数

在使用函数前要先确定函数已经被定义。

区别 argument 与 parameter 。传过去的是 argument ， 函数头的参数列表是 parameter 。 argument 的值赋给 parameter ， parameter 是函数的局部变量。

argument 与 parameter 的名字可以相同也可以不同。

@@ -1334,13 +1346,253 @@ error-prone（易错）

以上 t 一个是全局变量一个是局部变量。

-

函数执行顺序 （flow of execution）

+

函数执行顺序 （flow of execution）

函数的定义不执行，被调用时才执行。

顺序执行。 当遇到函数调用时，跳转到函数，执行函数，函数返回后继续执行跳转地后一条语句。

-

参考

+

排序

+

排序是常见重要的操作。 按照成绩排序。 按照文件名排序。 按照文件大小排序。 按照时间排序。

+

Python自带的 sorted 可以很好满足排序需求。

+
+

排序一组数或一组字符串

+

如果需要从大到小排序， 添加 reverse=True 。

+
+# Sort numbers
+import random
+a = [random.randint(0,100) for i in range(5)] # a list of 5 random numbers between 0 and 100
+print(a)
+
+sa_incr = sorted(a)
+print(sa_incr)
+
+sa_decr = sorted(a, reverse=True)
+print(sa_decr)
+
+# Sort a list of strings
+s = 'D3.js is a JavaScript library for manipulating documents based on data. D3 helps you bring data to life using HTML, SVG, and CSS. D3’s emphasis on web standards gives you the full capabilities of modern browsers without tying yourself to a proprietary framework, combining powerful visualization components and a data-driven approach to DOM manipulation.  https://d3js.org/'
+lst = list(set(s.split()))
+
+sa_incr = sorted(lst)
+print(sa_incr)
+
+sa_decr = sorted(lst, reverse=True)
+print(sa_decr)
+
+
+
+

自定义排序算法

+

为了弄清排序的原理， 我们看两种排序算法。

+
+

选择排序

+

遍历列表，每次把最小的那个放到最左边位置。

+
+def swap(L, i, j):
+    L[j], L[i] = L[i], L[j]
+
+
+def selection_sort(L):
+    i = 0
+    while i < len(L):
+        min_val = L[i]
+        k = j = i
+        while j < len(L):
+            if L[j] < min_val:
+                min_val = L[j]
+                k = j
+            j += 1
+        swap(L, i, k) # will change L
+        i += 1
+    return L
+
+if __name__ == '__main__':
+
+    import random
+    for n in range(10):
+        a = [random.randint(0,100) for i in range(n)]
+        sa = selection_sort(a)
+        print(sa)
+        assert sa == a
+        assert sa == sorted(a)
+
+
+
+

合并排序 （Merge sort）

+

将列表一分为二，对每半部分排序，把排好序的两部分合并之（确保合并后同样是排好序的）。 注意到，以下的实现方式是递归。

+
+def _merge(L, R):
+    ''' Return a sorted list that combines the sorted list L and sorted list R.'''
+    nL = len(L)
+    nR = len(R)
+    result = []
+    i = j = count = 0
+    while count < nL + nR:
+        if i >= nL and j < nR:
+            result.append(R[j])
+            j += 1
+        elif j >= nR and i < nL:
+            result.append(L[i])
+            i += 1
+        elif L[i] < R[j]:
+            result.append(L[i])
+            i += 1
+        else:
+            result.append(R[j])
+            j += 1
+        count += 1
+    return result
+
+
+def merge_sort(L):
+    if len(L) <= 1:
+        return L
+    else:
+        i = int(len(L)/2)
+        l = merge_sort(L[:i])
+        r = merge_sort(L[i:])
+        return _merge(l, r)
+
+if __name__ == '__main__':
+
+    import random
+    for n in range(100):
+        a = [random.randint(0,100) for i in range(n)]
+        sa = merge_sort(a)
+        assert sa == sorted(a)
+
+
+
+
+

比较排序速度

+

排序是 Python 的核心算法，所以是优化了再优化。

+

Python 自带的排序算法最快， selection_sort 最慢。

+
+from merge_sort import merge_sort
+from selection_sort import selection_sort
+
+import random, time
+L = [random.randint(0,10000) for i in range(10000)]
+
+print('Python sort ...')
+now = time.time()
+result0 = sorted(L)
+print(time.time() - now)
+
+
+print('Merge sort ...')
+now = time.time()
+result1 = merge_sort(L)
+print(time.time() - now)
+
+print('Selection sort ...')
+now = time.time()
+result2 = selection_sort(L)
+print(time.time() - now)
+
+assert result0== result1
+assert result1 == result2
+
+

在命令行运行上面的程序，在作者的计算机上得到如下的结果。

+
+
Python sort ...
+
0.002
+
Merge sort ...
+
0.083
+
Selection sort ...
+
11.57
+
+
+
+

排序元组列表

+

一个元组由多个元素组成，多个元组组成元组列表， 如何按照某个元素进行排序呢？

+

可以有以下两种方案。一种用模块 operator ， 一种用 lambda 函数。

+
+def sort_by_nth_element(lst, n):
+    ''' Return a sorted list of tuples lst, according to the nth element in each tuple.'''
+    import operator
+    result = sorted(lst, key=operator.itemgetter(n))
+    return result
+
+
+def sort_by_nth_element2(lst, n):
+    ''' Return a sorted list of tuples lst, according to the nth element in each tuple.'''
+    import operator
+    result = sorted(lst, key=lambda x: x[n]) # https://stackoverflow.com/questions/8966538/syntax-behind-sortedkey-lambda
+    return result
+
+
+if __name__ == '__main__':
+    lst = [(1, 'xxx', 2), (2, 'aaa', 1)]
+    print(sort_by_nth_element(lst, 0))
+    print(sort_by_nth_element(lst, 1))
+    print(sort_by_nth_element(lst, 2))
+
+    print(sort_by_nth_element2(lst, 0))
+    print(sort_by_nth_element2(lst, 1))
+    print(sort_by_nth_element2(lst, 2))
+
+
+
+

巧用 lambda 函数进行灵活排序

+

如何把一个由字符串组成的列表按照字符串的长短进行排序？

+
+lst = ['this', 'is', 'a', 'example']
+a = sorted(lst, key=lambda x: len(x))
+b = sorted(lst, key=lambda x: -len(x))
+print('\n'.join(a))
+
+s = '''https://genius.com/William-shakespeare-romeo-and-juliet-act-1-prologue-annotated#note-2756596
+Romeo and Juliet
+PROLOGUE
+Two households, both alike in dignity,
+In fair Verona, where we lay our scene,
+From ancient grudge break to new mutiny,
+Where civil blood makes civil hands unclean.
+From forth the fatal loins of these two foes
+A pair of star-cross'd lovers take their life;
+Whose misadventured piteous overthrows
+Doth with their death bury their parents' strife.
+The fearful passage of their death-mark'd love,
+And the continuance of their parents' rage,
+Which, but their children's end, nought could remove,
+Is now the two hours' traffic of our stage;
+The which if you with patient ears attend,
+What here shall miss, our toil shall strive to mend.'''
+
+lst = s.split('\n')
+c = sorted(lst, key=lambda x: len(x))
+d = sorted(lst, key=lambda x: -len(x))
+print('\n'.join(c))
+
+

以上程序运行会输出如下结果。

+
+
a
+
is
+
this
+
example
+
PROLOGUE
+
Romeo and Juliet
+
Two households, both alike in dignity,
+
Whose misadventured piteous overthrows
+
In fair Verona, where we lay our scene,
+
From ancient grudge break to new mutiny,
+
The which if you with patient ears attend,
+
And the continuance of their parents' rage,
+
Is now the two hours' traffic of our stage;
+
Where civil blood makes civil hands unclean.
+
From forth the fatal loins of these two foes
+
A pair of star-cross'd lovers take their life;
+
The fearful passage of their death-mark'd love,
+
Doth with their death bury their parents' strife.
+
What here shall miss, our toil shall strive to mend.
+
Which, but their children's end, nought could remove,
+
https://genius.com/William-shakespeare-romeo-and-juliet-act-1-prologue-annotated#note-2756596
+
+
+
+
+

参考

diff --git a/LectureNotesOnPython.rst b/LectureNotesOnPython.rst index 5251078..a729f22 100644 --- a/LectureNotesOnPython.rst +++ b/LectureNotesOnPython.rst @@ -5,7 +5,7 @@ Lecture Notes on Python :Authors: 蓝珲 (lanhui AT zjnu.edu.cn) -:Version: 0.1.1 of 2019-04-14 +:Version: 0.1.2 of 2019-04-14 @@ -1071,6 +1071,277 @@ key与value互换 +排序 +------------------------------------------------ + +排序是常见重要的操作。 按照成绩排序。 按照文件名排序。 按照文件大小排序。 按照时间排序。 + +Python自带的 ``sorted`` 可以很好满足排序需求。 + + +排序一组数或一组字符串 +~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ + +如果需要从大到小排序， 添加 ``reverse=True`` 。 + +.. code:: python + + # Sort numbers + import random + a = [random.randint(0,100) for i in range(5)] # a list of 5 random numbers between 0 and 100 + print(a) + + sa_incr = sorted(a) + print(sa_incr) + + sa_decr = sorted(a, reverse=True) + print(sa_decr) + + # Sort a list of strings + s = 'D3.js is a JavaScript library for manipulating documents based on data. D3 helps you bring data to life using HTML, SVG, and CSS. D3’s emphasis on web standards gives you the full capabilities of modern browsers without tying yourself to a proprietary framework, combining powerful visualization components and a data-driven approach to DOM manipulation. https://d3js.org/' + lst = list(set(s.split())) + + sa_incr = sorted(lst) + print(sa_incr) + + sa_decr = sorted(lst, reverse=True) + print(sa_decr) + + +自定义排序算法 +~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ + +为了弄清排序的原理， 我们看两种排序算法。 + + +选择排序 +``````````````````````````````````````````````````` + +遍历列表，每次把最小的那个放到最左边位置。 + +.. code:: python + + def swap(L, i, j): + L[j], L[i] = L[i], L[j] + + + def selection_sort(L): + i = 0 + while i < len(L): + min_val = L[i] + k = j = i + while j < len(L): + if L[j] < min_val: + min_val = L[j] + k = j + j += 1 + swap(L, i, k) # will change L + i += 1 + return L + + if __name__ == '__main__': + + import random + for n in range(10): + a = [random.randint(0,100) for i in range(n)] + sa = selection_sort(a) + print(sa) + assert sa == a + assert sa == sorted(a) + + +合并排序 （Merge sort） +``````````````````````````````````````````````````` + +将列表一分为二，对每半部分排序，把排好序的两部分合并之（确保合并后同样是排好序的）。 注意到，以下的实现方式是递归。 + +.. code:: python + + def _merge(L, R): + ''' Return a sorted list that combines the sorted list L and sorted list R.''' + nL = len(L) + nR = len(R) + result = [] + i = j = count = 0 + while count < nL + nR: + if i >= nL and j < nR: + result.append(R[j]) + j += 1 + elif j >= nR and i < nL: + result.append(L[i]) + i += 1 + elif L[i] < R[j]: + result.append(L[i]) + i += 1 + else: + result.append(R[j]) + j += 1 + count += 1 + return result + + + def merge_sort(L): + if len(L) <= 1: + return L + else: + i = int(len(L)/2) + l = merge_sort(L[:i]) + r = merge_sort(L[i:]) + return _merge(l, r) + + if __name__ == '__main__': + + import random + for n in range(100): + a = [random.randint(0,100) for i in range(n)] + sa = merge_sort(a) + assert sa == sorted(a) + + + +比较排序速度 +~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ + +排序是 Python 的核心算法，所以是优化了再优化。 + +Python 自带的排序算法最快， ``selection_sort`` 最慢。 + + +.. code:: python + + from merge_sort import merge_sort + from selection_sort import selection_sort + + import random, time + L = [random.randint(0,10000) for i in range(10000)] + + print('Python sort ...') + now = time.time() + result0 = sorted(L) + print(time.time() - now) + + + print('Merge sort ...') + now = time.time() + result1 = merge_sort(L) + print(time.time() - now) + + print('Selection sort ...') + now = time.time() + result2 = selection_sort(L) + print(time.time() - now) + + assert result0== result1 + assert result1 == result2 + + +在命令行运行上面的程序，在作者的计算机上得到如下的结果。 + +| Python sort ... +| 0.002 +| Merge sort ... +| 0.083 +| Selection sort ... +| 11.57 + + +排序元组列表 +~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ + +一个元组由多个元素组成，多个元组组成元组列表， 如何按照某个元素进行排序呢？ + +可以有以下两种方案。一种用模块 ``operator`` ， 一种用 ``lambda`` 函数。 + +.. code:: python + + def sort_by_nth_element(lst, n): + ''' Return a sorted list of tuples lst, according to the nth element in each tuple.''' + import operator + result = sorted(lst, key=operator.itemgetter(n)) + return result + + + def sort_by_nth_element2(lst, n): + ''' Return a sorted list of tuples lst, according to the nth element in each tuple.''' + import operator + result = sorted(lst, key=lambda x: x[n]) # https://stackoverflow.com/questions/8966538/syntax-behind-sortedkey-lambda + return result + + + if __name__ == '__main__': + lst = [(1, 'xxx', 2), (2, 'aaa', 1)] + print(sort_by_nth_element(lst, 0)) + print(sort_by_nth_element(lst, 1)) + print(sort_by_nth_element(lst, 2)) + + print(sort_by_nth_element2(lst, 0)) + print(sort_by_nth_element2(lst, 1)) + print(sort_by_nth_element2(lst, 2)) + + +巧用 lambda 函数进行灵活排序 +~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ + +如何把一个由字符串组成的列表按照字符串的长短进行排序？ + +.. code:: python + + lst = ['this', 'is', 'a', 'example'] + a = sorted(lst, key=lambda x: len(x)) + b = sorted(lst, key=lambda x: -len(x)) + print('\n'.join(a)) + + s = '''https://genius.com/William-shakespeare-romeo-and-juliet-act-1-prologue-annotated#note-2756596 + Romeo and Juliet + PROLOGUE + Two households, both alike in dignity, + In fair Verona, where we lay our scene, + From ancient grudge break to new mutiny, + Where civil blood makes civil hands unclean. + From forth the fatal loins of these two foes + A pair of star-cross'd lovers take their life; + Whose misadventured piteous overthrows + Doth with their death bury their parents' strife. + The fearful passage of their death-mark'd love, + And the continuance of their parents' rage, + Which, but their children's end, nought could remove, + Is now the two hours' traffic of our stage; + The which if you with patient ears attend, + What here shall miss, our toil shall strive to mend.''' + + lst = s.split('\n') + c = sorted(lst, key=lambda x: len(x)) + d = sorted(lst, key=lambda x: -len(x)) + print('\n'.join(c)) + + +以上程序运行会输出如下结果。 + + +| a +| is +| this +| example +| PROLOGUE +| Romeo and Juliet +| Two households, both alike in dignity, +| Whose misadventured piteous overthrows +| In fair Verona, where we lay our scene, +| From ancient grudge break to new mutiny, +| The which if you with patient ears attend, +| And the continuance of their parents' rage, +| Is now the two hours' traffic of our stage; +| Where civil blood makes civil hands unclean. +| From forth the fatal loins of these two foes +| A pair of star-cross'd lovers take their life; +| The fearful passage of their death-mark'd love, +| Doth with their death bury their parents' strife. +| What here shall miss, our toil shall strive to mend. +| Which, but their children's end, nought could remove, +| https://genius.com/William-shakespeare-romeo-and-juliet-act-1-prologue-annotated#note-2756596 + + + 参考 ------ -- cgit v1.2.1