插入排序

《算法导论》第一部分中并没有详细讲解某一种算法，而是以讲解算法这个概念，而插入排序是讲解算法基础的例子。

输入： n 个数的一个序列 <a1, a2, ..., an>。
输出： 输入序列的一个排列 <a1', a2', ..., an'>

因为算法很简单，就直接上代码：

A = [2, 5, 1, 3, 7, 6]

def instertion_sort(nums):
    for i in range(1, len(nums)):
        key = nums[i]
        j = i - 1
        while j >= 0 and nums[j] > key: # compare nums[j] and key
            nums[j + 1] = nums[j]
            j -= 1
        nums[j + 1] = key # set nums[j + 1] is key
    return nums


if __name__ == '__main__':
    print(instertion_sort(A))

下午看完了第二章第二节之后，晚上尝试完全凭记忆敲这段代码，结果还是出了两个问题，就是我打注释的两个地方。

第一个是 while 的判断条件，j 的临界条件是不小于 0，可能因为导论的数组是从 1 开始的，进过我已经意识到了，在写 range 的时候就意识到了，但是我手写的时候依然写的是 j > 0，可能只是下意识的担心越界。

第二个地方就是 nums[j + 1] = key，我一开始的时候写的是，nums[i] = key，这个应该是纯粹脑残了，因为 while 以 key 为基准，对前 i 个数字排排坐，而 key 最后落座在哪里，是通过 while 循环跑出来的，也就是说是和 j 的值相关。

循环不变式

对于循环不变式这个概念，导论引入的的确有点突兀，不过在看了一些人有趣的解释之后也算是明白了（比如知乎的这个讨论：https://www.zhihu.com/question/26700198 ）

循环不变式是验证循环正确性的一种方法，关注循环体中的主要的属性（比如在插入排序中 nums[0...i-1] 这段数字是保持递增的属性），如果这种属性能在开始循环时，循环中，结束循环后，都一直保持，那么我们就认为这个循环是正常工作的。

在算法导论中尝试使用数学归纳法来验证这个循环：

初始化： 循环得第一次迭代之前，它为真
保持： 如果循环的某次迭代之前它为真，那么下次迭代之前它仍为真
终止： 在循环终止时，不变式为我们提供一个有用的性质，该性质有助于证明算法是正确的。

因为这三个状态（开始，进行，结束），nums[0...i-1] 始终保持了递增这一个属性，因此验证了插入排序这个算法的正确性。

文档： https://pythonhosted.org/psutil/

Github： https://github.com/giampaolo/psutil

安装

pip install psutil

常用功能

因为毕设中只用到了 CPU，内存，磁盘这三个属性，但是这个库能获得的状态不止这些，还有网络，传感器和各种系统属性。只写下自己用到的，其他的文档介绍的挺全面。

CPU

psutil.cpu_times(percpu=False)

cpu_times 函数接受一个参数，percpu，默认为 False。

>>> psutil.cpu_times()
scputimes(user=33335.82, nice=0.0, system=35253.52, idle=405130.12)

执行之后将返回 user mode 和 kernel mode 的 CPU 时间（user，system），以及 CPU 空转的时间（idle）。

如果加上 percpu 参数，之后，将返回每个核心的信息：

>>> psutil.cpu_times(percpu=True)
[scputimes(user=12113.43, nice=0.0, system=14012.23, idle=92520.62), scputimes(user=4881.28, nice=0.0, system=4959.2, idle=108794.75), scputimes(user=11446.36, nice=0.0, system=11263.96, idle=95924.97), scputimes(user=4969.93, nice=0.0, system=5093.61, idle=108571.62)]

如果只是计算 CPU 的利用率的话，psutil.cpu_percent() 就够解决问题，cpu_percent 可以传递一个间隔参数，来计算一定间隔内的 CPU 利用率:

>>> psutil.cpu_percent(1)
13.7

内存

因为我只需要计算内存的使用率，所以只用到了 virtual_memory 方法。这个方法返回的参数很多，不过也是一目了然。

>>> psutil.virtual_memory()
svmem(total=17179869184L, available=4261830656L, percent=75.2, used=13366374400L, free=2298265600L, active=9087324160L, inactive=1963565056L, wired=2315485184L)

磁盘

disk_partitions 方法可以查看磁盘的使用情况，会返回一个 list，包含了比较全面的信息：

>>> psutil.disk_partitions()
[sdiskpart(device='/dev/disk1', mountpoint='/', fstype='hfs', opts='rw,local,rootfs,dovolfs,journaled,multilabel'), sdiskpart(device='/dev/disk0s3', mountpoint='/Volumes/Recovery HD', fstype='hfs', opts='rw,local,dovolfs,dontbrowse,journaled,multilabel')]

当然，以上只是提到了最简单的功能，还有很多使用的函数可以选择。

安装

pip install beautifulsoup4

解析器需要单独安装，html 解析器：

pip install html5lib

更多安装相关查看文档： 安装解析器

解析

搜索引擎收录的中文文档有点老旧，直接使用会报错，但是解析是一件很简单的事情：

from bs4 import BeautifulSoup
soup = BeautifulSoup(html_txt, "html5lib")

定位

定位分两种，一个是直接根据标签：

soup.title
# <title>The Dormouse's story</title>

soup.title.name
# u'title'

soup.title.string
# u'The Dormouse's story'

soup.title.parent.name
# u'head'

soup.p
# <p class="title"><b>The Dormouse's story</b></p>

soup.p['class']
# u'title'

soup.a
# <a class="sister" href="http://example.com/elsie" id="link1">Elsie</a>

另一种是通过 find 方法，该方法支持查找，包括 id，class，标签：

soup.find_all('a')
# [<a class="sister" href="http://example.com/elsie" id="link1">Elsie</a>,
#  <a class="sister" href="http://example.com/lacie" id="link2">Lacie</a>,
#  <a class="sister" href="http://example.com/tillie" id="link3">Tillie</a>]

soup.find(id="link3")
# <a class="sister" href="http://example.com/tillie" id="link3">Tillie</a>

安装

$ pip install requests

使用

GET：

payload = {'key1': 'value1', 'key2': 'value2'}
r = requests.get('https://github.com/timeline.json', params=payload)

POST

r = requests.post("http://httpbin.org/post", data=data)

其他方法：

r = requests.put("http://httpbin.org/put")
r = requests.delete("http://httpbin.org/delete")
r = requests.head("http://httpbin.org/get")
r = requests.options("http://httpbin.org/get")

响应

对于获取普通的 body，可以从 text 属性中获得：

import requests
r = requests.get('https://github.com/timeline.json')
r.text
u'[{"repository":{"open_issues":0,"url":"https://github.com/...

对于二进制数据，可以使用 r.content, 对于 json 的话，可以直接使用 r.json()，该方法会返回一个被解析的字典或列表。

无论是请求还是相应，用法比较符合直觉，更详细见文档： http://docs.python-requests.org/zh_CN/latest/user/quickstart.html

Session

虽然 http 是无状态的，但是请求往往是连续的，状态一般存储在 cookie 里。requests.Session 类便提供了一个 cookie 持续的请求方式，一般自定义 http client 都会继承自这个类。

用法：

>>> import requests
>>> s = requests.Session()
>>> s.get('http://httpbin.org/get')
<Response [200]>

# with
>>> with requests.Session() as s:
>>>     s.get('http://httpbin.org/get')
<Response [200]>

更多的参数可以参考相关文档：Session 更多参数

Object's Identity

对于任何一个 Object 来说，都有一个 id，如果多个变量指向了同一个静态常量，那么这几个变量讲拥有同样的 id。

>>> s1 = "abc"
>>> s2 = "abc"
>>> s1 == s2
True
>>> id(s1)
4390873208
>>> id(s2)
4390873208
>>> s1 is s2
True

如果两个不同的变量（常量），肯定将有不同的 id。

>>> id("abc")
4390873208
>>> id("abcd")
4391753216

is 比较

在 python 中，有两种常用的比较方式，一个是 == 比较，一个是 is 比较，前者是用来比较值是不是相等，后者是判断是不是属于同一个对象。其实，在 python 中，is 比较便是通过 id() 来实现的。当两个 Objec 拥有相同的 id 时，便会认为这是两个相同的对象。

因此，可以认为：object1 is object2 等价于 id(object1) == id(object2) 。

例外

今天在 v2ex 看到一个好玩的帖子（https://www.v2ex.com/t/336021 ），提到了 id([1]) == id([2]) 会返回 True。

而我跑了一组数据，结果也是很有意思：

>>> id([1]) 
4391579520 
>>> id([2]) 
4391579520 
>>> a = [1] 
>>> b = [1] 
>>> id([1]) 
4391757944 
>>> id([2]) 
4391757944 
>>> id(a) 
4391579520 
>>> id(b) 
4391641672 
>>> id([1]) 
4391787072
>>> id([2]) 
4391787072  

因为在文档中已经提到了，两个不同生命域的对象可能会有相同的 id，因此出现这种情况也不例外，毕竟 [1]，[2]，现在的确是两个不同的生命域的常量，因为这两个常量没有被任何变量引用，当使用结束之后，便会被回收掉，因此会出现两个不同的常量出现相同 id 的情况。

当给他们添加引用，会发现这个 id 就被确定到这个一个 [1] 常量上了，这是因为 这个 [1] 的生命域并没有结束（还被引用不能被回收），因此，新的 list object 不会再使用这个 id 而是换了新的 id。

2018.11.16 更新

今天又看到一种新的验证方式，定义如下类：

class WTF(object):
  def __init__(self): print("I")
  def __del__(self): print("D")

is 比较时，两个对象先创建再比较：

In [2]: WTF() is WTF()
I
I
D
D
Out[2]: False

id 比较时，当对象的 id 被获得之后，对象就会被注销，新对象恰好会分配在原内存空间，因此得到 True。

In [3]: id(WTF()) == id(WTF())
I
D
I
D
Out[3]: True