浏览器发起 HTTP 请求的典型场景

我们通过上面这张图来解释一下浏览器是如何发起一个 HTTP 请求的。

HTTP 协议全称是超文本传输协议（Hypertext Transfer Protocol），这里面需要理解三个地方：超文本、传输、协议，下面就从 HTTP 协议的历史讲起。

20 世纪 60 年代，美国国防部高等研究计划署（ARPA）建立了 ARPA 网，它有四个分布在世界各地的节点，被认为是互联网的始祖。

到了 70 年代，基于对 ARPA 网络的实践和思考，研究人员发明出了著名的 TCP/IP 协议，并在 80 年代中期进入了 UNIX 内核，使更多计算机接入了互联网。

时间复杂度使用大 O 标记法，这个大家应该都清楚，下面是常见的增长量级：

Python 中基本操作分析

常量时间

算术操作大部分都是常量时间，除法 > 乘法 > 加法和减法；

索引操作（下标访问）和 len 函数也是常量时间；

假如一个字符串只包含一个字符，所有的操作都是常量的；

在列表结尾添加和删除一个元素是常量的；

大部分字典操作都是常量的，但是 update 方法的运行时间和传入的字典大小成正比，keys、values 和 items 都是常量时间，因为它们返回的是迭代器，但是如果循环遍历这个迭代器，则循环是线性的。

线性时间

使用 for 循环遍历一个序列或字典是线性的；

字符串和元组的大部分操作都是线性的；

min 和 max 函数也是线性的；

切片操作的运行时间与输出的长度成正比，而与输入的长度无关；

内置函数 sum 也是线性的，但速度更快；

字符串拼接是线性的，运行时间与操作数的长度的总和有关，所有的字符串方法都是线性的。

其他时间

大多数列表方法是线性的，但是除非空间不足时复制到另一个更大的空间，排序是 $nlogn$；

如果循环体的增长量级是 $O(n^a)$ 则整个循环是 $O(n^{a+1})$，如果不论 $n$ 是多少，循环只最多运行 $k$ 次，则及时对很大的 $k$ 来说，整个循环的增长量级还是 $O(n^a)$。

搜索算法的分析

遍历操作是线性的，二分查找是对数级的，散列表是常量时间。

条件表达式

我们经常会使用条件语句来从两个值中选择一个，例如：

1
2
3
4

if x > 0:
    y = math.log(x)
else:
    y = float('nan')

这几行代码会检查 x 是否为正数。如果为正数，则计算 math.log；如果为负数，math.log 会抛出 ValueError 异常。为了避免程序停止，则直接生成了“NAN”，一个特殊的浮点数，代表“不是数”。

实际上这几行代码可以使用更加简洁的方式：

1

y = math.log(x) if x > 0 else float('nan')

这条语句是不是可以非常简洁？

有时候，递归表达式也可以用条件表达式重写，以斐波那契数列为例：

1
2
3
4
5

def factorial(n):
    if n == 0:
        return 1
    else:
        return n * factorial(n-1)

可以将它重写为：

1
2

def factorial(n):
    return 1 if n ==0 else n * factorial(n-1)

一般来说，如果条件语句的两个分支都只包含简单的判断或对同一变量进行赋值的表达式，那么就可以转化为条件表达式。

列表解析式和生成器

列表解析式可以快速生成一个列表，例如假如需要对列表中的元素做某些操作，生成一个新的列表，可能我们会这样写：

1
2
3
4
5

def capitalize_all(t):
    res = []
    for s in t:
        res.append(s.capitalize())
    return res

而使用列表解析式操作是这样子的：

1
2

def capitalize_all(t):
    return [s.capitalize() for s in t]

生成器表达式与列表解析式有一点不同，那就是生成器表达式使用圆括号：

1
2
3

>>> g = (x**2 for x in range(5))
>>> g
<generator object <genexpr> at 0x000001B46BB8FE08>

这个结果是一个生成器对象，它不会把所有的结果一次性计算出来，而是请求一个获取一个，它使用 next 函数获取下一个值：

1
2
3
4

>>> next(g)
0
>>> next(g)
1

生成器表达式经常和 sum、max 和 min 之类的函数配合使用：

1
2

>>> sum(x**2 for x in range(5))
30

any 和 all

Python 中有两个内置函数 any 和 all。any 接收一个由布尔值组成的序列，并当其中任何值是 True 时返回 True。它可以用于列表：

1
2

>>> any([True, False])
True

但更常见于生成器表达式：

1
2

>>> any(letter == 't' for letter in 'monty')
True

all 函数则是在序列中所有元素都是 True 时返回 True。

集合和 collections 模块

集合 set 是 Python 中的另一种数据类型，集合中的元素是没有重复的。

例如，判断一个字符集是不是在另一个字符集中全部出现：

1
2

def uses_only(word, available):
    return set(word) <= set(available)

操作符 <= 检查一个集合是否是另一个集合的子集。

collections 模块包含了一些常用的方法，例如计数器 Counter、defaultdict、命名元组等。

列表

列表与字符串类似，也是一个序列，所不同的地方在于，字符串中的元素是字符，列表中的元素可以是任意类型，并且可以嵌套，例如，字典、元组、列表、字符串、数值类型都可以作为列表的元素。

创建列表

最简单的方式就是使用 [] 创建列表：

1
2
3
4
5
6

>>> l = []
>>> l
[]
>>> l = ['str', 2.0, 5, [10, 20]]
>>> l
['str', 2.0, 5, [10, 20]]

遍历列表

遍历一个列表元素最常见的方法，就是使用 for 循环：

1
2
3
4
5
6

>>> for i in l:
...     print(i)
str
2.0
5
[10, 20]

修改列表

列表是可变的，因此可以任意修改列表中的元素，修改的方法可以直接通过下标修改：

1
2
3

>>> l[1] = 10
>>> l
['str', 10, 5, [10, 20]]

还可以通过列表切片的方式修改：

1
2
3

>>> l[1:3] = 1, 2
>>> l
['str', 1, 2, [10, 20]]

需要注意的是，切片操作的第二个下标是不包含在内的。

添加列表元素

使用 append 方法在列表尾部添加元素：

1
2
3

>>> l.append('new')
>>> l
['str', 1, 2, [10, 20], 'new']

使用 extend 添加整个列表，extend 方法接收一个列表作为参数，并将其所有元素添加到原列表后面：

1
2
3
4

>>> l1 = [4, 5]
>>> l.extend(l1)
>>> l
['str', 1, 2, [10, 20], 'new', 4, 5]

同样可以通过切片操作添加列表元素：

1
2
3

>>> l[len(l):] = 'new2'
>>> l
['str', 1, 2, [10, 20], 'new', 4, 5, 'n', 'e', 'w', '2']

len(l) 计算列表的长度，同时没有指定切片操作第二个下标，表示将新元素全部添加到列表之后。

注意，使用切片操作添加或修改列表元素，如果元素长度超出了切片指定的下标长度，则会按照元素长度修改列表：

1
2
3
4
5
6
7
8

>>> l
['l', 'i', 's', 't']
>>> l[4:5] = 1, 2
>>> l
['l', 'i', 's', 't', 1, 2]
>>> l[0:1] = 2, 4, 6
>>> l
[2, 4, 6, 'i', 's', 't', 1, 2]

删除列表元素

如果知道元素的下标，可以使用 pop 方法删除：

1
2
3

>>> l.pop()
'2'
>>> l.pop(0)

不指定 pop 方法的参数的话，表示删除最后一个元素，同时 pop 可以返回删除的值。

del 方法同样可以删除元素，但是没有返回值：

1
2
3

>>> del l[2]
>>> l
[1, 2, 'new', 4, 5, 'n', 'e', 'w']

如果不知道要删除元素的下标，可以使用 remove 删除该元素：

1
2
3
4
5

>>> l
[2, 'new', 4, 5, 'n', 'e', 'w', 2]
>>> l.remove(2)
>>> l
['new', 4, 5, 'n', 'e', 'w', 2]

可以看到，这个列表中有两个 2，但是 remove 方法只删除了第一个 2，表示 remove 方法只会删除列表中第一个符合的元素就立即返回。

如果要删除多个元素，可以使用 del 和切片操作：

1
2
3

>>> del l[4:]
>>> l
['new', 4, 5, 'n']

字符串和列表的相互转换

使用 list 函数将字符串转换为列表：

1
2
3
4

>>> s = 'list'
>>> l = list(s)
>>> l
['l', 'i', 's', 't']

list 函数会将字符串中的每一个字符作为一个列表元素。

如果字符串可以按照分隔符分割，可以使用字符串方法 split：

1
2
3

>>> s = 'this is a str'
>>> s.split()
['this', 'is', 'a', 'str']

split 方法默认使用空格作为分隔符，当然也可采用其他分隔符，如 ‘-‘、’,’ 等，直接作为参数传入 split 方法即可。

使用 join 方法连接字符串列表：

1
2
3
4
5
6

>>> t
['this', 'is', 'a', 'str']
>>> ''.join(t)  # 不使用分隔符
'thisisastr'
>>> ' '.join(t)  # 空格作为分隔符
'this is a str'

列表操作注意事项

1. 修改列表的方法可以通过 append、extend、切片操作完成；
2. 删除列表元素可以通过 pop 方法、del 函数、remove 方法完成；
3. 切片操作可以对原列表修改，也可复制一个列表；
4. ‘+’ 操作符会创建一个新的列表；
5. 大部分列表方法没有返回值，这一点与字符串方法不同；
6. 列表的很多操作可以通过多种方式完成，应该选定一个操作并坚持不变。

字典

字典中的元素是一个键值对。作为键必须使用不可变类型，如字符串、元组等，而作为值则可以使用任意类型。这是因为，字典是通过散列表的形式实现的，因此字典的键必须是可散列的，可变类型是不可散列的。

在 3.7 版本之前，Python 字典中的元素是无序的，在 3.7 版本中解决了这个问题，元素的顺序按照添加的顺序确定。

字典的操作

创建字典

可以直接通过 {} 操作符创建字典：

1
2
3
4
5
6

>>> dic = dict()
>>> dic
{}
>>> dic1 = {}
>>> dic1
{}

同样可以使用 in 操作符遍历字典，不同的是，无论字典多大，in 操作符所花费的时间都差不多，这是采用散列表实现的原因。字典的修改直接对相应的键赋值即可。

反转字典

顾名思义，反转字典就是要将字典的值作为键，而键作为值，在原来的字典中，由于键是唯一的，所以可能会出现有多个相同的值，这个时候需要一个列表来存储新的值。

1
2
3
4
5
6
7
8
9

def invert_dict(d):
    inverse = {}
    for key in d:
        val = d[key]
        if val not in inverse:
            inverse[val] = [key]
        else:
            inverse[val].append(key)
    return inverse

优化的斐波那契数列

传统的斐波那契数列当参数变的较大时，函数运行的时间非常长，分析函数调用图可以发现，很多值是被重复计算的，因此可以将已经计算过的值保存在字典中。

1
2
3
4
5
6
7
8

known = {0: 0, 1: 1}
def fibonacci(n):
    if n in known:
        return known[n]
    else:
        res = fibonacci(n - 1) + fibonacci(n - 2)
        known[n] = res
        return res

使用字典作为备忘，可以使得程序的运行速度大大提高。

元组

作为另外一种内置类型，元组最大的特点就是不可变，元组和列表类似，可以通过下标索引。

创建元组

元组就是用 , 分割的一列值：

1
2
3

>>> t = 'a', 'b', 'c', 'd'  # 这种创建方法不常用，但是需要了解
>>> t
('a', 'b', 'c', 'd')

通常创建元组需要用括号括起来：

1

>>> t = ('a', 'b', 'c', 'd')

如果元组只包含一个元素，需要在元素后面加上逗号：

1
2

>>> t = 'a',
>>> t = ('a',)

还可以通过 tuple 函数创建：

1
2
3
4
5
6

>>> t = tuple()
>>> t
()
>>> t = tuple('tuple')
>>> t
('t', 'u', 'p', 'l', 'e')

不带参数会创建一个空的元组，如果参数是一个序列，结果就是一个包含序列的元素的元组。

除此之外，tuple 也支持切片操作，但不支持所有的修改操作。

元组赋值

Python 中交换两个变量的值非常轻松：

1

>>> a, b = b, a

一条语句即可完成交换，另外，语句的右边可以是任意类型的序列，例如想要拆分电子邮件地址：

1
2
3
4
5
6

>>> addr = 'monty@python.org'
>>> uname, domain = addr.split('@')
>>> uname
'monty'
>>> domain
'python.org'

参数的收集和分散

函数可以接收不定个数的参数，使用 * 操作符来收集参数：

1
2

def printall(*args):
    print (args)

* 会将所有的参数收集到一个元组中。

另外，如果有一个序列的值想将它们作为可变长参数传入到函数中，可以使用 * 操作符：

1
2
3

>>> t = (7, 3)
>>> divmod(*t)
(2, 1)

列表和元组

zip 函数可以接收多个序列，并返回一个元组列表，长度是序列中较短的一个，zip 是一种迭代器，可以使用 for 循环遍历，可以使用 zip 对象制作一个列表：

1
2

>>> list(zip('abc', '123'))
[('a', '1'), ('b', '2'), ('c', '3')]

如果需要遍历序列中的元素及其下标，可以使用 enumerate 函数：

1
2
3
4
5
6

>>> for index, element in enumerate('abc'):
...     print(index, element)
...
0 a
1 b
2 c

字典和元组

字典中的 items 方法返回元组序列，另外，使用 dict 和 zip 可以得到一个简洁的创建字典的方法：

1
2
3

>>> d = dict(zip('abc', range(3)))
>>> d
{'a': 0, 'b': 1, 'c': 2}